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

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

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

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

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

Рассмотрим нелинейное программирование проблема формы:

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

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

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

куда ${\displaystyle \lambda }$ и ${\displaystyle \sigma }$ находятся Множители Лагранжа.

Фаза LP

В LP-фазе SLQP решается следующая линейная программа:

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

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

Фаза EQP

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

${\displaystyle {\begin{array}{rl}\min \limits _{d}&f(x_{k})+\nabla f(x_{k})^{T}d+{\tfrac {1}{2}}d^{T}\nabla _{xx}^{2}{\mathcal {L}}(x_{k},\lambda _{k},\sigma _{k})d\\\mathrm {s.t.} &b_{{\cal {A}}_{k}}(x_{k})+\nabla b_{{\cal {A}}_{k}}(x_{k})^{T}d=0\\&c_{{\cal {A}}_{k}}(x_{k})+\nabla c_{{\cal {A}}_{k}}(x_{k})^{T}d=0.\end{array}}}$

Обратите внимание, что термин ${\displaystyle f(x_{k})}$ в приведенных выше целевых функциях может быть опущено для задач минимизации, поскольку она постоянна.

Смотрите также

• Метод Ньютона
• Секущий метод
• Последовательное линейное программирование
• Последовательное квадратичное программирование

Примечания

1. Хорхе Нокедаль и Стивен Дж. Райт (2006). Численная оптимизация. Springer. ISBN  0-387-30303-0.

Рекомендации

• Хорхе Нокедаль и Стивен Дж. Райт (2006). Численная оптимизация. Springer. ISBN  0-387-30303-0.