Показать меню

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

13.12.2020
157

Последовательное квадратичное программирование (англ. 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.}
Еще по этой теме:
Алгоритм Кармаркара
17:59, 11 декабрь
Алгоритм Кармаркара
Алгоритм Кармаркара — это алгоритм, представленный Нарендра Кармаркаром в 1984 для решения задач линейного программирования. Это был первый достаточно эффективный алгоритм, который решал задачи за
Метод фазовых функций
16:02, 08 декабрь
Метод фазовых функций
Метод фазовых функций — метод решения задач квантовой механики. Основан на понятии фазовой функции, имеющей ясный физический смысл. При рассмотрении движения элементарной частицы в потенциальном
Эволюционно-симулятивный метод
09:43, 08 декабрь
Эволюционно-симулятивный метод
Эволюционно-симулятивный метод (ЭСМ) — метод моделирования равновесных случайных процессов и принятия решений в условиях неопределенности. ЭСМ успешно применяется в экономике и физике. Общие
PPAML
01:30, 08 декабрь
PPAML
PPAML (Probabilistic Programming for Advanced Machine Learning) — Исследовательская программа Агентства по перспективным оборонным научно-исследовательским разработкам США, посвящённая вероятностному
Субградиентные методы
16:47, 04 декабрь
Субградиентные методы
Субградиентные методы — итеративные методы решения задач выпуклой минимизации. Субградиентные методы, разработанные Наумом Зуселевич Шором и другими учёными в 1960-х и 1970-х, сходятся даже если
APX
08:20, 02 декабрь
APX
APX (от англ. «approximable») в теории вычислительной сложности — это класс NP-трудных задач, для которых существуют аппроксимационные алгоритмы полиномиальной сложности с постоянным коэффициентом
Комментарии:
Добавить комментарий
Ваше Имя:
Ваш E-Mail: