Une fonction f sur un domaine convexe est quasiconvexe si tous ses ensembles de sous-niveaux {x : f(x) ≤ alpha} sont convexes pour tout alpha ; équivalemment, f(tx + (1-t)y) ≤ max{f(x), f(y)} pour t dans [0,1].

Principe

Généralise la convexité en préservant la convexité de la géométrie des sous-niveaux plutôt que les inégalités d'interpolation linéaire ; elle capture des comportements unimodaux ou en plateau tout en conservant la structure du minimum global.

Démonstration

La fonction par morceaux f(x)=1 pour x≤0 et f(x)=x+1 pour x>0 sur R a des sous-niveaux convexes (des intervalles) et est quasiconvexe mais non convexe car elle ne satisfait pas la borne de Jensen au niveau du coude en 0.

Mauvaise application

Prétendre que la quasiconvexité implique l'applicabilité de tous les outils d'optimisation convexe (par ex. garanties de descente par sous-gradients) ; les problèmes quasiconvexes peuvent ne pas posséder les mêmes propriétés de dualité et de régularité que les problèmes convexes.

Conséquence

La quasiconvexité garantit qu'un minimum local est un minimum global sur un domaine convexe et que les méthodes par niveaux et certaines stratégies de dichotomie restent valides pour l'optimisation globale.

Inversion

Les fonctions convexes forment une sous-classe stricte : la convexité impose des bornes en combinaisons linéaires (Jensen) et des conditions d'ordre deux plus fortes ; remplacer '≤ max' par '≤ moyenne pondérée' donne la convexité.

Limite

Définie sur des domaines convexes et relative à la convexité des sous-niveaux ; n'implique pas la différentiabilité, la convexité stricte, ni l'ensemble des résultats de dualité convexe ; n'est pas équivalente à la quasiconcavité.

Tension sémantique

La tension entre quasiconvexité et convexité apparaît en conception d'algorithmes : certaines garanties de descente subsistent, mais les vitesses, formulations duales et théorèmes de séparation sont plus faibles ou absents pour les fonctions quasiconvexes.

Synthèse

Une fonction quasiconvexe est celle dont les sous-niveaux sont convexes : elle généralise la convexité en préservant la géométrie du minimum global tout en permettant un comportement ponctuel non convexe qui admet néanmoins certaines stratégies d'optimisation globale.