Método Piyavsky

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 1 de septiembre de 2017; la verificación requiere 1 edición .

El método de Piyavsky es un método para encontrar el mínimo ( máximo ) global de una función de Lipschitz dada en un conjunto compacto . Es fácil de implementar y tiene condiciones de convergencia bastante simples. Adecuado para una amplia clase de funciones cuya derivada, por ejemplo, podemos limitar.

Idea de método

Deje que la función definida en satisfaga la condición de Lipschitz: $f(x)$ $\izquierda[a,b\derecha]$

$\mid f(x_{2})-f(x_{1})\mid \leq L\|x_{2}-x_{1}\|$ .

Las condiciones de Lipschitz obviamente implican una desigualdad bilateral que limita el comportamiento esperado de la función.

$f_{i}-L\|x-x_{i}\|\leq f(x)\leq f_{i}+L\|x-x_{i}\|$ ,

donde , el punto en el que se realizó la medición. $f_{i}$

Hagamos algunas pruebas . $x_{1},x_{2},...,x_{k}\rightarrow f_{1},f_{2},...,f_{k}$

Llamemos a la función minorant y majorant . $f_{k}^{-}(x)=\max_{{i=\overline {1,k}}}^{{}}\left\{f_{i}-L\|x-x_{i }\|\derecho\}$ $f_{k}^{+}(x)=\min_{{i=\overline {1,k}}}^{{}}\left\{f_{i}+L\|x-x_{i }\|\derecho\}$

Gráficamente, son líneas discontinuas, por lo que el método de Piyavsky a menudo también se denomina método de línea discontinua. Obviamente, limitan la función desde dos lados: $f_{k}^{-}(x)\leq f(x)\leq f_{k}^{+}(x)$

Denotemos . El mínimo global de una función se puede estimar: $f_{k}^{*}=\min _{{i=\overline {1,k}}}^{{}}\left\{f_{i}\right\}$ $f(x^{*})$ $\min _{{x\in \left[a,b\right]}}^{{}}\left\{f_{k}^{-}(x)\right\}\leq f(x^{ *})\leq f_{k}^{*}$

Al hacer que el "corredor" indicado sea menor que el predeterminado , se puede encontrar el mínimo global de la función. El método de Piyavsky en cada paso realiza una nueva prueba de la función , mientras corrige la minorante y la estimación actual del mínimo global. Las pruebas se realizan en el punto mínimo del minorante actual. $\varepsilon$ $f_{{yo+1}}$

Algoritmo

Establecemos (o evaluamos) la constante de Lipschitz , la precisión y el número de intentos iniciales. $L>0$ $\varepsilon >0$ $k_{0}$
Estas pruebas las realizamos en diferentes puntos del compacto . . $k$ $x_{1},x_{2},...,x_{k}\rightarrow f_{1},f_{2},...,f_{k}$ $k:=k_{0}$
$f_{k}^{*}=\min _{{i=\overline {1,k}}}^{{}}\left\{f_{i}\right\}$ . Simplemente puede comparar con el valor en la iteración anterior.
$x_{{k+1}}=arg\min_{{x\in\Pi_{k}}}^{{}}f_{k}^{-}(x)$ , donde . $\Pi _{k}=\left\{x\in K:f(x)\leq f_{k}^{*}\right\}$
Si - detener. El mínimo se encuentra en el punto . $f_{k}^{*}-f_{k}^{-}(x_{{k+1}})\leq\varepsilon$ $x_{{k+1}}$
Se está realizando una prueba . . Se corrige la menor. Regrese al paso 2. $f_{{k+1}}=f(x_{{k+1}})$ $k:=k+1$

Teorema de la convergencia

Sea compacto. - Lipschitz, con constante , . Entonces, para cualquier forma de colocar los puntos iniciales , el método de Piyavsky se detendrá después de un número finito de pasos , y . $k$ $f(x)$ $L>0$ $\varepsilon >0$ $x_{1},x_{2},...,x_{k}\en K$ $N(f)$ $f_{k}^{*}-f(x^{*})\leq\varepsilon$

Literatura

Piyavsky S. A. Un algoritmo para encontrar el extremo absoluto de funciones // Journal of Computational Mathematics and Mathematical Physics, volumen 12, número 4 (1972), páginas 885—896.
Norkin V. I. Sobre el método de Piyavsky para resolver un problema general de optimización global // Journal of Computational Mathematics and Mathematical Physics, volumen 32, número 7 (1992), páginas 992—1006.

Métodos de optimización
unidimensional	método de la sección áurea Dicotomía método de parábola búsqueda de cuadrícula Método de búsqueda de bloque uniforme método fibonacci búsqueda ternaria método Piyavsky Método Strongin
orden cero	método de Gauss Método Nelder-Mead Método Hook-Jeeves método de Rosenbrock metodo powell
Primer orden	descenso de gradiente método Zeutendijk Descenso coordinado método de gradiente conjugado Métodos Cuasi-Newtonianos Algoritmo de Levenberg-Marquardt
segundo orden	método de newton Método de Newton-Raphson Algoritmo de Broyden-Fletcher-Goldfarb-Shanno (BFGS)
estocástico	Método de Montecarlo recocido simulado Algoritmos evolutivos evolución diferencial Algoritmo de hormiga método de enjambre de partículas Algoritmo de colonia de abejas Método de paseo aleatorio
Métodos de programación lineal	método símplex algoritmo de gomori método elipsoide método potencial
Métodos de programación no lineal	Programación cuadrática secuencial