Maximiser une fonction convexe (minimiser une fonction concave) avec une contrainte linéaire

où , \ mathbf {x} = [x_1, x_2, ..., x_N] ^ T \ in \ mathbb {R} ^ {N \ times 1} , et \ mathbf {A} \ in \ mathbb {R} ^ {M \ fois N}$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}$

Nous pouvons voir que $f(.)$ Est sous la forme de $\sqrt{1+y^2}$ et est une fonction convexe.
On peut également montrer que f (.) Est borné dans $[\sqrt{2}, 2]$ .

Il s'agit d'un problème de minimisation convexe avec une contrainte linéaire.

Quels sont les algorithmes standard utilisés pour résoudre ce genre de problèmes?

En utilisant la nature spécifique du problème, est-il possible de le résoudre à l'aide d'un logiciel / package d'optimisation standard?

Vous pouvez profiter de la structure du problème, bien que je ne connaisse aucun solveur préemballé qui le fera pour vous.

Essentiellement, ce que vous recherchez est de minimiser une fonction concave sur un polytope convexe (ou polyèdre convexe). Une recherche rapide a révélé quelques sources pertinentes (je me souviens vaguement que l'une d'entre elles a été mentionnée lorsque j'ai suivi un cours sur la programmation non linéaire il y a plus de quatre ans):

Falk, JE et Hoffman, KL Concave minimisation via collapsing polytopes , Operations Research, 1986, Vol. 34, n ° 6, p. 919-929.

Hoffman, KL Une méthode pour minimiser globalement les fonctions convexes sur des ensembles convexes , Programmation Mathématique, 1981, Vol. 20, p. 22-31.

Benson, HP Un algorithme fini pour la minimisation concave sur un polyèdre , Naval Research Logistics, 1985, Vol. 32, n ° 1, p. 165-177.

Un tas de références sur le site de Christophe Meyer .

Il existe d'autres sources si vous "minimisez la fonction concave sur le polytope" (ou remplacez "polytope" par "polyèdre").

J'ai assisté il y a quelques années à une conférence sur l'optimisation. À l'époque, nous utilisions Matlab en combinaison avec YALMIP.

Le Wiki YALMIP

Ce problème peut être vu comme une différence de problème de programmation des fonctions convexes (DC). Il existe une vaste littérature sur la programmation DC, vous pouvez y rechercher des études connexes. L'une des méthodes les plus connues est la méthode DCA, voir par exemple: http://lma.univ-pau.fr/meet/mamern09/en/Lethi-MAMERN09.pdf

Une autre étude récente que les enquêtes de la littérature continue dans une certaine mesure et peut - être à portée de main est: https://arxiv.org/pdf/1511.01796.pdf

Vous pouvez également utiliser une méthode plus générale pour les problèmes non lisses, par exemple la méthode basée sur un proxy donnée dans: http://num.math.uni-goettingen.de/~ssabach/BST2013.pdf

Je proposerais l' algorithme de Frank Wolfe et les méthodes connexes pour votre considération. Fondamentalement, vous linéarisez la fonction objectif et résolvez le LP résultant à chaque itération. Je pense, cependant, que vous auriez besoin d'ajouter des limites sur pour rendre cette approche efficace.$x$