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

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

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

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

$\min\limits_x f(x),$

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

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

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

$L(x,\;\lambda,\;\sigma)=f(x)-\lambda^Tb(x)-\sigma^Tc(x),$

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

На итерации $x_k$ основного алгоритма определяются соответствующие направления поиска $d_k$ как решение следующей подзадачи квадратичного программирования:

$\min\limits_d L(x_k,\;\lambda_k,\;\sigma_k)+\nabla L(x_k,\;\lambda_k,\;\sigma_k)^Td+\frac{1}{2}d^T\nabla_{xx}^2 L(x_k,\;\lambda_k,\;\sigma_k)d,$

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

$b(x_k)+\nabla b(x_k)^Td\geqslant 0,\;c(x_k)+\nabla c(x_k)^Td=0.$

См. также

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

Примечания

1. ↑ Трифонов А. Г. Optimization Toolbox 2.2 Руководство пользователя // Softline Co.

Литература

• Sequential Quadratic Programming

Для улучшения этой статьи по математике желательно?: Добавить иллюстрации. Проставить для статьи более точные категории. Проставив сноски, внести более точные указания на источники. Проверить качество перевода с иностранного языка.