Maksymalizowanie funkcji wypukłej (minimalizowanie funkcji wklęsłej) z wiązaniem liniowym

Problem jest

gdzie $f(\mathbf{x}) = \sum_{i=1}^N\sqrt{1+\frac{x_i^4}{(\sum_{i=1}^{N}x_i^2)^2}}$ ,
$\mathbf{x} = [x_1,x_2,...,x_N]^T \in \mathbb{R}^{N\times 1}$ i
$\mathbf{A} \in \mathbb{R}^{M\times N}$

Widzimy, że f (.) Ma$f(.)$ postać $\sqrt{1+y^2}$ i jest funkcją wypukłą.
Można również wykazać, że f (.) Jest ograniczone w $[\sqrt{2}, 2]$ .

Jest to wypukły problem minimalizacji z ograniczeniem liniowym.

Jakie są standardowe algorytmy stosowane do rozwiązywania tego rodzaju problemów?

Czy korzystając ze specyfiki problemu można go rozwiązać za pomocą dowolnego standardowego oprogramowania / pakietu optymalizacyjnego?

Możesz skorzystać ze struktury problemu, choć nie znam gotowego solvera, który by to zrobił.

Zasadniczo to, czego szukasz, to zminimalizowanie funkcji wklęsłej nad wypukłym polytopem (lub wypukłym wielościanem). Szybkie wyszukiwanie wyciągnęło kilka istotnych źródeł (niejasno pamiętam jedno z nich wspomniane, gdy cztery lata temu wziąłem udział w zajęciach z programowania nieliniowego):

Falk, JE i Hoffman, Minimalizacja wklęsłości KL poprzez zapadające się polytopy , Operations Research, 1986, tom. 34, nr 6, s. 1 919–929.

Hoffman, KL Metoda globalnego minimalizowania funkcji wypukłych w zestawach wypukłych , Mathematical Programming, 1981, t. 20, p. 22–31.

Benson, HP Skończony algorytm minimalizacji wklęsłej nad wielościanem , Naval Research Logistics, 1985, t. 32, nr 1, s. 1 165-177.

Kilka referencji na stronie internetowej Christophe Meyera .

Istnieje więcej źródeł, jeśli Google „zminimalizuje funkcję wklęsłą nad wielopisem” (lub zastąpi „polytop” „wielościanem”).

Brałem udział kilka lat temu w wykładzie na temat optymalizacji. Wtedy używaliśmy Matlaba w połączeniu z YALMIP.

Wiki YALMIP

Problem ten można postrzegać jako różnicę w problemie programowania funkcji wypukłych (DC). Istnieje obszerna literatura na temat programowania DC, można tam przeszukiwać pokrewne badania. Jedną z najbardziej znanych metod jest metoda DCA, patrz na przykład: http://lma.univ-pau.fr/meet/mamern09/en/Lethi-MAMERN09.pdf

Kolejny najnowszy artykuł, który do pewnego stopnia analizuje literaturę DC i może być przydatny, to: https://arxiv.org/pdf/1511.01796.pdf

Możesz także zastosować bardziej ogólną metodę rozwiązywania problemów nieszablonowych, na przykład metodę opartą na proxy podaną w: http://num.math.uni-goettingen.de/~ssabach/BST2013.pdf

Proponuję do rozważenia algorytm Franka Wolfe'a i powiązane metody. Zasadniczo linearyzujesz funkcję celu i rozwiązujesz wynikowy LP przy każdej iteracji. Myślę jednak, że trzeba by dodać granice aby to podejście było skuteczne.$x$