Fonction quasi-convexe

En mathématiques, une fonction quasi-convexe est une fonction à valeurs réelles, définie sur un ensemble convexe d'un espace vectoriel réel, telle que l'image réciproque de tout ensemble de la forme est convexe ou encore telle que, sur tout segment, la plus grande valeur de la fonction est atteinte à l'une des extrémités. L'opposée d'une fonction quasi-convexe est dite quasi-concave.

Une fonction « décroissante puis croissante » donc quasi-convexe, mais non convexe.
De même, la densité de probabilité de la loi normale est quasi-concave mais non concave.
Une fonction non quasi-convexe : l'ensemble des points pour lesquels les valeurs de la fonction sont sous les pointillés rouges est l'union des deux intervalles rouges, qui n'est pas convexe.

Toute fonction convexe est quasi-convexe mais la réciproque est fausse : par exemple, toute fonction monotone sur un intervalle réel est quasi-linéaire, c'est-à-dire à la fois quasi-convexe et quasi-concave.

Définition

Une fonction définie sur une partie convexe C d'un espace vectoriel réel E est dite :

  • quasi-convexe si pour tout réel , l'ensemble de sous-niveau est convexe ou, ce qui est équivalent, si
     ;
  • strictement quasi-convexe si l'on a même :
     ;
  • quasi-concave si son opposée est quasi-convexe, c'est-à-dire si
     ;
  • strictement quasi-concave si son opposée est strictement quasi-convexe, c'est-à-dire si
    .
  • quasi-linéaire[1],[2] (ou quasi-monotone[3]) si elle est à la fois quasi-convexe et quasi-concave.

Propriétés

Toute forme linéaire est quasi-linéaire.

Une fonction monotone est quasi-linéaire, c'est-à-dire à la fois quasi-convexe et quasi-concave.
En plus d'être monotone, cette fonction est strictement concave.

Une fonction définie sur un intervalle est quasi-convexe si et seulement si elle est monotone ou « décroissante puis croissante », c'est-à-dire s'il existe dans deux intervalles complémentaires (l'un des deux pouvant être vide) tels que soit décroissante sur et croissante sur [4]. De même, est quasi-concave si et seulement si elle est monotone ou « croissante puis décroissante »[5]. Elle est donc quasi-linéaire si et seulement si elle est monotone.

Si une fonction possédant un maximum global en un point m du convexe est quasi-concave alors elle est unimodale (en), c'est-à-dire croissante le long de tout segment orienté aboutissant en m. La réciproque est vraie si (d'après la caractérisation précédente de la quasi-concavité dans ce cas), mais on construit facilement sur une fonction unimodale et non quasi-concave[6].

Intérêt de la notion

En optimisation, les problèmes avec des fonctions objectif quasi-convexes peuvent se résoudre avec les mêmes méthodes que les fonctions objectif convexes. En particulier, dans le cas de problèmes non contraints ou avec un ensemble admissible convexe, tout minimum local est un minimum global, sauf si la fonction est constante au voisinage de ce point[7]. Les algorithmes de descente peuvent être « piégés » par un tel « plateau horizontal ».

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Quasiconvex function » (voir la liste des auteurs).
  1. (en) Stephen Boyd et Lieven Vandenberghe, chap. 3.4 « Quasiconvex functions », dans Convex Optimization, Cambridge Press University, , 730 p. (ISBN 978-0-521-83378-3, lire en ligne), p. 95.
  2. (en) S. A. R. Al-Mezel, F. R. M. Al-Solamy et Q. H. Ansari, Fixed Point Theory, Variational Analysis, and Optimization, CRC Press, (lire en ligne), p. 148.
  3. (en) Harvey J. Greenberg et W. P. Pierskalla, « A review of quasi-convex functions », Operations Research, vol. 19, no 7, , p. 1553-1570 (lire en ligne) : Definition 4 p. 1555.
  4. Exercice corrigé du chapitre « Convexité » de la leçon sur les fonctions d'une variable réelle sur Wikiversité.
  5. (en) Josef Stoer (en) et Christoph Witzgall, Convexity and Optimization in Finite Dimensions, vol. I, coll. « Grund. math. Wiss. » (no 163), (lire en ligne), p. 172, th. 4.9.11.
  6. (en) « How to prove quasi-convex if and only if unimodal? », sur math.stackexchange.com, .
  7. Greenberg et Pierskalla 1971 : Table II p. 1560, 11.b.

Voir aussi

Bibliographie

  • (en) Mordecai Avriel, Walter E. Diewert (en), Siegfried Schaible et Israel Zang, Generalized Concavity, SIAM, coll. « Classics in Applied Mathematics » (no 63), (1re éd. 1988) (lire en ligne), chap. 3
  • (en) Ivan Singer, Abstract Convex Analysis, Canadian Mathematical Society Series of Monographs and Advanced Texts, John Wiley & Sons, New York, 1997. xxii+491 pp.  (ISBN 0-471-16015-6)
  • (en) Maurice Sion, « On general minimax theorems », Pacific J. Math., vol. 8, , p. 171-176 (lire en ligne)

Liens externes

  • Portail de l'analyse
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.