Fonction auto-concordante

Une fonction auto-concordante est une fonction satisfaisant une inégalité différentielle, facilitant ainsi son optimisation par la méthode de Newton^{[1]:Sec. 6.2.4.2}.  Une barrière auto-concordante est une fonction auto-concordante particulière, qui est également une fonction barrière pour un ensemble convexe particulier. Les barrières auto-concordantes sont des éléments importants des méthodes de points intérieurs pour l'optimisation.

Une définition générale est la suivante^{[2]:Def.2.0.1}. Soit C un ouvert convexe non vide de Rⁿ . Soit f une fonction trois fois continûment différentiable définie sur C. On dit que f est auto-concordante sur C si elle satisfait les propriétés suivantes:

1. Propriété de barrière : sur toute séquence de points dans C qui converge vers un point frontière de C , f converge vers l'infini.

2. . Inégalité différentielle : pour tout point x de C et toute direction h de R _n , soit g _h la fonction f restreinte à la direction h , c'est-à-dire : g _h ( t ) = f ( x + t*h ). Alors la fonction unidimensionnelle g _h doit satisfaire l'inégalité différentielle suivante :

${\displaystyle |g_{h}'''(x)|\leq 2g_{h}''(x)^{3/2}}$.

Ou d emanière équivalente^[3]:

${\displaystyle \left.{\frac {d}{d\alpha }}\nabla ^{2}f(x+\alpha y)\right|_{\alpha =0}\preceq 2{\sqrt {y^{T}\nabla ^{2}f(x)\,y}}\,\nabla ^{2}f(x)}$

• Portail des mathématiques
• Portail de l'informatique théorique