Search
\[ \def\_#1{\mathbf{#1}} \def\x{\times} \def\R{\mathbb{R}} \def\mat#1{\begin{bmatrix}#1\end{bmatrix}} \def\matr#1{\begin{bmatrix*}[r]#1\end{bmatrix*}} \]
(T.Werner, 2021)
Máme $n$ koulí, které na sebe působí přitažlivou silou, ubývající se čtvercem vzdálenosti, tedy potenciální energie dvojice koulí je nepřímo úměrná jejich vzdálenosti (prostě jako gravitace). Koule se nemohou pronikat, tedy středy dvou koulí s poloměry $r_1,r_2$ nemohou být blíže než $r_1+r_2$. Chceme najít stav tohoto systému s nejmenší potenciální energií.
Tohle je minimalizace nekonvexní funkce na složité nekonvexní množině, která je asi velmi obtížná. Proto uděláme aproximaci. Dvě koule na sebe působí součtem dvou sil: jedna je přitažlivá jako výše, druhá je ve velké vzdálenosti zanedbatelná, ale když se vzdálenost středu koulí blíží $r_1+r_2$, tak rychle roste (je to tedy jakási bariérová funkce). Tím úlohu převedeme na úlohu bez omezení.
Potenciální energii dvojice koulí se středy $\_x_1,\_x_2$ a poloměry $r_1,r_2$ modelujeme funkcí \[ E(t) = \frac1{(bt)^k} - \frac1t \] kde \[ t=\|\_x_1-\_x_2\|-(r_1+r_2) \] je vzdálenost koulí bez poloměrů. Pro $t\le0$ definujeme $E(t)=+\infty$. Parametry $b>0$ a $k\ge2$ řídí strmost bariérové funkce.
Potenciální energie $E(\_x_1,\dots,\_x_n)$ systému všech koulí je součet těchto párových energií pro všechny dvojice různých koulí. Pro gradientní metodu je třeba najít její gradient, což je hezké cvičení na derivace složených funkcí.
Zkoušel jsem to předběžně naprogramovat v Matlabu gradientní metodou s hloupou heuristikou na volbu kroku, kód je zde. Chodí to, ale konverguje pomalu.
Úlohu lze modifikovat spoustou způsobů: