Penalizačná a Barierová metóda

Penalizačná metóda

Metódu penalizačnej funkcie navrhol Carrol a neskôr ju podrobnejšie spracoval Fiacco a McCormick. Za základnú myšlienku môžeme považovať nahradenie úlohy na viazaný extrém postupnosťou úloh na voľný extrém. Dôvodom je, že takýto prístup je menej algoritmicky náročný. V každej takejto iterácii sa bude riešiť pomocná úloha na voľný extrém, ktorý bude závislý od parametra. Postupnosť takýchto riešení bude následne konvergovať k optimálnemu riešeniu pôvodnej úlohy. Nakoľko sa účelová funkcia dvoch po sebe riešených úloh líši len minimálne, tak riešenie získané v \(k\) - tej iterácii  je dobrým odhadom pre riešenie, ktoré získame v \(k+1\) - iterácii. Penalizačná metóda je určená pre úlohy typu  \(\min \{f(x):x\in M\},\)  kde \(M\subseteq\Omega\subseteq \mathbf{R}^n\) a \(M\) je uzavretá a \(\Omega\) je otvorená množina. Je to všeobecnejší postup pre optimalizačné úlohy, ktorý je možné modifikovať aj pre úlohy \(\hbox{LP}\).

Zavedieme penalizačnú funkciu \(\Psi: \Omega\to \mathbf{R}^{+}_0\), ktorá spĺňa podmienku \(\Psi(x)=0\) pre \(x\in M\) a rastie zo vzdialenosťou od množiny \(M\). Cieľom úlohy je stanoviť \[\min\{f(x)+\mu \,\Psi(x):x\in \Omega\},\] t.j. k účelovej funkcii pridáme funkciu, ktorá bude penalizovať porušenie každého ohraničenia. Ak máme ohraničenie  \(h(x)=0\), tak penále je v tvare \(\mu\, h^2(x)\). V prípade ohraničenia \(g(x)\leq 0\) je  penále  v tvare \(\mu\,\max\{0,g(x)\}\). Teda v prípade takéhoto prístupu by bolo kritérium pre \(p\in \mathbf{N}\), zvyčajne pre \(p=2\), v tvare \[\sigma(x)=\sum_{i=1}^m \left[\max\{0,g_i(x)\}\right]^p+\sum_{i=1}^n\vert h_k(x)\vert^p.\]

Myšlienku  algoritmu:

• Krok 1: Zvolí­me test ukončenia \(\varepsilon>0\), index \(k=1\),  východiskový bod \(x^k\), východiskový penalizačný parameter \(\mu^{k}\) a koeficient zmeny penalizačného parametra \(b\).
• Krok 2: Pre východiskový bod \(x^k\) vyriešime úlohu \(F(x)=f(x)+\mu^k.\sigma(x)\). Jej vyriešením zí­skame bod \(x^{\mu^ k}\) a položíme \(x^{k+1}=x^{\mu^k}\).
• Krok 3: Ak \(\mu^k\sigma(x)\lt\varepsilon\), tak koniec algoritmu. Inak \(\mu_{k+1}=b.\mu^k\),  \(k=k+1\) a pokračujeme Krokom 2.

Barierová metóda

Barierová metóda je určená pre úlohy typu \(\min \{f(x):x\in M\}\), kde \(M\subseteq \mathbf{R}^n\) a \(M\) je uzavretá množina, pre ktorú platí  \(\hbox{uzáver} (int(M))=M\). Vhodnou barierovou funkciou \(\Theta: M\to \mathbf{R}^{+}_0\) je funkcia, ktorá spĺňa podmienku \(\Theta(x)=+\infty\) pre \(x\in \sigma(M)\) a rastie tým viac, čí­m bližšie je k hranici  množiny \(M\). Princí­p barierových funkcií­ teda spočí­va v tom, že sa vytvorí­ pomocná funkcia, ktorá má mimo oblasť a tiež na hranici veľmi veľké hodnoty. A tak pri približovaní sa k hranici oblasti, hodnota pomocnej funckie neohraničene narastá.  Metóda si vyžaduje, aby množina prí­pustných riešení úlohy nemala prázdne vnútro a preto je vhodná pre nerovnosti \(g_j(x)\leq 0\) a nie pre úlohy s rovnicami. Typickým tvarom barierovej funckie je \[B(x)=-\sum_{j=1}^{n}\frac{1}{g_j(x)} \quad\hbox{a}\quad B(x)=-\sum_{j=1}^{n}\log (g_j(x)).\]Skutočné riešenia častokrát zvyknú ležať na hranici oblasti pokiaľ je niektorá z ohraničení aktí­vne. Nato, aby sme sa dosiahli riešenie, budeme  riešiť postupnosť úlloh, pri ktorej sa bude bariéra postupne znižovať.

Myšlienku  algoritmu:

• Krok 1: Pre \(\varepsilon>0\), \(x^1\in int(M)\) ľubovoľné,  \(0<\beta<1\) a \(k=1\).
• Krok 2: Nájdeme \(x^{k+1}\) optimálne riešenie úlohy \[ \min\{f(x)+v_j\,\Theta(x):x\in int(M)\}.\]
• Krok 3: Ak \(v_j\,\Theta(x^{k+1})\lt\varepsilon\), tak koniec algoritmu. Inak \(v_{k+1}=\beta v_j\) a \(k=k+1\) a pokračujeme Krokom 2.