Последовательное квадратичное программирование

Последовательное квадратичное программирование (англ. Sequential quadratic programming (SQP)) — один из наиболее распространённых и эффективных оптимизационных алгоритмов общего назначения, основной идеей которого является последовательное решение задач квадратичного программирования, аппроксимирующих данную задачу оптимизации. Для оптимизационных задач без ограничений алгоритм SQP преобразуется в метод Ньютона поиска точки, в которой градиент целевой функции обращается в ноль. Для решения исходной задачи с ограничениями-равенствами метод SQP преобразуется в специальную реализацию ньютоновских методов решения системы Лагранжа.

Основные сведения

Рассмотрим задачу нелинейного программирования следующего вида:

$\min \limits _{x}f(x),$

при ограничениях

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

Лагранжиан задачи примет следующий вид:

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

где $\lambda$ и $\sigma$ — множители Лагранжа.

На итерации $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,$

при ограничениях

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

См. также

• Метод Ньютона

Литература

• Sequential Quadratic Programming