Fonction semi-lisse

En analyse mathématique, la semi-lissité d'une fonction est un concept de différentiabilité plus faible que celui de Fréchet, qui permet toutefois d'assurer la convergence locale de l'algorithme de Newton lorsque l'opérateur dérivée est remplacé par un élément inversible du différentiel de Clarke. L'algorithme correspondant est connu sous le nom de méthode de Newton semi-lisse.

La semi-lissité est stable pour beaucoup d'opérations habituelles (addition, produit scalaire, composition, ...) mais aussi pour la prise de minimum et de maximum, ce qui rend cette propriété attractive dans beaucoup de problèmes.

Définitions

Soient $𝔼$ et $𝔽$ deux espaces vectoriels réels de dimension finie, $\mathrm{\Omega }$ un ouvert de $𝔼$ et $F:\mathrm{\Omega }\to 𝔽$ une fonction non lisse (c'est-à-dire non différentiable au sens de Fréchet), mais toutefois localement lipschitzienne sur $\mathrm{\Omega }$ et donc avec un différentiel de Clarke non vide aux points de $\mathrm{\Omega }$. On note ce dernier en $x$ par ${\partial }_{C}F(x)$.

Motivation

Les définitions sont motivées par le souhait de faire converger plus ou moins rapidement la suite générée par une version adaptée de l'algorithme de Newton pour trouver une zéro $x_{*}$ du système d'équations non lisses Modèle:Centrer La version généralisée de l'algorithme de Newton que l'on considère, appelée méthode de Newton semi-lisse, s'écrit Modèle:Centrer où $J_k$ est une jacobienne inversible de ${\partial }_{C}F(x_k)$, qui est supposée exister.

On cherche à faire converger les itérés $x_k$ en se fondant sur le calcul suivant : Modèle:Centrer où l'on a noté $h_k:=x_k-x_{*}$. Dès lors, si $\{J_k^{-1}\}$ est bornée et si Modèle:Centrer la convergence superlinéaire de la suite $\{x_k\}$ est assurée. C'est précisément cette dernière estimation qui est requise dans la définition de la semi-lissité. On remarquera bien que $J_k$ est une jacobienne généralisée en $x_{*}+h_k$, et pas en $x_{*}$, comme on pourrait être tenté de l'imposer en s'inspirant de la Fréchet-différentiabilité.

Semi-lissité

La définition de la semi-lissité requiert un peu plus que l'estimation de $F(x_{*}+h_k)-F(x_{*})-Jh$ donnée dans la section «Motivation», car on souhaite que cette propriété puisse se conserver après diverses opérations.

Quelques remarques.

• La lipschitziannité de $F$ dans le voisinage de $x$ assure que le différentiel de Clarke ${\partial }_{C}F(x)$ est non vide et compact. On peut donc l'utiliser dans la suite de la définition.
• L'existence de dérivées directionnelles est demandée pour assurer de bonnes propriétés à la notion de dérivabilité semi-lisse.
• Comme annoncé dans la section «Motivation», dans l'estimation de $F(x+h)-F(x)-Jh$, les jacobiennes $J$ sont prises dans le différentiel en $x+h$, pas en $x$.

La notion de semi-lissité a été introduite par Mifflin (1977) pour les fonctions à valeurs scalaires et étendue aux fonctions à valeurs vectorielles par Qi et Sun (1993).

Propriétés

Propriétés générales

Une fonction de classe $C^1$ est semi-lisse.

Une fonction convexe est aussi semi-lisse.

Dans la proposition ci-dessous, on dit que $F:\mathrm{\Omega }\to 𝔽$ est semi-lisse par morceaux en $x\in \mathrm{\Omega }$, s'il existe un voisinage $V$ de $x$ et des fonctions semi-lisses $F_i:V\to 𝔽$, pour $i\in I$ avec $|I|$ est fini, tels que :

• $F$ est continue sur $V$,
• pour tout $x^{\prime }\in V$, il existe un indice $i\in I$ tel que $F(x^{\prime })=F_i(x^{\prime })$.

Lorsque les morceaux sont affines, on dit que la fonction est affine par morceaux en $x$.

On peut aussi obtenir la semi-lissité d'une fonction à valeurs vectorielles si ses composantes sont semi-lisses.

La semi-lissité est stable par composition.

Aspects calculatoires

Un atout important de la semi-lissité est de se conserver par prise de minimum et de maximum de fonctions, ce qui n'est pas le cas de la Fréchet-différentiabilité !

Exemples

• Les normes $\Vert \cdot {\Vert }_p$ pour $1⩽p⩽\mathrm{\infty }$ sont fortement semi-lisses en tout point.
• La C-fonction $\text{min}:(a,b)\in {ℝ}^2\mapsto \min (a,b)\in ℝ$ est fortement semi-lisse en tout point.
• La C-fonction de Fischer-Burmeister $(a,b)\in {ℝ}^2\mapsto \sqrt{a^2+b^2}-(a+b)\in ℝ$ est fortement semi-lisse en tout point.
• Le projecteur sur un convexe défini par des contraintes convexes de classe $C^2$ est fortement semi-lisse en un point du convexe satisfaisant la qualification (QC-IL) (et plus généralement la qualification de rang constant).

Annexes

Articles connexes

• Algorithme de Newton semi-lisse
• Différentiel généralisé

Références

• Modèle:En F. Facchinei, J.-S. Pang (2003). Finite-Dimensional Variational Inequalities and Complementarity Problems (deux volumes). Springer Series in Operations Research. Springer.
• Modèle:En A.F. Izmailov, M.V. Solodov (2014). Newton-Type Methods for Optimization and Variational Problems, Springer Series in Operations Research and Financial Engineering, Springer.
• Modèle:En R. Mifflin (1977). Semismooth and semiconvex functions in constrained optimization. SIAM Journal on Control and Optimization, 15, 959–972.
• Modèle:En L. Qi, J. Sun (1993). A nonsmooth version of Newton’s method. Mathematical Programming, 58, 353–367.