Czym różni się programowanie geometryczne od programowania wypukłego?

10

Czym różni się (uogólnione) programowanie geometryczne od ogólnego programowania wypukłego?

Program geometryczny można przekształcić w program wypukły i zazwyczaj rozwiązuje się go metodą punktu wewnętrznego. Ale jaka jest przewaga nad bezpośrednim sformułowaniem problemu jako programu wypukłego i rozwiązaniem go metodą punktu wewnętrznego?

Czy klasa programów geometrycznych stanowi jedynie podzbiór klasy programów wypukłych, które można rozwiązać szczególnie skutecznie metodami punktów wewnętrznych? Lub zaletą jest po prostu to, że ogólny program geometryczny można łatwo określić w formie czytelnej dla komputera.

Z drugiej strony, czy istnieją programy wypukłe, których programów geometrycznych nie da się wystarczająco dobrze zbliżyć?

optimization convex-optimization

— Thomas Klimpel
źródło

5

Właściwie nigdy nie słyszałem o programowaniu geometrycznym do tego pytania. Oto artykuł przeglądowy Stephena Boyda i wsp. (Vandenberghe jest także współautorem), który jest tutorialem programowania geometrycznego.

Programy geometryczne, jak pierwotnie wyrażono, nie są wypukłe. Na przykład, jest posynomial i nie jest wypukły, aby programy geometryczne nie są ściśle podzbiór programowania wypukła. $x^{1/2}$

Zaletą przekształcania programu geometrycznego w program wypukły jest to, że oryginalny program geometryczny niekoniecznie jest wypukły. Jeśli rozwiązałeś program geometryczny jako program nieliniowy (NLP), musisz użyć metod z optymalizacji niewypukłej, aby zagwarantować globalne optymalne rozwiązanie. Metody te są droższe niż wypukłe metody optymalizacji, wymagają bardziej strojenia algorytmicznego i wymagają wstępnych domysłów.

Ponadto, jeśli użyjesz algorytmu z niewypukłego NLP, będziesz musiał określić swój możliwy zestaw jako zestaw kompaktowy w ; w programach geometrycznych jest prawidłowym ograniczeniem. $\mathbb{R}^{n}$ $x > 0$

Nie jest jasne, czy zestaw programów geometrycznych odwzorowuje (poprzez transformację logarytmiczno-wykładniczą) na zestaw programów wypukłych, który rozwiązuje się szczególnie skutecznie. Nie widzę żadnych korzyści z programowania geometrycznego poza przekształceniem w programy wypukłe.

Jeśli chodzi o twoje ostatnie pytanie, nie sądzę, aby zestaw programów geometrycznych był izomorficzny w stosunku do zestawu programów wypukłych, więc podejrzewam, że istnieją programy wypukłe, których nie można wyrazić jako programy geometryczne, a tych programów podejrzewam, że są takie, których programów geometrycznych nie można dość dobrze przybliżyć. Nie mam jednak dowodu ani kontrprzykładu.

— Geoff Oxberry
źródło

Wygląda na to, że rozdział 8 twojego artykułu przeglądowego próbuje odpowiedzieć na moje pytanie. Jednak po pierwszym pobieżnym spojrzeniu mam wrażenie, że w rzeczywistości dowolny program wypukły może być aproksymowany programem geometrycznym (oczywiście przekształconym logarytmicznie ...). Ponieważ jednak każdy program liniowy jest „oczywiście” również programem geometrycznym, może to być również wariant stwierdzenia, że dowolny program wypukły może być aproksymowany przez program liniowy, ale nie to rozumiem przez „przybliżone racjonalnie” dobrze".

— Thomas Klimpel

Kiedy pojawił się termin programowania geometrycznego, nie było łatwo rozwiązać ogólnych programów wypukłych i można było wykorzystać specjalną strukturę. Teraz, oczywiście, kiedy rozpozna się, że program jest geometryczny, przekształca go w program wypukły i rozwiązuje go przy pomocy wewnętrznych metod punktowych.

— Arnold Neumaier

3

$f(x) \leq 1$ $f(x)$ $-x-y \leq 1$ $-x-y$ $-x^2-y^2\leq 1$

— Optować
źródło

Programowanie geometryczne nie jest ścisłym podzbiorem programowania wypukłego; jednak w transformacji logarytmiczno-wykładniczej przekształcone programy geometryczne są programami wypukłymi.

— Geoff Oxberry

Tak właśnie chciałem powiedzieć. Edytowana odpowiedź dla jasności.

— Opt