Active-set-metod

"Active set" omdirigerar hit. För bandet, se The Active Set .

I matematisk optimering är den aktiva uppsättningsmetoden en algoritm som används för att identifiera de aktiva begränsningarna i en uppsättning ojämlikhetsbegränsningar . De aktiva restriktionerna uttrycks sedan som likhetsrestriktioner, och transformerar därigenom ett ojämlikhetsbegränsat problem till ett enklare jämlikhetsbegränsat delproblem.

Ett optimeringsproblem definieras med hjälp av en objektiv funktion för att minimera eller maximera, och en uppsättning begränsningar

$g_{1}(x)\geq 0,\dots ,g_{k}(x)\geq 0$

som definierar den möjliga regionen , det vill säga mängden av alla x för att söka efter den optimala lösningen. Givet en punkt $x$ i den genomförbara regionen, en begränsning

$g_{i}(x)\geq 0$

kallas aktiv vid $\displaystyle x_{0}}$$g_{i}(x_{0})>0.$ om $g_{i}(x_{0})=0$ , och inaktiv vid $displaystyle x}$ om Likhetsbegränsningar är alltid aktiva. Den aktiva uppsättningen vid $x_{0}$ består av de begränsningar $\displaystyle g_{i}(x_{0})}$ som är aktiva vid den aktuella punkten ( Nocedal & Wright 2006 s. 308).

Den aktiva uppsättningen är särskilt viktig i optimeringsteorin, eftersom den avgör vilka begränsningar som kommer att påverka det slutliga resultatet av optimeringen. Till exempel, när man löser det linjära programmeringsproblemet , ger den aktiva uppsättningen hyperplanen som skär varandra vid lösningspunkten. I kvadratisk programmering , eftersom lösningen inte nödvändigtvis finns på en av kanterna av den avgränsande polygonen, ger en uppskattning av den aktiva mängden oss en delmängd av olikheter att titta på när vi söker efter lösningen, vilket minskar sökningens komplexitet.

Active-set metoder

I allmänhet har en aktiv uppsättningsalgoritm följande struktur:

Hitta en genomförbar startpunktsupprepning

tills "optimal nog"

löser likhetsproblemet definierat av den aktiva mängden (ungefär)

sök beräkna Lagrangemultiplikatorerna för den aktiva mängden

ta bort en delmängd av begränsningarna med negativa Lagrangemultiplikatorer

efter omöjliga begränsningar

avsluta upprepning

Metoder som kan beskrivas som aktiva uppsättningsmetoder inkluderar:

• Successiv linjär programmering (SLP)
• Sekventiell kvadratisk programmering (SQP)
• Sekventiell linjär-kvadratisk programmering (SLQP)
• Metod med reducerad gradient (RG)
• Generaliserad reducerad gradientmetod (GRG)

Bibliografi

•    Murty, KG (1988). Linjär komplementaritet, linjär och olinjär programmering . Sigma-serien i tillämpad matematik. Vol. 3. Berlin: Heldermann Verlag. s. xlviii+629 s. ISBN 3-88538-403-5 . MR 0949214 . Arkiverad från originalet 2010-04-01 . Hämtad 2010-04-03 .
•   Nocedal, Jorge; Wright, Stephen J. (2006). Numerisk optimering (2:a upplagan). Berlin, New York: Springer-Verlag . ISBN 978-0-387-30303-1 .