Výpočtové systémy - OptiSLang

Optimalizace gradientní metodou

Gradientní optimalizační metody jsou deterministické (pro stejné zadání vždy stejný výsledek). Jsou to takové metody, které jsou založené na iterativním postupu hodnot proměnných z počátečních hodnot směrem k optimálním. U optimalizace bez omezení je iterativní proces v programu OptiSLang založen na Newton-Raphsonově algoritmu kdy iterační proces lze popsat následujícím způsobem:

\( x^{(k+1)} = x^{(k)} - \sigma_k \cdot f \prime \prime \left( x^{(k)} \right) ^{-1} \cdot f \prime \left( x^{(k)} \right) \),

(1)

kde \( x^{k} \) je vektor proměnných, \( \sigma_k \) je délka kroku, \(f \) je cílová funkce, \( f \prime \) je gradient cílové funkce a \( f \prime \prime \) je Hessova matice cílové funkce. U cílové funkce s omezením je úloha přeformulovaná na řešení Lagrangeovy funkce, která je řešena pomocí algoritmů kvadratického programování. Gradientní metody jsou vhodné pro řešení skupiny problémů, kdy:

• Cílová funkce je konvexní. Pokud není, může optimalizace do-iterovat pouze do lokálního minima. Bez znalosti tvaru cílové funkce je možností optimalizaci spustit pro různé počáteční hodnoty proměněných.
• Cílová funkce je hladká. Tedy funkce je diferencovatelná (lze stanovit gradient) uvnitř stanovených mezí.
• Problém je dobře vyvážený. Tedy že malá změna hodnoty libovolné proměnné způsobí změnu hodnoty cílové funkce stejné velikosti. OptiSlang nabízí možnost zvolit váhové parametry před spuštěním optimalizace (Scaling).
• Počet proměnných je spíše malý. Náročnost optimalizace je určena použitým hardware a také náročností vyčíslení cílové funkce.
• Cílová funkce a její gradient je počítán s dostatečnou přesností.
• Zastavovací podmínka není příliš malá. Pokud optimalizace iteruje bez možnosti zlepšení výsledku, je doporučeno optimalizaci spustit s větší zastavovací podmínkou a při stejném výsledku považovat řešení za správné.
• Omezení proměnných nejsou v rozporu. V opačném případě optimalizace poběží dokud není dosaženo chyby.
• Omezení proměnných nejsou nadbytečná. Algoritmus požaduje aby gradienty aktivních omezení byly v každém kroku lineárně nezávislé.

Program OptiSlang nabízí pro řešení optimalizací gradientní metodou algoritmus sekvenčního kvadratického programování NLPQL (Nonlinear Programming using a Quadratic or Linear Least-square algorithm) a konkrétně upravený algoritmus NLPQLP (Schittkowski, 2004) ovšem bez implementace paralelních výpočtů. Dále program OptiSLang nabízí algoritmus LBFSG, který používá k aproximaci Hessovy matice BFGS aproximaci (Broyden, Fletcher, Goldfarb a Shanno) a tím urychluje výpočet optimalizace s velkým počtem proměnných (až 50 000). Tento algoritmus však nejde použít na optimalizace s nelineárními omezeními. Pro úlohy, které jsou počítány na KME (vyčíslení cílové funkce je řádově náročnější než vyčíslení Hessovy matice) je doporučeno používat algoritmus NLPQLP.

Nastavení, spuštění a průběh optimalizace je zobrazeno v animaci 1.



Řešením optimalizace je úhel \( \theta = 47,4° \).