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

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

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

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

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

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

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

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

L ( x , λ , σ ) = f ( x ) − λ T b ( x ) − σ T c ( x ) , {displaystyle L(x,;lambda ,;sigma )=f(x)-lambda ^{T}b(x)-sigma ^{T}c(x),}

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

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

min d L ( x k , λ k , σ k ) + ∇ L ( x k , λ k , σ k ) T d + 1 2 d T ∇ x x 2 L ( x k , λ k , σ k ) d , {displaystyle min limits _{d}L(x_{k},;lambda _{k},;sigma _{k})+ abla L(x_{k},;lambda _{k},;sigma _{k})^{T}d+{frac {1}{2}}d^{T} abla _{xx}^{2}L(x_{k},;lambda _{k},;sigma _{k})d,}

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

b ( x k ) + ∇ b ( x k ) T d ⩾ 0 , c ( x k ) + ∇ c ( x k ) T d = 0. {displaystyle b(x_{k})+ abla b(x_{k})^{T}dgeqslant 0,;c(x_{k})+ abla c(x_{k})^{T}d=0.}