(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ů:

• Lz si hrát s volbou délky kroku u GD (fixed step, diminishing step, backtracking line search).
• Lze si hrát s bariérovou funkcí. Alternativou k uvedené bariéře je logaritmická bariéra $-\log(bt)$.
• Chodilo mi to dobře s parametry $k=3$ a $b=1$, přičemž koule měly jednotkové poloměry a byly v počátečních vzdálenostech (náhodně generovaných) řádově nekolik jednotek. Nabízí se po zkonvergování tyto parametry utáhnout, tj. zvětšit strmost bariéry.
• Lze mezi studenty vyhlásit soutěž, kdo dosáhne menší energie a za jak dlouho.
• Konverguje to pomalu, pro trochu strmější bariéru a nevhodnou počáteční konfiguraci vůbec. Nabízí se zkusit kombinovat gradientní metodu s minimalizací po blocích souřadnic (kde jeden blok je střed jedné koule).
• Po konvergenci systém typicky vytvoří hezkou nějak symetrickou konfiguraci s lokálně nejmenší energií. Je možno zkoumat lokální minima.
• Je možno dát koulím náboje, takže některé dvojice se budou přitahovat a jiné odpuzovat.
• Je možné udělat z koulí magnetické dipóly, jako ve známé hračce Neocube (spousta neodymových magnetů tvaru kuliček).
• Je možné to dělat ve 3-D prostoru (to by se hůř vizualizovalo).