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

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

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

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

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

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

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

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

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

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

На итерации ${\displaystyle x_{k}}$ основного алгоритма определяются соответствующие направления поиска ${\displaystyle d_{k}}$ как решение следующей подзадачи квадратичного программирования:

${\displaystyle \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,}$

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

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

См. также

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