Sekventiell linjär-kvadratisk programmering

Sekventiell linjär-kvadratisk programmering ( SLQP ) är en iterativ metod för icke-linjära optimeringsproblem där objektiv funktion och begränsningar är två gånger kontinuerligt differentierbara . På samma sätt som sekventiell kvadratisk programmering (SQP), fortsätter SLQP genom att lösa en sekvens av optimeringsunderproblem. Skillnaden mellan de två tillvägagångssätten är att:

i SQP är varje delproblem ett kvadratiskt program , med en kvadratisk modell av målet föremål för en linearisering av begränsningarna
i SLQP löses två delproblem i varje steg: ett linjärt program (LP) som används för att bestämma en aktiv uppsättning , följt av ett jämlikhetsbegränsat kvadratiskt program (EQP) som används för att beräkna det totala steget

Denna nedbrytning gör SLQP lämplig för storskaliga optimeringsproblem, för vilka effektiva LP- och EQP-lösare finns tillgängliga, dessa problem är lättare att skala än fullfjädrade kvadratiska program.

Grunderna i algoritmen

Tänk på ett icke-linjärt programmeringsproblem av formen:

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

Lagrangian för detta problem är

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

där $\lambda \geq 0$ och $\sigma$ är lagrangemultiplikatorer .

LP-fas

I LP-fasen av SLQP löses följande linjära program:

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

Låt ${\cal {A}}_{k}$ beteckna den aktiva mängden vid den optimala $d_{\text{LP}}^{*}$ för detta problem, dvs. att säga, uppsättningen av begränsningar som är lika med noll vid $d_{\text{LP}}^{*}$ . Beteckna med $b_{{\cal {A}}_{k}}$ och $c_{{\cal {A}}_{k}}$ undervektorerna för $b$ och $c$ som motsvarar element i ${\cal {A}}_{k}$ .