Vazana optimalizace

Vázaná optimalizace: KKT podmínky

Úvod do problému

V optimalizaci se často setkáváme s úlohami, které jsou omezené nebo "vázané". To znamená, že hledáme minimum funkce pod určitými podmínkami. Tyto podmínky mohou být rovnosti nebo nerovnosti.

Standardní formulace takového vázaného optimalizačního problému je následující:

$$\begin{aligned} & \text{minimalizuj } f(x), \\ & \text{za podmínek } g(x) = 0, \\ & \text{a také } h(x) \leq 0. \end{aligned}$$

Koncept duality

Prvotní optimalizační problém

Prvotní (nebo také primární) optimalizační problém je ten původní - tedy hledání minima funkce $f(x)$ za daných omezujících podmínek.

(Langrangeova) druhotná funkce

Druhotná (nebo také duální) funkce je funkcí vytvořenou z Langrangeovy funkce, která přidává omezující podmínky k naší optimalizační funkci. Tato funkce má tvar:

$$q(\lambda, \mu) = \inf_{x \in D} L(x, \lambda, \mu),$$

kde $L(x, \lambda, \mu) = f(x) + \lambda^T g(x) + \mu^T h(x)$ je Langrangeova funkce.

Slabá dualita

Koncept slabé duality v optimalizační teorii říká, že hodnota duálního problému vždy poskytuje dolní mez pro prvotní problém. Neboli slabá dualita poskytuje dolní mez pro primární optimalizační problém z hodnoty duálního problému, což je významné pro problémy minimalizace. Vyjadřuje se jako: $$d^* \leq p^*,$$ kde $d^*$ a $p^*$ jsou optimální hodnoty duálního a primárního problému, respektive.

Silná dualita

Silná dualita rozšířuje slabou dualitu tím, že pro konvexní optimalizační problémy splňující Slaterovu podmínku, je optimální hodnota duálního problému rovna optimální hodnotě primárního problému. Matematicky: $$d^* = p^*,$$ Slaterova podmínka vyžaduje, aby existoval alespoň jeden přípustný bod $x$ s neaktivními nerovnostními neafinními podmínkami (tedy platí ostrá nerovnost).

KKT podmínky

Karushovy-Kuhnovy-Tuckerovy (KKT) podmínky jsou kritické pro řešení problémů nelineárního programování. Jsou založeny na tom, že pokud existuje optimální řešení, musí být splněny určité podmínky. KKT podmínky platí za předpokladu, že existují gradienty $∇f(x^∗)$, $∇g_i(x^∗)$ a $∇h_j (x^∗)$ a že je splněna podmínka CQ (constraint qualification).

1. Stanovištní podmínka (Stationarity): Gradient celkové funkce, včetně původní funkce a všech omezení, je v optimálním bodě nulový. Matematicky: $$\nabla_x L(x^*, \lambda^*, \mu^*) = 0$$ kde $x^*$, $\lambda^*$ a $\mu^*$ jsou optimální hodnoty proměnných a Lagrangeových multiplikátorů.

2. Komplementární nedostatečnost (Complementary slackness): Pokud je některé z nerovnostních omezení splněno rovností, pak odpovídající Lagrangeův multiplikátor musí být nenulový. $$\mu^*_j h_j(x^*) = 0, \quad j = 1, ..., p,$$ kde $h_j(x)$ jsou nerovnostní omezení a $\mu^*_j$ odpovídající Lagrangeovy multiplikátory.

3. Přípustnost duálního problému (Dual feasibility): Lagrangeovy multiplikátory pro nerovnostní omezení jsou nezáporné. $$\mu^*_j \geq 0, \quad j = 1, ..., p,$$ kde $\mu^*_j$ jsou Lagrangeovy multiplikátory pro nerovnostní omezení.

Jednou z často používaných CQ je LICQ (Linear Independence CQ): gradienty rovnostních vazeb v $x^∗$ a aktivních nerovnostních vazeb v $x^∗$ jsou lineárně nezávislé. Označujeme to jako LICQ($x^∗$). Existují také další rafinovanější CQ, které mohou být použity.

Vázaná optimalizace: penalizační metody

Úvod

Penalizační metody jsou výpočetní techniky používané v optimalizačních problémech, kde se omezení nahrazují tresty za jejich porušení. Základní myšlenka spočívá v následujícím:

1. Nahrazujeme optimalizovanou funkci jinou funkcí, která se skládá z původní funkce $f(x)$
2. Dodatečný penalizační člen za každou vazbu. Tento penalizační člen bude nulový, pokud je splněna vazební podmínka, a jinak bude kladný.

