Programación cuadrática secuencial

La programación cuadrática secuencial ( SQP ) es uno de los algoritmos de optimización de propósito general más comunes y efectivos [1] , cuya idea principal es la solución secuencial de problemas de programación cuadrática que aproximan un problema de optimización dado . Para problemas de optimización sin restricciones , el algoritmo SQP se transforma en el método de Newton para encontrar el punto en el que el gradiente de la función objetivo va a cero. Para resolver el problema original con restricciones de igualdad, el método SQP se transforma en una implementación especial de los métodos newtonianos para resolver el sistema de Lagrange .

Información básica

Considere un problema de programación no lineal de la siguiente forma:

{\ estilo de visualización \ min \ límites _ {x} f (x),}

bajo restricciones

b(x)\geqslant 0,\;c(x)=0.

El Lagrangiano del problema toma la siguiente forma:

L(x,\;\lambda ,\;\sigma )=f(x)-\lambda ^{T}b(x)-\sigma ^{T}c(x),

donde y son los multiplicadores de Lagrange . $\lambda$ $\sigma$

En la iteración del algoritmo principal, las direcciones de búsqueda correspondientes se determinan como una solución al siguiente subproblema de programación cuadrática : $x_k$ $d_{k}$

\min \limits _{d}L(x_{k},\;\lambda _{k},\;\sigma _{k})+\nabla L(x_{k},\;\lambda _{k},\;\sigma_{k})^{T}d+{\frac {1}{2}}d^{T}\nabla_{xx}^{2}L(x_{k} ,\;\lambda _{k},\;\sigma _{k})d,

bajo restricciones

b(x_{k})+\nabla b(x_{k})^{T}d\geqslant 0,\;c(x_{k})+\nabla c(x_{k})^{ T}d=0.

Véase también

método de newton

Notas

↑ Trifonov A.G. Optimization Toolbox 2.2 User Guide Copia de archivo fechada el 11 de agosto de 2016 en Wayback Machine // Softline Co.

Literatura

Programación Cuadrática Secuencial

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