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.