Často se používá také posloupnost penalizačních členů, jejichž hodnota roste a více nutí metodu hledat přípustné řešení.

Kvadratická penalizace

Optimalizujeme funkci $Q(x, \nu)$, která je definována jako: $$Q(x, \nu) = f(x) + \frac{\nu}{2} \sum_{i} g_i^2(x) + \frac{\nu}{2} \sum_{j} ([h_j(x)]^+)^2,$$ kde $[y]^+ = \max\{y, 0\}$.

( Mezi přechodem z $0$ na $y$ je tam zlom tedy není spojitě diferencovatelná )

Kvadratická penalizace je vhodnější pro rovnostní omezení, protože pokud máme nerovnostní omezení, $Q$ často není spojitě diferencovatelná.

ℓ1 penalizace

Původní funkci nahrazujeme ℓ1 penalizační funkcí: $$\varphi_1(x, \nu) = f(x) + \nu \sum_i |g_i(x)| + \nu \sum_j [h_j(x)]^+.$$ Stejně jako u kvadratické penalizace, ani tato funkce obecně není spojitě diferencovatelná. Pokud je však $x^* \in M$ bodem ostrého minima vzhledem k $M$ a splňuje KKT podmínky, pak je i bodem minima funkce $\varphi_1(x, \nu)$ pro všechna $\nu > \nu^*$, kde $$\nu^* = \|\lambda^*, \mu^*\|_\infty = \max\{|\lambda_i|, |\mu_j|\}$$ V praxi se pro řešení často nahrazuje nehladká funkce $\varphi_1$ nějakou hladkou (kvadratickou) aproximací.

Algoritmus

Penalizační metody se používají pro řešení optimalizačních problémů s omezeními. Následující je přehledné znázornění kroků tohoto algoritmu:

1. Inicializace: Zvolíme počáteční hodnotu penalizačního parametru $\nu_0 > 0$. Dále zvolíme nezápornou posloupnost $\nu_k$, která konverguje k nule, tj. $\nu_k \rightarrow 0$. Tato posloupnost nám pomůže určit, kdy máme ukončit optimalizaci penalizované funkce v každém kroku.

2. Iterace: Pro každé $k = 0, 1, 2, ...$ provádíme následující kroky:

   1. Optimalizace penalizované funkce: V tomto kroku hledáme přibližný bod minima $x_k$ funkce $Q(x, \nu_k)$. Tuto optimalizaci ukončíme, když norma gradientu penalizované funkce v bodě $x_k$ je menší nebo rovna $\nu_k$, tj. $\|\nabla_xQ(x_k, \nu_k)\| \leq \nu_k$. Přibližný bod minima $x_k$ je poté použit jako aktuální řešení optimalizačního problému.
   2. Kontrola konvergence: Pokud je splněna finální podmínka konvergence (specifická pro konkrétní problém a metodu), ukončíme celý algoritmus a vrátíme aktuální řešení $x_k$.
   3. Aktualizace penalizačního parametru: Nastavíme nový penalizační parametr $\nu_{k+1}$ tak, aby byl větší než aktuální penalizační parametr $\nu_k$ : $\nu_{k+1} > \nu_k$.

Tento proces se opakuje, dokud není dosaženo konvergence. Výsledkem je řešení, které minimalizuje původní optimalizační problém s omezeními, respektive s tresty za jejich porušení.

Pokud je $x_k$ přesným bodem minima $Q(x, \nu_k)$ a $\nu_k \rightarrow +\infty$, pak každý hromadný bod ${x_k}$ je globálním přípustným řešením. V praxi však často nelze podúlohy přesně řešit, a proto tato metoda může konvergovat i k nepřípustným bodům (nebo jiným bodům splňujícím KKT podmínky).

Metoda vnitřního bodu

Metoda vnitřního bodu je optimalizační technika zaměřená na problémy s nerovnostními omezeními. Penalizace je provedena pomocí logaritmu, což vede k tomu, že původní omezení $h(x) \leq 0$ je transformováno na $h(x) < 0$.

Původní funkci nahrazujeme funkcí:

$$B(x, \nu) = f(x) - \nu \sum_{j=1}^{m} log(-h_j(x))$$ Aktualizace $x_{k+1} = x_k + p_k$ se dělá krokem v Newtonově metodě

Moderní metody vnitřního bodu (bariérové metody)

Moderní metody vnitřního bodu, také známé jako bariérové metody, jsou pokročilejším rozšířením klasické metody vnitřního bodu. Tyto metody transformují původní problém tak, že nerovnostní vazby jsou převedeny na rovnostní pomocí tzv. doplňkových proměnných, známých jako "slack variables".