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

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

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

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

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

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

$b(x)⩾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 {\mathrm{\backslash limits}}_{d}L(x_k,{\lambda }_k,{\sigma }_k)+\mathrm{\nabla }L(x_k,{\lambda }_k,{\sigma }_k{)}^{T}d+\frac{1}{2}{d}^T\underset{xx}{\overset{2}{\mathrm{\nabla }}}L(x_k,{\lambda }_k,{\sigma }_k)d,$

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

$b(x_k)+\mathrm{\nabla }b(x_k{)}^{T}d⩾0,c(x_k)+\mathrm{\nabla }c(x_k{)}^{T}d=0.$

См. также

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

Литература

• Sequential Quadratic Programming