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

Последовательное линейно-квадратичное программирование ( SLQP ) — это итеративный метод решения задач нелинейной оптимизации , где целевая функция и ограничения дважды непрерывно дифференцируются . Подобно последовательному квадратичному программированию (SQP), SLQP предполагает решение последовательности подзадач оптимизации. Разница между двумя подходами заключается в том, что:

в SQP каждая подзадача представляет собой квадратичную программу с квадратичной моделью цели, подверженной линеаризации ограничений.
в SLQP на каждом шаге решаются две подзадачи: линейная программа (LP), используемая для определения активного набора , за которой следует квадратичная программа с ограничениями равенства (EQP), используемая для вычисления общего шага.

Такое разложение делает SLQP подходящим для крупномасштабных задач оптимизации, для которых доступны эффективные решатели LP и EQP, причем эти задачи легче масштабировать, чем полноценные квадратичные программы.

Его можно считать связанным с квазиньютоновскими методами , но отличным от них .

Основы алгоритма

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

{\begin{array}{rl}\min \limits _{x}&f(x)\\{\mbox{s.t.}}&b(x)\geq 0\\&c(x)=0.\end{array}}

Лагранжиан для этой задачи есть ^[1]

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

где $\lambda \geq 0$ и $\sigma$ являются множителями Лагранжа .

Фаза низкого давления

На этапе LP SLQP решается следующая линейная программа:

{\begin{array}{rl}\min \limits _{d}&f(x_{k})+\nabla f(x_{k})^{T}d\\\mathrm {s.t.} &b(x_{k})+\nabla b(x_{k})^{T}d\geq 0\\&c(x_{k})+\nabla c(x_{k})^{T}d=0.\end{array}}

Позволять ${\cal {A}}_{k}$ обозначаем активный набор в оптимуме $d_{\text{LP}}^{*}$ этой задачи, то есть набор ограничений, равных нулю в точке $d_{\text{LP}}^{*}$ . Обозначим через $b_{{\cal {A}}_{k}}$ и $c_{{\cal {A}}_{k}}$ подвекторы $b$ и $c$ соответствующие элементам ${\cal {A}}_{k}$ .