Sekwencyjne programowanie liniowo-kwadratowe

Sekwencyjne programowanie liniowo-kwadratowe ( SLQP ) to iteracyjna metoda rozwiązywania nieliniowych problemów optymalizacyjnych , w których funkcja celu i ograniczenia są dwukrotnie różniczkowalne w sposób ciągły . Podobnie jak w przypadku sekwencyjnego programowania kwadratowego (SQP), SLQP polega na rozwiązywaniu sekwencji podproblemów optymalizacji. Różnica między tymi dwoma podejściami polega na tym, że:

w SQP każdy podproblem jest programem kwadratowym , z kwadratowym modelem celu podlegającym linearyzacji ograniczeń
w SLQP na każdym kroku rozwiązywane są dwa podproblemy: program liniowy (LP) używany do określenia aktywnego zbioru , po którym następuje program kwadratowy z ograniczeniami równości (EQP) używany do obliczenia całkowitego kroku

Ten rozkład sprawia, że SLQP nadaje się do rozwiązywania problemów optymalizacyjnych na dużą skalę, dla których dostępne są wydajne rozwiązania LP i EQP, przy czym problemy te są łatwiejsze do skalowania niż pełnoprawne programy kwadratowe.

Podstawy algorytmu

Rozważ problem programowania nieliniowego postaci:

{\ Displaystyle {\ rozpocząć {tablica} {rl} \ min \ limity _ {x} & f (x) \\ {\ mbox {st }}&b(x)\geq 0\\&c(x)=0.\end{tablica}}}

Lagrange'a dla tego problemu jest

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

gdzie i $_$ $_$ Lagrange'a _ _

faza LP

W fazie LP SLQP rozwiązywany jest następujący program liniowy:

{\ Displaystyle {\ rozpocząć {tablica} {rl} \ min \ ograniczenia _ {d} & f (x_ {k}) + \ nabla f (x_ {k}) ^ {T} d \\\ operatorname {st} & b (x_{k})+\nabla b(x_{k})^{T}d\geq 0\\&c(x_{k})+\nabla c(x_{k})^{T}d=0 .\end{tablica}}}

Niech ${\ cal {A}} _ {k}}$ $Displaystyle$ oznacza zbiór aktywny w optymalnym czyli powiedzieć, zestaw ograniczeń, które są równe zeru w ${\ Displaystyle d _ {\ tekst {LP}} ^ {*}}$ . Oznacz przez ${{\ cal {A}$ $} _ {k}}}$ i wektorów podrzędnych i do ${\ displaystyle$ $}$ odpowiadające elementom ${\ displaystyle {\ cal {A}} _ {k}}$ .

Faza EQP

W fazie EQP SLQP kierunek wyszukiwania kroku jest uzyskiwany przez rozwiązanie następującego programu kwadratowego z ograniczeniami równości: re ${\ displaystyle d_ {k}$

{\ Displaystyle {\ rozpocząć {tablica} {rl} \ min \ ograniczenia _ {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 { st} &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{tablica}}}

Zauważ, że termin w powyższych funkcjach $celu$ można pominąć w przypadku problemów z minimalizacją

Zobacz też

Notatki

Jorge Nocedal i Stephen J. Wright (2006). Optymalizacja numeryczna . Skoczek. ISBN 0-387-30303-0 .