Maximieren einer konvexen Funktion (Minimieren einer konkaven Funktion) mit einer linearen Einschränkung

Dabei ist , und x=[x1,x2,. . . ,xN]T≤RN×1A≤RM×$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}$
$\mathbf{A} \in \mathbb{R}^{M\times N}$

Wir können sehen, dass Die Form von und eine konvexe Funktion ist. Es kann auch gezeigt werden, dass f (.) In .$f(.)$ [$\sqrt{1+y^2}$
$[\sqrt{2}, 2]$

Dies ist ein konvexes Minimierungsproblem mit einer linearen Beschränkung.

Mit welchen Standardalgorithmen werden diese Probleme gelöst?

Ist es aufgrund der spezifischen Natur des Problems möglich, es mit einer Standardoptimierungssoftware / -paket zu lösen?

Sie können die Struktur des Problems nutzen, obwohl ich keinen vorgefertigten Löser kenne, der dies für Sie erledigt.

Im Wesentlichen suchen Sie nach einer Minimierung einer konkaven Funktion über einem konvexen Polytop (oder einem konvexen Polyeder). Eine schnelle Suche ergab einige relevante Quellen (ich erinnere mich vage, dass eine davon erwähnt wurde, als ich vor über vier Jahren einen Kurs über nichtlineare Programmierung belegte):

Falk, JE und Hoffman, KL Konkave Minimierung über kollabierende Polytope , Operations Research, 1986, Vol. 34, No. 6, p. 919-929.

Hoffman, KL Eine Methode zur globalen Minimierung konvexer Funktionen über konvexe Mengen , Mathematical Programming, 1981, Vol. 20, p. 22-31.

Benson, HP Ein endlicher Algorithmus zur konkaven Minimierung über einem Polyeder , Naval Research Logistics, 1985, Vol. 3 , No. 32, No. 1, p. 165-177.

Eine Reihe von Referenzen auf der Website von Christophe Meyer .

Es gibt mehr Quellen, wenn Sie bei Google "die konkave Funktion über dem Polytop minimieren" (oder "Polytop" durch "Polyeder" ersetzen).

Ich habe vor einigen Jahren einen Vortrag über Optimierung besucht. Damals haben wir Matlab in Kombination mit YALMIP verwendet.

Das YALMIP Wiki

Dieses Problem kann als Unterschied des Programmierproblems bei konvexen Funktionen (DC) angesehen werden. Es gibt eine umfangreiche Literatur zur DC-Programmierung, in der Sie nach verwandten Studien suchen können. Eine der bekanntesten Methoden ist die DCA-Methode, siehe zum Beispiel: http://lma.univ-pau.fr/meet/mamern09/en/Lethi-MAMERN09.pdf

Ein weiteres aktuelles Papier, das die DC-Literatur in gewissem Umfang untersucht und möglicherweise nützlich ist, ist: https://arxiv.org/pdf/1511.01796.pdf

Sie können auch eine allgemeinere Methode für nicht glatte Probleme verwenden, z. B. die in http://num.math.uni-goettingen.de/~ssabach/BST2013.pdf angegebene prox-basierte Methode

Ich würde den Frank Wolfe-Algorithmus und verwandte Methoden für Ihre Überlegung anbieten . Grundsätzlich linearisieren Sie die Zielfunktion und lösen die resultierende LP bei jeder Iteration. Ich denke jedoch, dass Sie Grenzen hinzufügen müssten , um diesen Ansatz effektiv zu machen.$x$