9. PROBLEM VEZANIH EKSTREMOV Z NEENAČBAMI (VEN)

definicija problema vezanih ektremov z neenačbami (VEN)

zapis lagrangeeve funkcije

kaj so lagrangeevi multiplikatorji/množitelji

Lagrangeevi množitelji so pomožni skalarji (λ_i), s katerimi VEN prevedemo na iskanje navadnih ekstremov

KKT pogoji

kdaj so KKT pogoji zadostni za globalni minimum?

torej: KKT pogoji so zadostni če sta ciljna funkcija in mn. dopustnik rešitev konveksni

izreko o potrebnih KKT pogojih za problem vezanih ekstremov z neenačbami

torej, če že vemo, da je neka točka optimalna, mora ta nujno izpolnjevati KKT pogoje

Sletherjev pogoj

D˚≠ ∅

notranjost dopustnega območja D ne sme biti prazna, tj. obstaja notranja točka - ta točka izpolnjuje pogoj:

g_i(x) < 0 za vse i= 1,…,m

kdaj je VEN konveksen?

Problem vezanih ekstremov (VEN) je konveksen natanko tedaj, ko:

• je Ω konveksna množica

• je konveksna ciljna funkcija

• so vezi g_i: Ω→R i = 1,…,m konveksne funkcije

• če v problemu nastopajo vezi z enakostmi h_j(x) = 0 morajo biti te afine

iskanje optimalne rešitve VEN

1. preverimo konveksnost problema:

ciljna funkcija je konveksna, vse vezi v obliki enakosti so afine, vse vezi v obili neenakosti so konveksne

2. zapišemo Lagrangeevo funkcijo

3. parcialno odvedemo Lagrangeevo funkcijo po vsaki spremenljivki

4. pogoji:

• stacionarnost: L_xi = 0

• dualna dopustnost: λ_i > 0

• primarna dopustnost: g_i(x) < 0

• komplementarnost: λ_ig_i(x) = 0