Metoda množice aktivnih omejitev

Metoda množice aktivnih omejitev (krajše metoda aktivne množice) je pristop pri reševanju problemov nelinearnega programiranja oziroma optimizacijskih problemov z neenakostnimi omejitvami.

Pri tej metodi v zaporednih iteracijah preoblikujemo neenakostne omejitve, ki so aktivne, v enakostne omejitve. V vsaki iteraciji rešimo problem s tako preoblikovanimi omejitvami. Na koncu iteracije preverimo, katere neenakostne omejitve so postale aktivne v novem približku (posodobimo množico aktivnih omejitev) ter na podoben način začnemo naslednjo iteracijo z novo množico aktivnih neenakostnih omejitev, ki jih zamenjamo z enakostnimi.

Metoda je v osnovi uporabna pri linearnih omejitvah, torej pri linearnem in kvadratičnem programiranju. Je tudi sestavni del različnih algoritmov za reševanje splošnih problemov nelinearnega programiranja, saj reševanje teh problemov pogosto prevedemo na zaporedno reševanje problemov linearnega ali kvadratičnega programiranja.

Metodo aktivne množice pogosto uporabljamo v povezavi z minimizacijo v dani smeri ali z metodo omejenega koraka.

Aktive omejitve

Pri optimizacijskih problemih z neenakostnimi omejitvami imamo funkcijo, ki jo minimiziramo ali maksimiziramo, ter množico omejitev oblike

$g_{1}(\mathbf {x} )\leq 0,\dots ,g_{m}(\mathbf {x} )\leq 0$,

ki določajo dopustno območje - množico vseh tistih točk x, med katerimi iščemo optimalno rešitev. V dani točki x je neenakostna omejitev

$g_{j}(\mathbf {x} )\leq 0$

aktivna, če je

$g_{j}(\mathbf {x} )\geq 0$,

in neaktivna, če je

$g_{j}(\mathbf {x} )<0$,

Množica aktivnih omejitev oziroma aktivna množica imenujemo v kontekstu optimizacijskih postopkov množico vseh omejitev, ki so aktivne v točki, ki jo trenutno obravnavamo.

V kontekstu optimizacijskih problemov včasih govorimo o aktivnih omejitvah, kadar so dane omejitve aktivne v rešitvi optimizacijskega problema (kar pomeni, da je vrednost omejitvene funkcije v rešitvi enaka 0). V tem kontekstu so neaktivne omejitve tiste, za katerih omejitvene funkcije velja v rešitvi problema $\mathbf {x} ^{*}$ $g_{j}(\mathbf {x} ^{*})<0$ (to so torej omejitve, ki ne vplivajo na lokalno rešitev problema). Bolj natančno govorimo o omejitvah, ki so aktivne ali neaktivne v rešitvi problema.

Glej tudi

• Optimizacija
• Nelinearno programiranje
• Minimizacija v dani smeri
• Metoda omejenega koraka