Méthode des points intérieurs

${\displaystyle O(n^{3,5}L) </span referrerpolicy=$ Les opérations sur les nombres de L bits (où n est le nombre de variables et de constantes) sont également très efficaces en pratique. L'article de Karmarkar a suscité un vif intérêt pour les méthodes de points intérieurs. Deux ans plus tard, James Renegar a inventé la première méthode de points intérieurs de suivi de chemin , avec un temps d'exécution de ${\displaystyle O(n^{3}L) <semantics><mrow><mstyle><mi>O</mi><mo>(</mo><msup><mi>n</mi><mrow><mn>3</mn></mrow></msup><mi>L</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle O(n^{3}L)}</annotation></semantics></math><img src=$

Tout problème d'optimisation convexe peut être transformé en minimisation (ou maximisation) d'une fonction linéaire sur un ensemble convexe par conversion sous forme d'épigraphe . L'idée d'encoder l' ensemble admissible à l'aide d'une barrière et de concevoir des méthodes de barrière a été étudiée par Anthony V. Fiacco, Garth P. McCormick et d'autres au début des années 1960. Ces idées ont été principalement développées pour la programmation non linéaire générale , mais elles ont été abandonnées par la suite en raison de l'existence de méthodes plus performantes pour cette classe de problèmes (par exemple, la programmation quadratique séquentielle ).

Yurii Nesterov et Arkadi Nemirovski ont proposé une classe particulière de barrières permettant d'encoder tout ensemble convexe. Ils garantissent que le nombre d' itérations de l'algorithme est borné par un polynôme en fonction de la dimension et de la précision de la solution.

La classe des méthodes primales-duales de suivi de chemin par points intérieurs est considérée comme la plus performante. L'algorithme prédicteur-correcteur de Mehrotra constitue la base de la plupart des implémentations de cette classe de méthodes.

Définitions

On nous donne un programme convexe de la forme : ${\displaystyle {\begin{aligned}{\underset {x\in \mathbb {R} ^{n}}{ ext{minimize}}}\quad &f(x)\\{ ext{subject to}}\quad &x\in G.\end{aligned <semantics><mrow><mstyle><mrow><mtable><mtr><mtd><mrow><munder><mtext>minimiser</mtext><mrow><mi>x</mi><mo>∈</mo><msup><mrow><mi>R</mi></mrow><mrow><mi>n</mi></mrow></msup></mrow></munder></mrow><mspace></mspace></mtd><mtd><mi>f</mi><mo>(</mo><mi>x</mi><mo>)</mo></mtd></mtr><mtr><mtd><mrow><mtext>sous réserve de</mtext></mrow><mspace></mspace></mtd><mtd><mi>x</mi><mo>∈</mo><mi>G</mi><mo>.</mo></mtd></mtr></mtable></mrow></mstyle></mrow><annotation>{\displaystyle {\begin{aligned}{\underset {x\in \mathbb {R} ^{n}}{ ext{minimiser}}}\quad &f(x)\\{ ext{sous la contrainte}}\quad &x\in G.\end{aligned}}}</annotation></semantics></math><img src=$ f est une fonction linéaire . Habituellement, l'ensemble convexe G est représenté par un ensemble d'inégalités convexes et d'égalités linéaires ; les égalités linéaires peuvent être éliminées à l'aide de l'algèbre linéaire , donc par souci de simplicité, on suppose qu'il n'y a que des inégalités convexes, et le programme peut être décrit comme suit, où les g _i sont des fonctions convexes : ${\displaystyle {\begin{aligned}{\underset {x\in \mathbb {R} ^{n}}{ ext{minimize}}}\quad &f(x)\\{ ext{subject to}}\quad &g_{i}(x)\leq 0{ ext{ for }}i=1,\dots ,m.\\\end{aligned <semantics><mrow><mstyle><mrow><mtable><mtr><mtd><mrow><munder><mtext>minimiser</mtext><mrow><mi>x</mi><mo>∈</mo><msup><mrow><mi>R</mi></mrow><mrow><mi>n</mi></mrow></msup></mrow></munder></mrow><mspace></mspace></mtd><mtd><mi>f</mi><mo>(</mo><mi>x</mi><mo>)</mo></mtd></mtr><mtr><mtd><mrow><mtext>sous réserve de</mtext></mrow><mspace></mspace></mtd><mtd><msub><mi>g</mi><mrow><mi>je</mi></mrow></msub><mo>(</mo><mi>x</mi><mo>)</mo><mo>≤</mo><mn>0</mn><mrow><mtext> pour </mtext></mrow><mi>je</mi><mo>=</mo><mn>1</mn><mo>,</mo><mo>…</mo><mo>,</mo><mi>m</mi><mo>.</mo></mtd></mtr></mtable></mrow></mstyle></mrow><annotation>{\displaystyle {\begin{aligned}{\underset {x\in \mathbb {R} ^{n}}{ ext{minimiser}}}\quad &f(x)\\{ ext{sous la contrainte}}\quad &g_{i}(x)\leq 0{ ext{ pour }}i=1,\dots ,m.\\\end{aligned}}}</annotation></semantics></math><img src=$ vecteur fini de coefficients (par exemple, les coefficients des fonctions quadratiques). La dimension de ce vecteur de coefficients est appelée la taille du programme. Un solveur numérique pour une famille de programmes donnée est un algorithme qui, étant donné le vecteur de coefficients, génère une suite de solutions approchées x _t pour t = 1, 2, ..., en utilisant un nombre fini d'opérations arithmétiques. Un solveur numérique est dit convergent si, pour tout programme de la famille et tout ε > 0 positif, il existe un T (qui peut dépendre du programme et de ε ) tel que, pour tout t > T , la solution approchée x _t est ε-approximative, c'est-à-dire : ${\displaystyle {\begin{aligned}&f(x_{t})-f^{*}\leq \epsilon ,\\&g_{i}(x_{t})\leq \epsilon \quad { ext{for}}\quad i=1,\dots ,m,\\&x\in G,\end{aligned <semantics><mrow><mstyle><mrow><mtable><mtr><mtd></mtd><mtd><mi>f</mi><mo>(</mo><msub><mi>x</mi><mrow><mi>t</mi></mrow></msub><mo>)</mo><mo>−</mo><msup><mi>f</mi><mrow><mo>∗</mo></mrow></msup><mo>≤</mo><mi>ϵ</mi><mo>,</mo></mtd></mtr><mtr><mtd></mtd><mtd><msub><mi>g</mi><mrow><mi>je</mi></mrow></msub><mo>(</mo><msub><mi>x</mi><mrow><mi>t</mi></mrow></msub><mo>)</mo><mo>≤</mo><mi>ϵ</mi><mspace></mspace><mrow><mtext>pour</mtext></mrow><mspace></mspace><mi>je</mi><mo>=</mo><mn>1</mn><mo>,</mo><mo>…</mo><mo>,</mo><mi>m</mi><mo>,</mo></mtd></mtr><mtr><mtd></mtd><mtd><mi>x</mi><mo>∈</mo><mi>G</mi><mo>,</mo></mtd></mtr></mtable></mrow></mstyle></mrow><annotation>{\displaystyle {\begin{aligned}&f(x_{t})-f^{*}\leq \epsilon ,\\&g_{i}(x_{t})\leq \epsilon \quad { ext{pour}}\quad i=1,\dots ,m,\\&x\in G,\end{aligned}}}</annotation></semantics></math><img src=$ ${\displaystyle f^{* <semantics><mrow><mstyle><msup><mi>f</mi><mrow><mo>∗</mo></mrow></msup></mstyle></mrow><annotation>{\displaystyle f^{*}}</annotation></semantics></math><img src=$ polynomial si le nombre total d'opérations arithmétiques dans les T premières étapes est au plus égal à

poly(taille-problème) * log( V / ε ),

où V est une constante dépendant des données, par exemple la différence entre la plus grande et la plus petite valeur de l'ensemble des solutions admissibles. Autrement dit, V / ε représente la « précision relative » de la solution, c'est-à-dire la précision par rapport au coefficient le plus élevé. log( V / ε ) représente le nombre de « chiffres de précision ». Par conséquent, un solveur est dit « polynomial » si chaque chiffre de précision supplémentaire requiert un nombre d'opérations polynomial en fonction de la taille du problème.

Types

Les méthodes de points intérieurs comprennent notamment :

Méthodes de réduction potentielles : l'algorithme de Karmarkar fut le premier.
Méthodes de suivi de chemin : les algorithmes de James Renegar et Clovis Gonzaga ont été les premiers.
Méthodes primales-duales .

Méthodes de suivi de chemin

Idée

Étant donné un programme d'optimisation convexe (P) avec contraintes, on peut le convertir en un programme sans contraintes en ajoutant une fonction barrière . Plus précisément, soit b une fonction convexe lisse, définie à l'intérieur de la région admissible G , telle que pour toute séquence ${\displaystyle \{x_{j}\in { extbf {G}}\ <semantics><mrow><mstyle><mo>{</mo><msub><mi>x</mi><mrow><mi>j</mi></mrow></msub><mo>∈</mo><mrow><mrow><mtext>G</mtext></mrow></mrow><mo>}</mo></mstyle></mrow><annotation>{\displaystyle \{x_{j}\in { extbf {G}}\}}</annotation></semantics></math><img src=$ G : ${\displaystyle \lim _{j o \infty }b(x_{j})=\infty <semantics><mrow><mstyle><munder><mo>limite</mo><mrow><mi>j</mi><mo>→</mo><mi>∞</mi></mrow></munder><mi>b</mi><mo>(</mo><msub><mi>x</mi><mrow><mi>j</mi></mrow></msub><mo>)</mo><mo>=</mo><mi>∞</mi></mstyle></mrow><annotation>{ displaystyle lim _ {j to infty} b (x_ {j}) = infty}</annotation></semantics></math><img src=$ b est non dégénéré, c'est-à-dire : ${\displaystyle b''(x) <semantics><mrow><mstyle><msup><mi>b</mi><mo>″</mo></msup><mo>(</mo><mi>x</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle b''(x)}</annotation></semantics></math><img src=$ ${\displaystyle P_{t}=t\cdot f(x)+b(x) <semantics><mrow><mstyle><msub><mi>P</mi><mrow><mi>t</mi></mrow></msub><mo>=</mo><mi>t</mi><mo>⋅</mo><mi>f</mi><mo>(</mo><mi>x</mi><mo>)</mo><mo>+</mo><mi>b</mi><mo>(</mo><mi>x</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle P_{t}=t\cdot f(x)+b(x)}</annotation></semantics></math><img src=$

Techniquement, le programme est restreint, puisque b est défini uniquement à l'intérieur de G. Cependant, en pratique, il est possible de le résoudre comme un programme non contraint, car tout solveur cherchant à minimiser la fonction ne s'approchera pas de la frontière où b tend vers l'infini. Par conséquent, ( P( _t )) admet une solution unique, notée x *( t ). La fonction x * est une fonction continue de t , appelée chemin central . Tous les points d'accumulation de x *, lorsque t tend vers l'infini, sont des solutions optimales du programme initial (P).

Une méthode de suivi de chemin est une méthode permettant de suivre la fonction x * le long d'une certaine suite croissante t₁ _, t₂ _{, ..., c'est}_- à-dire : calculer une approximation suffisamment bonne xᵢ du point x *( tᵢ ₎ , telle que la différence xᵢ _- x *( tᵢ ) tende vers 0 lorsque i tend vers l'infini ; puis la suite xᵢ converge vers la solution optimale de (P). Cela nécessite de spécifier trois _éléments_:

La fonction barrière b(x).
Une politique pour déterminer les paramètres de pénalité t _i .
Le solveur d'optimisation sans contrainte utilisé pour résoudre ( P _i ) et trouver x _i est par exemple la méthode de Newton . Il est à noter que chaque x _i peut servir de point de départ pour résoudre le problème suivant ( P _{i+1} ).

La principale difficulté pour démontrer que la méthode est polynomiale réside dans le fait que, lorsque le paramètre de pénalité augmente, la solution se rapproche de la frontière et la pente de la fonction s'accentue. Le temps d'exécution des solveurs, comme la méthode de Newton, s'allonge alors, et il devient difficile de prouver que le temps d'exécution total est polynomial.

Renegar et Gonzaga ont prouvé qu'une instance spécifique d'une méthode de suivi de chemin est polynomiale :

Les contraintes (et l'objectif) sont des fonctions linéaires ;
La fonction barrière est logarithmique : ${\displaystyle b(x)=-\sum _{j=1}^{m}\log({-g_{j}(x)}) <semantics><mrow><mstyle><mi>b</mi><mo>(</mo><mi>x</mi><mo>)</mo><mo>=</mo><mo>−</mo><munderover><mo>∑</mo><mrow><mi>j</mi><mo>=</mo><mn>1</mn></mrow><mrow><mi>m</mi></mrow></munderover><mi>enregistrer</mi><mo>⁡</mo><mo>(</mo><mrow><mo>−</mo><msub><mi>g</mi><mrow><mi>j</mi></mrow></msub><mo>(</mo><mi>x</mi><mo>)</mo></mrow><mo>)</mo></mstyle></mrow><annotation>{\displaystyle b(x)=-\sum _{j=1}^{m}\log({-g_{j}(x)})}</annotation></semantics></math><img src=$
Le paramètre de pénalité t est mis à jour géométriquement, c'est-à-dire, ${\displaystyle t_{i+1}:=\mu \cdot t_{i <semantics><mrow><mstyle><msub><mi>t</mi><mrow><mi>je</mi><mo>+</mo><mn>1</mn></mrow></msub><mo>:=</mo><mi>μ</mi><mo>⋅</mo><msub><mi>t</mi><mrow><mi>je</mi></mrow></msub></mstyle></mrow><annotation>{\displaystyle t_{i+1}:=\mu \cdot t_{i}}</annotation></semantics></math><img src=$ μ est une constante (ils ont pris ${\displaystyle \mu =1+0.001\cdot {\sqrt {m <semantics><mrow><mstyle><mi>μ</mi><mo>=</mo><mn>1</mn><mo>+</mo><mn>0,001</mn><mo>⋅</mo><mrow><msqrt><mi>m</mi></msqrt></mrow></mstyle></mrow><annotation>{\displaystyle \mu =1+0.001\cdot {\sqrt {m}}}</annotation></semantics></math><img src=$ m est le nombre de contraintes d'inégalité);
Le solveur est la méthode de Newton, et une seule étape de Newton est effectuée pour chaque étape de t .

Ils ont prouvé que, dans ce cas, la différence x _i - x *( t _i ) reste au plus égale à 0,01, et f( x _i ) - f* est au plus égale à 0,01 ${\displaystyle {\frac {2m}{t_{j <semantics><mrow><mstyle><mrow><mfrac><mrow><mn>2</mn><mi>m</mi></mrow><msub><mi>t</mi><mrow><mi>j</mi></mrow></msub></mfrac></mrow></mstyle></mrow><annotation>{\displaystyle {\frac {2m}{t_{j}}}}</annotation></semantics></math><img src=$ ${\displaystyle {\frac {1}{t_{j <semantics><mrow><mstyle><mrow><mfrac><mn>1</mn><msub><mi>t</mi><mrow><mi>j</mi></mrow></msub></mfrac></mrow></mstyle></mrow><annotation>{ displaystyle { frac {1} {t_ {j}}}}</annotation></semantics></math><img src=$ t _i par 2 (ou tout autre facteur constant), ce qui nécessite ${\displaystyle O({\sqrt {m}}) <semantics><mrow><mstyle><mi>O</mi><mo>(</mo><mrow><msqrt><mi>m</mi></msqrt></mrow><mo>)</mo></mstyle></mrow><annotation>{\displaystyle O({\sqrt {m}})}</annotation></semantics></math><img src=$ mn ² ) opérations, la complexité totale est de O( m ^3/2 n ² ) opérations pour un chiffre de précision.

Yuri Nesterov a étendu cette idée des programmes linéaires aux programmes non linéaires. Il a noté que la principale propriété de la barrière logarithmique, utilisée dans les démonstrations précédentes, est son auto-concordance avec un paramètre de barrière fini. Par conséquent, de nombreuses autres classes de programmes convexes peuvent être résolues en temps polynomial à l'aide d'une méthode de suivi de chemin, si l'on peut trouver une fonction barrière auto-concordante appropriée pour leur région admissible.

Détails

On nous donne un problème d'optimisation convexe (P) sous « forme standard » :

minimiser c ^Tx st x dans G ,

où G est convexe et fermée. On peut également supposer que G est bornée (on peut facilement la rendre bornée en ajoutant une contrainte | x | ≤ R pour un R suffisamment grand ).

Pour utiliser la méthode des points intérieurs, nous avons besoin d'une barrière auto-concordante pour G. Soit b une barrière M -auto-concordante pour G , où M ≥ 1 est le paramètre d'auto-concordance. Nous supposons que nous pouvons calculer efficacement la valeur de b , son gradient et sa matrice hessienne pour tout point x à l'intérieur de G.

Pour tout t > 0, on définit la fonction objectif pénalisée f _t (x) := t c ^Tx + b( x ) . On définit le chemin des minimiseurs par : x*(t) := arg min f _t (x) . On approche ce chemin par une suite croissante t _i . La suite est initialisée par une procédure d'initialisation en deux phases non triviale. Ensuite, elle est mise à jour selon la règle suivante : ${\displaystyle t_{i+1}:=\mu \cdot t_{i <semantics><mrow><mstyle><msub><mi>t</mi><mrow><mi>je</mi><mo>+</mo><mn>1</mn></mrow></msub><mo>:=</mo><mi>μ</mi><mo>⋅</mo><msub><mi>t</mi><mrow><mi>je</mi></mrow></msub></mstyle></mrow><annotation>{\displaystyle t_{i+1}:=\mu \cdot t_{i}}</annotation></semantics></math><img src=$

Pour chaque t _i , nous trouvons un minimum approximatif de f _ti , noté x _i . Ce minimum approximatif est choisi de manière à satisfaire la « condition de proximité » suivante (où L est la tolérance du chemin ) :

${\displaystyle {\sqrt {[ abla _{x}f_{t}(x_{i})]^{T}[ abla _{x}^{2}f_{t}(x_{i})]^{-1}[ abla _{x}f_{t}(x_{i})]}}\leq L <semantics><mrow><mstyle><mrow><msqrt><mo>[</mo><msub><mi>∇</mi><mrow><mi>x</mi></mrow></msub><msub><mi>f</mi><mrow><mi>t</mi></mrow></msub><mo>(</mo><msub><mi>x</mi><mrow><mi>je</mi></mrow></msub><mo>)</mo><msup><mo>]</mo><mrow><mi>T</mi></mrow></msup><mo>[</mo><msubsup><mi>∇</mi><mrow><mi>x</mi></mrow><mrow><mn>2</mn></mrow></msubsup><msub><mi>f</mi><mrow><mi>t</mi></mrow></msub><mo>(</mo><msub><mi>x</mi><mrow><mi>je</mi></mrow></msub><mo>)</mo><msup><mo>]</mo><mrow><mo>−</mo><mn>1</mn></mrow></msup><mo>[</mo><msub><mi>∇</mi><mrow><mi>x</mi></mrow></msub><msub><mi>f</mi><mrow><mi>t</mi></mrow></msub><mo>(</mo><msub><mi>x</mi><mrow><mi>je</mi></mrow></msub><mo>)</mo><mo>]</mo></msqrt></mrow><mo>≤</mo><mi>L</mi></mstyle></mrow><annotation>{\displaystyle {\sqrt {[ abla _{x}f_{t}(x_{i})]^{T}[ abla _{x}^{2}f_{t}(x_{i})]^{-1}[ abla _{x}f_{t}(x_{i})]}}\leq L}</annotation></semantics></math><img src=$

Pour trouver x _i_+1 , on part de x _i et on applique la méthode de Newton amortie . On répète cette méthode plusieurs fois, jusqu'à ce que la « relation de proximité » mentionnée précédemment soit satisfaite. Le premier point qui satisfait cette relation est noté x _i₊₁ .

Convergence et complexité

Le taux de convergence de la méthode est donné par la formule suivante, pour tout i :

${\displaystyle c^{T}x_{i}-c^{*}\leq {\frac {2M}{t_{0}}}\mu ^{-i <semantics><mrow><mstyle><msup><mi>c</mi><mrow><mi>T</mi></mrow></msup><msub><mi>x</mi><mrow><mi>je</mi></mrow></msub><mo>−</mo><msup><mi>c</mi><mrow><mo>∗</mo></mrow></msup><mo>≤</mo><mrow><mfrac><mrow><mn>2</mn><mi>M</mi></mrow><msub><mi>t</mi><mrow><mn>0</mn></mrow></msub></mfrac></mrow><msup><mi>μ</mi><mrow><mo>−</mo><mi>je</mi></mrow></msup></mstyle></mrow><annotation>{\displaystyle c^{T}x_{i}-c^{*}\leq {\frac {2M}{t_{0}}}\mu ^{-i}}</annotation></semantics></math><img src=$

Prise ${\displaystyle \mu =\left(1+r/{\sqrt {M}} ight) <semantics><mrow><mstyle><mi>μ</mi><mo>=</mo><mrow><mo>(</mo><mrow><mn>1</mn><mo>+</mo><mi>r</mi><mrow><mo>/</mo></mrow><mrow><msqrt><mi>M</mi></msqrt></mrow></mrow><mo>)</mo></mrow></mstyle></mrow><annotation>{\displaystyle \mu =\left(1+r/{\sqrt {M}} ight)}</annotation></semantics></math><img src=$ x _i à x _i_+1 est au plus un nombre fixe, qui dépend uniquement de r et L. En particulier, le nombre total d'itérations de Newton nécessaires pour trouver une solution ε -approximative (c'est-à-dire trouver x dans G tel que c ^Tx - c* ≤ ε ) est au plus :

${\displaystyle O(1)\cdot {\sqrt {M}}\cdot \ln \left({\frac {M}{t_{0}\varepsilon }}+1 ight) <semantics><mrow><mstyle><mi>O</mi><mo>(</mo><mn>1</mn><mo>)</mo><mo>⋅</mo><mrow><msqrt><mi>M</mi></msqrt></mrow><mo>⋅</mo><mi>ln</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><mrow><mfrac><mi>M</mi><mrow><msub><mi>t</mi><mrow><mn>0</mn></mrow></msub><mi>ε</mi></mrow></mfrac></mrow><mo>+</mo><mn>1</mn></mrow><mo>)</mo></mrow></mstyle></mrow><annotation>{\displaystyle O(1)\cdot {\sqrt {M}}\cdot \ln \left({\frac {M}{t_{0}\varepsilon }}+1 ight)}</annotation></semantics></math><img src=$

où le facteur constant O(1) ne dépend que de r et L. Le nombre d'itérations de Newton requises pour la procédure d'initialisation en deux étapes est au plus :

${\displaystyle O(1)\cdot {\sqrt {M}}\cdot \ln \left({\frac {M}{1-\pi _{x_{f}^{*}}({\bar {x}})}}+1 ight)+O(1)\cdot {\sqrt {M}}\cdot \ln \left({\frac {M{ ext{Var}}_{G}(c)}{\epsilon }}+1 ight) <semantics><mrow><mstyle><mi>O</mi><mo>(</mo><mn>1</mn><mo>)</mo><mo>⋅</mo><mrow><msqrt><mi>M</mi></msqrt></mrow><mo>⋅</mo><mi>ln</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><mrow><mfrac><mi>M</mi><mrow><mn>1</mn><mo>−</mo><msub><mi>π</mi><mrow><msubsup><mi>x</mi><mrow><mi>f</mi></mrow><mrow><mo>∗</mo></mrow></msubsup></mrow></msub><mo>(</mo><mrow><mrow><mover><mi>x</mi><mo>¯</mo></mover></mrow></mrow><mo>)</mo></mrow></mfrac></mrow><mo>+</mo><mn>1</mn></mrow><mo>)</mo></mrow><mo>+</mo><mi>O</mi><mo>(</mo><mn>1</mn><mo>)</mo><mo>⋅</mo><mrow><msqrt><mi>M</mi></msqrt></mrow><mo>⋅</mo><mi>ln</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><mrow><mfrac><mrow><mi>M</mi><msub><mrow><mtext>Var</mtext></mrow><mrow><mi>G</mi></mrow></msub><mo>(</mo><mi>c</mi><mo>)</mo></mrow><mi>ϵ</mi></mfrac></mrow><mo>+</mo><mn>1</mn></mrow><mo>)</mo></mrow></mstyle></mrow><annotation>{\displaystyle O(1)\cdot {\sqrt {M}}\cdot \ln \left({\frac {M}{1-\pi _{x_{f}^{*}}({\bar {x}})}}+1 ight)+O(1)\cdot {\sqrt {M}}\cdot \ln \left({\frac {M{ ext{Var}}_{G}(c)}{\epsilon }}+1 ight)}</annotation></semantics></math><img src=$

où le facteur constant O(1) ne dépend que de r et L , et ${\displaystyle { ext{Var}}_{G}(c):=\max _{x\in G}c^{T}x-\min _{x\in G}c^{T}x <semantics><mrow><mstyle><msub><mrow><mtext>Var</mtext></mrow><mrow><mi>G</mi></mrow></msub><mo>(</mo><mi>c</mi><mo>)</mo><mo>:=</mo><munder><mo>max</mo><mrow><mi>x</mi><mo>∈</mo><mi>G</mi></mrow></munder><msup><mi>c</mi><mrow><mi>T</mi></mrow></msup><mi>x</mi><mo>−</mo><munder><mo>min</mo><mrow><mi>x</mi><mo>∈</mo><mi>G</mi></mrow></munder><msup><mi>c</mi><mrow><mi>T</mi></mrow></msup><mi>x</mi></mstyle></mrow><annotation>{\displaystyle { ext{Var}}_{G}(c):=\max _{x\in G}c^{T}x-\min _{x\in G}c^{T}x}</annotation></semantics></math><img src=$ ${\displaystyle {\bar {x <semantics><mrow><mstyle><mrow><mrow><mover><mi>x</mi><mo>¯</mo></mover></mrow></mrow></mstyle></mrow><annotation>{\displaystyle {\bar {x}}}</annotation></semantics></math><img src=$ G. Globalement, la complexité de Newton globale pour trouver une solution ε -approximative est au plus

${\displaystyle O(1)\cdot {\sqrt {M}}\cdot \ln \left({\frac {V}{\varepsilon }}+1 ight) <semantics><mrow><mstyle><mi>O</mi><mo>(</mo><mn>1</mn><mo>)</mo><mo>⋅</mo><mrow><msqrt><mi>M</mi></msqrt></mrow><mo>⋅</mo><mi>ln</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><mrow><mfrac><mi>V</mi><mi>ε</mi></mfrac></mrow><mo>+</mo><mn>1</mn></mrow><mo>)</mo></mrow></mstyle></mrow><annotation>{\displaystyle O(1)\cdot {\sqrt {M}}\cdot \ln \left({\frac {V}{\varepsilon }}+1 ight)}</annotation></semantics></math><img src=$ ${\displaystyle V={\frac {{ ext{Var}}_{G}(c)}{1-\pi _{x_{f}^{*}({\bar {x}}) <semantics><mrow><mstyle><mi>V</mi><mo>=</mo><mrow><mfrac><mrow><msub><mrow><mtext>Var</mtext></mrow><mrow><mi>G</mi></mrow></msub><mo>(</mo><mi>c</mi><mo>)</mo></mrow><mrow><mn>1</mn><mo>−</mo><msub><mi>π</mi><mrow><msubsup><mi>x</mi><mrow><mi>f</mi></mrow><mrow><mo>∗</mo></mrow></msubsup><mo>(</mo><mrow><mrow><mover><mi>x</mi><mo>¯</mo></mover></mrow></mrow><mo>)</mo></mrow></msub></mrow></mfrac></mrow></mstyle></mrow><annotation>{\displaystyle V={\frac {{ ext{Var}}_{G}(c)}{1-\pi _{x_{f}^{*}({\bar {x}})}}}}</annotation></semantics></math><img src=$

Chaque étape de Newton nécessite O( ^n³) opérations arithmétiques.

Initialisation : méthodes de phase I

Pour initialiser les méthodes de suivi de chemin, il nous faut un point situé à l'intérieur relatif de la région admissible G. Autrement dit : si G est définie par les inégalités g _i ( x ) ≤ 0, alors il nous faut un x tel que g _i ( x ) < 0 pour tout i ∈ 1, ..., m . Si nous ne disposons pas d'un tel point, nous devons en trouver un à l'aide d'une méthode dite de phase I. Une méthode de phase I simple consiste à résoudre le programme convexe suivant : ${\displaystyle {\begin{aligned}{ ext{minimize}}\quad &s\\{ ext{subject to}}\quad &g_{i}(x)\leq s{ ext{ for }}i=1,\dots ,m\end{aligned <semantics><mrow><mstyle><mrow><mtable><mtr><mtd><mrow><mtext>minimiser</mtext></mrow><mspace></mspace></mtd><mtd><mi>s</mi></mtd></mtr><mtr><mtd><mrow><mtext>sous réserve de</mtext></mrow><mspace></mspace></mtd><mtd><msub><mi>g</mi><mrow><mi>je</mi></mrow></msub><mo>(</mo><mi>x</mi><mo>)</mo><mo>≤</mo><mi>s</mi><mrow><mtext> pour </mtext></mrow><mi>je</mi><mo>=</mo><mn>1</mn><mo>,</mo><mo>…</mo><mo>,</mo><mi>m</mi></mtd></mtr></mtable></mrow></mstyle></mrow><annotation>{\displaystyle {\begin{aligned}{ ext{minimize}}\quad &s\\{ ext{subject to}}\quad &g_{i}(x)\leq s{ ext{ for }}i=1,\dots ,m\end{aligned}}}</annotation></semantics></math><img src=$ s *.

Si s *<0, alors nous savons que x* est un point intérieur du problème initial et pouvons passer à la « phase II », qui consiste à résoudre le problème initial.
Si s *>0, alors nous savons que le programme original est irréalisable - la région réalisable est vide.
Si s *=0 et qu'il est atteint par une solution x*, alors le problème est faisable mais n'a pas de point intérieur ; s'il n'est pas atteint, alors le problème est infaisable.

_{Pour ce programme ,} il est facile d'obtenir un point intérieur : on peut choisir arbitrairement x = 0 et s = n'importe quel nombre supérieur à max( f₁ (0), ..., fₘ (0 ₎ ). Il peut donc être résolu par des méthodes de points intérieurs. Cependant, le temps d'exécution est proportionnel à log(1/ s *). Plus s* tend vers 0, plus il devient difficile de trouver une solution exacte au problème de la phase I, et donc plus difficile de déterminer si le problème initial est réalisable.

Considérations pratiques

Les garanties théoriques supposent que le paramètre de pénalité augmente au taux ${\displaystyle \mu =\left(1+r/{\sqrt {M}} ight) <semantics><mrow><mstyle><mi>μ</mi><mo>=</mo><mrow><mo>(</mo><mrow><mn>1</mn><mo>+</mo><mi>r</mi><mrow><mo>/</mo></mrow><mrow><msqrt><mi>M</mi></msqrt></mrow></mrow><mo>)</mo></mrow></mstyle></mrow><annotation>{\displaystyle \mu =\left(1+r/{\sqrt {M}} ight)}</annotation></semantics></math><img src=$ ${\displaystyle O({\sqrt {M}}) <semantics><mrow><mstyle><mi>O</mi><mo>(</mo><mrow><msqrt><mi>M</mi></msqrt></mrow><mo>)</mo></mstyle></mrow><annotation>{\displaystyle O({\sqrt {M}})}</annotation></semantics></math><img src=$ μ est plus grand (par exemple 2 ou plus), alors le nombre d'itérations de Newton requises dans le pire des cas est dans ${\displaystyle O(M) <semantics><mrow><mstyle><mi>O</mi><mo>(</mo><mi>M</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle O(M)}</annotation></semantics></math><img src=$ de μ plus élevée conduit à une convergence beaucoup plus rapide. Ces méthodes sont appelées méthodes à long pas . En pratique, si μ est compris entre 3 et 100, le programme converge en 20 à 40 itérations de Newton, quel que soit le nombre de contraintes (bien que la durée d'exécution de chaque itération de Newton augmente naturellement avec le nombre de contraintes). La valeur exacte de μ dans cet intervalle a peu d'influence sur les performances.

Méthodes de réduction du potentiel

Pour les méthodes de réduction du potentiel, le problème est présenté sous forme conique :

minimiser c ^Tx st x dans {b+L} ∩ K ,

où b est un vecteur de R ^n , L est un sous-espace vectoriel de R ^n (donc b + L est un plan affine ), et K est un cône convexe fermé et pointé d'intérieur non vide. Tout programme convexe peut être converti en forme conique. Pour utiliser la méthode de réduction du potentiel (en particulier, l'extension de l'algorithme de Karmarkar à la programmation convexe), nous avons besoin des hypothèses suivantes :

A. L'ensemble admissible { b+L} ∩ K est borné et intersecte l'intérieur du cône K.
B. On nous donne à l'avance une solution strictement réalisable x ^, c'est-à-dire une solution réalisable à l'intérieur de K .
C. Nous connaissons à l'avance la valeur optimale de l'objectif, c*, du problème.
D. On nous donne une barrière auto-concordante M -logarithmiquement homogène F pour le cône K.

Les hypothèses A, B et D sont nécessaires dans la plupart des méthodes de points intérieurs. L'hypothèse C est spécifique à l'approche de Karmarkar ; elle peut être atténuée en utilisant une fonction objectif variable. Il est possible de réduire davantage le programme au format de Karmarkar .

minimiser s ^Tx st x dans M ∩ K et e ^Tx = 1

où M est un sous-espace linéaire de dans R ⁿ , et la valeur optimale de l'objectif est 0. La méthode est basée sur la fonction de potentiel scalaire suivante :

v ( x ) = F ( x ) ⁺M ln ( sTx )

où F est la barrière M -auto-concordante du cône admissible. Il est possible de démontrer que, lorsque x est strictement admissible et que v ( x ) est très petit (très négatif), x est approximativement optimal. L'idée de la méthode de réduction du potentiel est de modifier x de sorte que le potentiel à chaque itération diminue d'au moins une constante fixe X (plus précisément, X = 1/3 - ln(4/3)). Cela implique qu'après i itérations, la différence entre la valeur de la fonction objectif et sa valeur optimale est au plus V * exp( -iX / M ), où V est une constante dépendant des données. Par conséquent, le nombre d'étapes de Newton nécessaires pour une solution ε -approximative est au plus ${\displaystyle O(1)\cdot M\cdot \ln \left({\frac {V}{\varepsilon }}+1 ight)+1 <semantics><mrow><mstyle><mi>O</mi><mo>(</mo><mn>1</mn><mo>)</mo><mo>⋅</mo><mi>M</mi><mo>⋅</mo><mi>ln</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><mrow><mfrac><mi>V</mi><mi>ε</mi></mfrac></mrow><mo>+</mo><mn>1</mn></mrow><mo>)</mo></mrow><mo>+</mo><mn>1</mn></mstyle></mrow><annotation>{\displaystyle O(1)\cdot M\cdot \ln \left({\frac {V}{\varepsilon }}+1 ight)+1}</annotation></semantics></math><img src=$

Notez que dans les méthodes de suivi de chemin, l'expression est ${\displaystyle {\sqrt {M <semantics><mrow><mstyle><mrow><msqrt><mi>M</mi></msqrt></mrow></mstyle></mrow><annotation>{\displaystyle {\sqrt {M}}}</annotation></semantics></math><img src=$ M , qui est théoriquement préférable. Mais en pratique, la méthode de Karmarkar permet de progresser par étapes beaucoup plus importantes vers l'objectif, et peut donc converger bien plus rapidement que ne le garantissent les théories.

Méthodes primales-duales

L'idée de la méthode primale-duale est facile à démontrer pour l'optimisation non linéaire sous contraintes . Par souci de simplicité, considérons le problème d'optimisation non linéaire suivant avec contraintes d'inégalité :

${\displaystyle {\begin{aligned}\operatorname {minimize} \quad &f(x)\\{ ext{subject to}}\quad &x\in \mathbb {R} ^{n},\\&c_{i}(x)\geq 0{ ext{ for }}i=1,\ldots ,m,\\{ ext{where}}\quad &f:\mathbb {R} ^{n} o \mathbb {R} ,\ c_{i}:\mathbb {R} ^{n} o \mathbb {R} .\end{aligned}}\quad (1) <semantics><mrow><mstyle><mrow><mtable><mtr><mtd><mi>minimiser</mi><mspace></mspace></mtd><mtd><mi>f</mi><mo>(</mo><mi>x</mi><mo>)</mo></mtd></mtr><mtr><mtd><mrow><mtext>sous réserve de</mtext></mrow><mspace></mspace></mtd><mtd><mi>x</mi><mo>∈</mo><msup><mrow><mi>R</mi></mrow><mrow><mi>n</mi></mrow></msup><mo>,</mo></mtd></mtr><mtr><mtd></mtd><mtd><msub><mi>c</mi><mrow><mi>je</mi></mrow></msub><mo>(</mo><mi>x</mi><mo>)</mo><mo>≥</mo><mn>0</mn><mrow><mtext> pour </mtext></mrow><mi>je</mi><mo>=</mo><mn>1</mn><mo>,</mo><mo>…</mo><mo>,</mo><mi>m</mi><mo>,</mo></mtd></mtr><mtr><mtd><mrow><mtext>où</mtext></mrow><mspace></mspace></mtd><mtd><mi>f</mi><mo>:</mo><msup><mrow><mi>R</mi></mrow><mrow><mi>n</mi></mrow></msup><mo>→</mo><mrow><mi>R</mi></mrow><mo>,</mo><mtext> </mtext><msub><mi>c</mi><mrow><mi>je</mi></mrow></msub><mo>:</mo><msup><mrow><mi>R</mi></mrow><mrow><mi>n</mi></mrow></msup><mo>→</mo><mrow><mi>R</mi></mrow><mo>.</mo></mtd></mtr></mtable></mrow><mspace></mspace><mo>(</mo><mn>1</mn><mo>)</mo></mstyle></mrow><annotation>{\displaystyle {\begin{aligned}\operatorname {minimize} \quad &f(x)\\{ ext{subject to}}\quad &x\in \mathbb {R} ^{n},\\&c_{i}(x)\geq 0{ ext{ for }}i=1,\ldots ,m,\\{ ext{where}}\quad &f:\mathbb {R} ^{n} o \mathbb {R} ,\ c_{i}:\mathbb {R} ^{n} o \mathbb {R} .\end{aligned}}\quad (1)}</annotation></semantics></math><img src=$

Ce problème d'optimisation sous contrainte d'inégalité est résolu en le convertissant en une fonction objectif sans contrainte dont on espère trouver efficacement le minimum. Plus précisément, la fonction barrière logarithmique associée à (1) est ${\displaystyle B(x,\mu )=f(x)-\mu \sum _{i=1}^{m}\log(c_{i}(x)).\quad (2) <semantics><mrow><mstyle><mi>B</mi><mo>(</mo><mi>x</mi><mo>,</mo><mi>μ</mi><mo>)</mo><mo>=</mo><mi>f</mi><mo>(</mo><mi>x</mi><mo>)</mo><mo>−</mo><mi>μ</mi><munderover><mo>∑</mo><mrow><mi>je</mi><mo>=</mo><mn>1</mn></mrow><mrow><mi>m</mi></mrow></munderover><mi>enregistrer</mi><mo>⁡</mo><mo>(</mo><msub><mi>c</mi><mrow><mi>je</mi></mrow></msub><mo>(</mo><mi>x</mi><mo>)</mo><mo>)</mo><mo>.</mo><mspace></mspace><mo>(</mo><mn>2</mn><mo>)</mo></mstyle></mrow><annotation>{\displaystyle B(x,\mu )=f(x)-\mu \sum _{i=1}^{m}\log(c_{i}(x)).\quad (2)}</annotation></semantics></math><img src=$

Ici ${\displaystyle \mu <semantics><mrow><mstyle><mi>μ</mi></mstyle></mrow><annotation>{\displaystyle \mu }</annotation></semantics></math><img src=$ ${\displaystyle \mu <semantics><mrow><mstyle><mi>μ</mi></mstyle></mrow><annotation>{\displaystyle \mu }</annotation></semantics></math><img src=$ ${\displaystyle B(x,\mu ) <semantics><mrow><mstyle><mi>B</mi><mo>(</mo><mi>x</mi><mo>,</mo><mi>μ</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle B(x,\mu )}</annotation></semantics></math><img src=$

Le gradient d'une fonction différentiable ${\displaystyle h:\mathbb {R} ^{n} o \mathbb {R} <semantics><mrow><mstyle><mi>h</mi><mo>:</mo><msup><mrow><mi>R</mi></mrow><mrow><mi>n</mi></mrow></msup><mo>→</mo><mrow><mi>R</mi></mrow></mstyle></mrow><annotation>{\displaystyle h:\mathbb {R} ^{n} o \mathbb {R} }</annotation></semantics></math><img src=$ ${\displaystyle abla h <semantics><mrow><mstyle><mi>∇</mi><mi>h</mi></mstyle></mrow><annotation>{\displaystyle abla h}</annotation></semantics></math><img src=$ ${\displaystyle abla B(x,\mu )= abla f(x)-\mu \sum _{i=1}^{m}{\frac {1}{c_{i}(x)}} abla c_{i}(x).\quad (3) <semantics><mrow><mstyle><mi>∇</mi><mi>B</mi><mo>(</mo><mi>x</mi><mo>,</mo><mi>μ</mi><mo>)</mo><mo>=</mo><mi>∇</mi><mi>f</mi><mo>(</mo><mi>x</mi><mo>)</mo><mo>−</mo><mi>μ</mi><munderover><mo>∑</mo><mrow><mi>je</mi><mo>=</mo><mn>1</mn></mrow><mrow><mi>m</mi></mrow></munderover><mrow><mfrac><mn>1</mn><mrow><msub><mi>c</mi><mrow><mi>je</mi></mrow></msub><mo>(</mo><mi>x</mi><mo>)</mo></mrow></mfrac></mrow><mi>∇</mi><msub><mi>c</mi><mrow><mi>je</mi></mrow></msub><mo>(</mo><mi>x</mi><mo>)</mo><mo>.</mo><mspace></mspace><mo>(</mo><mn>3</mn><mo>)</mo></mstyle></mrow><annotation>{\displaystyle abla B(x,\mu )= abla f(x)-\mu \sum _{i=1}^{m}{\frac {1}{c_{i}(x)}} abla c_{i}(x).\quad (3)}</annotation></semantics></math><img src=$

En plus de la variable originale (« primale ») ${\displaystyle x <semantics><mrow><mstyle><mi>x</mi></mstyle></mrow><annotation>{\displaystyle x}</annotation></semantics></math><img src=$ ${\displaystyle \lambda \in \mathbb {R} ^{m <semantics><mrow><mstyle><mi>λ</mi><mo>∈</mo><msup><mrow><mi>R</mi></mrow><mrow><mi>m</mi></mrow></msup></mstyle></mrow><annotation>{\displaystyle \lambda \in \mathbb {R} ^{m}}</annotation></semantics></math><img src=$ ${\displaystyle c_{i}(x)\lambda _{i}=\mu ,\quad \forall i=1,\ldots ,m.\quad (4) <semantics><mrow><mstyle><msub><mi>c</mi><mrow><mi>je</mi></mrow></msub><mo>(</mo><mi>x</mi><mo>)</mo><msub><mi>λ</mi><mrow><mi>je</mi></mrow></msub><mo>=</mo><mi>μ</mi><mo>,</mo><mspace></mspace><mi>∀</mi><mi>je</mi><mo>=</mo><mn>1</mn><mo>,</mo><mo>…</mo><mo>,</mo><mi>m</mi><mo>.</mo><mspace></mspace><mo>(</mo><mn>4</mn><mo>)</mo></mstyle></mrow><annotation>{\displaystyle c_{i}(x)\lambda _{i}=\mu ,\quad \forall i=1,\ldots ,m.\quad (4)}</annotation></semantics></math><img src=$

L'équation (4) est parfois appelée la condition de « complémentarité perturbée », en raison de sa ressemblance avec le « relâchement complémentaire » dans les conditions KKT .

Nous essayons de trouver ceux-là ${\displaystyle (x_{\mu },\lambda _{\mu }) <semantics><mrow><mstyle><mo>(</mo><msub><mi>x</mi><mrow><mi>μ</mi></mrow></msub><mo>,</mo><msub><mi>λ</mi><mrow><mi>μ</mi></mrow></msub><mo>)</mo></mstyle></mrow><annotation>{\displaystyle (x_{\mu },\lambda _{\mu })}</annotation></semantics></math><img src=$

Substitution ${\displaystyle 1/c_{i}(x)=\lambda _{i}/\mu <semantics><mrow><mstyle><mn>1</mn><mrow><mo>/</mo></mrow><msub><mi>c</mi><mrow><mi>je</mi></mrow></msub><mo>(</mo><mi>x</mi><mo>)</mo><mo>=</mo><msub><mi>λ</mi><mrow><mi>je</mi></mrow></msub><mrow><mo>/</mo></mrow><mi>μ</mi></mstyle></mrow><annotation>{\displaystyle 1/c_{i}(x)=\lambda _{i}/\mu }</annotation></semantics></math><img src=$ ${\displaystyle abla B(x_{\mu },\lambda _{\mu })= abla f(x_{\mu })-J(x_{\mu })^{T}\lambda _{\mu }=0,\quad (5) <semantics><mrow><mstyle><mi>∇</mi><mi>B</mi><mo>(</mo><msub><mi>x</mi><mrow><mi>μ</mi></mrow></msub><mo>,</mo><msub><mi>λ</mi><mrow><mi>μ</mi></mrow></msub><mo>)</mo><mo>=</mo><mi>∇</mi><mi>f</mi><mo>(</mo><msub><mi>x</mi><mrow><mi>μ</mi></mrow></msub><mo>)</mo><mo>−</mo><mi>J</mi><mo>(</mo><msub><mi>x</mi><mrow><mi>μ</mi></mrow></msub><msup><mo>)</mo><mrow><mi>T</mi></mrow></msup><msub><mi>λ</mi><mrow><mi>μ</mi></mrow></msub><mo>=</mo><mn>0</mn><mo>,</mo><mspace></mspace><mo>(</mo><mn>5</mn><mo>)</mo></mstyle></mrow><annotation>{\displaystyle abla B(x_{\mu },\lambda _{\mu })= abla f(x_{\mu })-J(x_{\mu })^{T}\lambda _{\mu }=0,\quad (5)}</annotation></semantics></math><img src=$ ${\displaystyle J <semantics><mrow><mstyle><mi>J</mi></mstyle></mrow><annotation>{\displaystyle J}</annotation></semantics></math><img src=$ ${\displaystyle c(x) <semantics><mrow><mstyle><mi>c</mi><mo>(</mo><mi>x</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle c(x)}</annotation></semantics></math><img src=$

L'intuition derrière (5) est que le gradient de ${\displaystyle f(x) <semantics><mrow><mstyle><mi>f</mi><mo>(</mo><mi>x</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle f(x)}</annotation></semantics></math><img src=$ ${\displaystyle \mu <semantics><mrow><mstyle><mi>μ</mi></mstyle></mrow><annotation>{\displaystyle \mu }</annotation></semantics></math><img src=$ ${\displaystyle c_{i}(x)=0 <semantics><mrow><mstyle><msub><mi>c</mi><mrow><mi>je</mi></mrow></msub><mo>(</mo><mi>x</mi><mo>)</mo><mo>=</mo><mn>0</mn></mstyle></mrow><annotation>{\displaystyle c_{i}(x)=0}</annotation></semantics></math><img src=$ ${\displaystyle abla f <semantics><mrow><mstyle><mi>∇</mi><mi>f</mi></mstyle></mrow><annotation>{\displaystyle abla f}</annotation></semantics></math><img src=$ ${\displaystyle c_{i}(x) <semantics><mrow><mstyle><msub><mi>c</mi><mrow><mi>je</mi></mrow></msub><mo>(</mo><mi>x</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle c_{i}(x)}</annotation></semantics></math><img src=$

Laisser ${\displaystyle (p_{x},p_{\lambda }) <semantics><mrow><mstyle><mo>(</mo><msub><mi>p</mi><mrow><mi>x</mi></mrow></msub><mo>,</mo><msub><mi>p</mi><mrow><mi>λ</mi></mrow></msub><mo>)</mo></mstyle></mrow><annotation>{\displaystyle (p_{x},p_{\lambda })}</annotation></semantics></math><img src=$ ${\displaystyle (x,\lambda ) <semantics><mrow><mstyle><mo>(</mo><mi>x</mi><mo>,</mo><mi>λ</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle (x,\lambda )}</annotation></semantics></math><img src=$ ${\displaystyle (p_{x},p_{\lambda }) <semantics><mrow><mstyle><mo>(</mo><msub><mi>p</mi><mrow><mi>x</mi></mrow></msub><mo>,</mo><msub><mi>p</mi><mrow><mi>λ</mi></mrow></msub><mo>)</mo></mstyle></mrow><annotation>{\displaystyle (p_{x},p_{\lambda })}</annotation></semantics></math><img src=$ ${\displaystyle {\begin{pmatrix}H(x,\lambda )&-J(x)^{T}\\\operatorname {diag} (\lambda )J(x)&\operatorname {diag} (c(x))\end{pmatrix}}{\begin{pmatrix}p_{x}\\p_{\lambda }\end{pmatrix}}={\begin{pmatrix}- abla f(x)+J(x)^{T}\lambda \\\mu 1-\operatorname {diag} (c(x))\lambda \end{pmatrix}}, <semantics><mrow><mstyle><mrow><mrow><mo>(</mo><mtable><mtr><mtd><mi>H</mi><mo>(</mo><mi>x</mi><mo>,</mo><mi>λ</mi><mo>)</mo></mtd><mtd><mo>−</mo><mi>J</mi><mo>(</mo><mi>x</mi><msup><mo>)</mo><mrow><mi>T</mi></mrow></msup></mtd></mtr><mtr><mtd><mi>diagnostic</mi><mo>⁡</mo><mo>(</mo><mi>λ</mi><mo>)</mo><mi>J</mi><mo>(</mo><mi>x</mi><mo>)</mo></mtd><mtd><mi>diagnostic</mi><mo>⁡</mo><mo>(</mo><mi>c</mi><mo>(</mo><mi>x</mi><mo>)</mo><mo>)</mo></mtd></mtr></mtable><mo>)</mo></mrow></mrow><mrow><mrow><mo>(</mo><mtable><mtr><mtd><msub><mi>p</mi><mrow><mi>x</mi></mrow></msub></mtd></mtr><mtr><mtd><msub><mi>p</mi><mrow><mi>λ</mi></mrow></msub></mtd></mtr></mtable><mo>)</mo></mrow></mrow><mo>=</mo><mrow><mrow><mo>(</mo><mtable><mtr><mtd><mo>−</mo><mi>∇</mi><mi>f</mi><mo>(</mo><mi>x</mi><mo>)</mo><mo>+</mo><mi>J</mi><mo>(</mo><mi>x</mi><msup><mo>)</mo><mrow><mi>T</mi></mrow></msup><mi>λ</mi></mtd></mtr><mtr><mtd><mi>μ</mi><mn>1</mn><mo>−</mo><mi>diagnostic</mi><mo>⁡</mo><mo>(</mo><mi>c</mi><mo>(</mo><mi>x</mi><mo>)</mo><mo>)</mo><mi>λ</mi></mtd></mtr></mtable><mo>)</mo></mrow></mrow><mo>,</mo></mstyle></mrow><annotation>{\displaystyle {\begin{pmatrix}H(x,\lambda )&-J(x)^{T}\\\operatorname {diag} (\lambda )J(x)&\operatorname {diag} (c(x))\end{pmatrix}}{\begin{pmatrix}p_{x}\\p_{\lambda }\end{pmatrix}}={\begin{pmatrix}- abla f(x)+J(x)^{T}\lambda \\\mu 1-\operatorname {diag} (c(x))\lambda \end{pmatrix}},}</annotation></semantics></math><img src=$

où ${\displaystyle H <semantics><mrow><mstyle><mi>H</mi></mstyle></mrow><annotation>{\displaystyle H}</annotation></semantics></math><img src=$ ${\displaystyle B(x,\mu ) <semantics><mrow><mstyle><mi>B</mi><mo>(</mo><mi>x</mi><mo>,</mo><mi>μ</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle B(x,\mu )}</annotation></semantics></math><img src=$ ${\displaystyle \operatorname {diag} (\lambda ) <semantics><mrow><mstyle><mi>diagnostic</mi><mo>⁡</mo><mo>(</mo><mi>λ</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle \operatorname {diag} (\lambda )}</annotation></semantics></math><img src=$ ${\displaystyle \lambda <semantics><mrow><mstyle><mi>λ</mi></mstyle></mrow><annotation>{\displaystyle \lambda }</annotation></semantics></math><img src=$ ${\displaystyle \operatorname {diag} (c(x)) <semantics><mrow><mstyle><mi>diagnostic</mi><mo>⁡</mo><mo>(</mo><mi>c</mi><mo>(</mo><mi>x</mi><mo>)</mo><mo>)</mo></mstyle></mrow><annotation>{\displaystyle \operatorname {diag} (c(x))}</annotation></semantics></math><img src=$ ${\displaystyle c(x) <semantics><mrow><mstyle><mi>c</mi><mo>(</mo><mi>x</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle c(x)}</annotation></semantics></math><img src=$

En raison de (1), (4) la condition

{\displaystyle \lambda \geq 0 <semantics><mrow><mstyle><mi>λ</mi><mo>≥</mo><mn>0</mn></mstyle></mrow><annotation>{\displaystyle \lambda \geq 0}</annotation></semantics></math></span><img src=

devrait être appliquée à chaque étape. Cela peut se faire en choisissant les options appropriées ${\displaystyle \alpha <semantics><mrow><mstyle><mi>α</mi></mstyle></mrow><annotation>{\displaystyle \alpha }</annotation></semantics></math><img src=$

{\displaystyle (x,\lambda ) o (x+\alpha p_{x},\lambda +\alpha p_{\lambda }). <semantics><mrow><mstyle><mo>(</mo><mi>x</mi><mo>,</mo><mi>λ</mi><mo>)</mo><mo>→</mo><mo>(</mo><mi>x</mi><mo>+</mo><mi>α</mi><msub><mi>p</mi><mrow><mi>x</mi></mrow></msub><mo>,</mo><mi>λ</mi><mo>+</mo><mi>α</mi><msub><mi>p</mi><mrow><mi>λ</mi></mrow></msub><mo>)</mo><mo>.</mo></mstyle></mrow><annotation>{\displaystyle (x,\lambda ) o (x+\alpha p_{x},\lambda +\alpha p_{\lambda }).}</annotation></semantics></math></span><img src=

x en utilisant la méthode des points intérieurs.

Types de programmes convexes résolubles par des méthodes de points intérieurs

Voici quelques cas particuliers de programmes convexes qui peuvent être résolus efficacement par des méthodes de points intérieurs.

Programmes linéaires

Considérons un programme linéaire de la forme : ${\displaystyle {\begin{aligned}\operatorname {minimize} \quad &c^{ op }x\\{ ext{subject to}}\quad &Ax\leq b.\end{aligned}}. <semantics><mrow><mstyle><mrow><mtable><mtr><mtd><mi>minimiser</mi><mspace></mspace></mtd><mtd><msup><mi>c</mi><mrow><mi>⊤</mi></mrow></msup><mi>x</mi></mtd></mtr><mtr><mtd><mrow><mtext>sous réserve de</mtext></mrow><mspace></mspace></mtd><mtd><mi>UN</mi><mi>x</mi><mo>≤</mo><mi>b</mi><mo>.</mo></mtd></mtr></mtable></mrow><mo>.</mo></mstyle></mrow><annotation>{\displaystyle {\begin{aligned}\operatorname {minimize} \quad &c^{ op }x\\{ ext{subject to}}\quad &Ax\leq b.\end{aligned}}.}</annotation></semantics></math><img src=$ ${\displaystyle b(x):=-\sum _{j=1}^{m}\ln(b_{j}-a_{j}^{T}x). <semantics><mrow><mstyle><mi>b</mi><mo>(</mo><mi>x</mi><mo>)</mo><mo>:=</mo><mo>−</mo><munderover><mo>∑</mo><mrow><mi>j</mi><mo>=</mo><mn>1</mn></mrow><mrow><mi>m</mi></mrow></munderover><mi>ln</mi><mo>⁡</mo><mo>(</mo><msub><mi>b</mi><mrow><mi>j</mi></mrow></msub><mo>−</mo><msubsup><mi>un</mi><mrow><mi>j</mi></mrow><mrow><mi>T</mi></mrow></msubsup><mi>x</mi><mo>)</mo><mo>.</mo></mstyle></mrow><annotation>{\displaystyle b(x):=-\sum _{j=1}^{m}\ln(b_{j}-a_{j}^{T}x).}</annotation></semantics></math><img src=$ ${\displaystyle b <semantics><mrow><mstyle><mi>b</mi></mstyle></mrow><annotation>{\displaystyle b}</annotation></semantics></math><img src=$ M = m (le nombre de contraintes). Par conséquent, le nombre d'étapes de Newton requises pour la méthode de suivi de chemin est O( mn ² ), et la complexité temporelle totale est O( m ^3/2n ² ).

programmes quadratiques à contraintes quadratiques

Étant donné un programme quadratique à contraintes quadratiques de la forme : ${\displaystyle {\begin{aligned}\operatorname {minimize} \quad &d^{ op }x\\{ ext{subject to}}\quad &f_{j}(x):=x^{ op }A_{j}x+b_{j}^{ op }x+c_{j}\leq 0\quad { ext{ for all }}j=1,\dots ,m,\end{aligned <semantics><mrow><mstyle><mrow><mtable><mtr><mtd><mi>minimiser</mi><mspace></mspace></mtd><mtd><msup><mi>d</mi><mrow><mi>⊤</mi></mrow></msup><mi>x</mi></mtd></mtr><mtr><mtd><mrow><mtext>sous réserve de</mtext></mrow><mspace></mspace></mtd><mtd><msub><mi>f</mi><mrow><mi>j</mi></mrow></msub><mo>(</mo><mi>x</mi><mo>)</mo><mo>:=</mo><msup><mi>x</mi><mrow><mi>⊤</mi></mrow></msup><msub><mi>UN</mi><mrow><mi>j</mi></mrow></msub><mi>x</mi><mo>+</mo><msubsup><mi>b</mi><mrow><mi>j</mi></mrow><mrow><mi>⊤</mi></mrow></msubsup><mi>x</mi><mo>+</mo><msub><mi>c</mi><mrow><mi>j</mi></mrow></msub><mo>≤</mo><mn>0</mn><mspace></mspace><mrow><mtext> pour tous </mtext></mrow><mi>j</mi><mo>=</mo><mn>1</mn><mo>,</mo><mo>…</mo><mo>,</mo><mi>m</mi><mo>,</mo></mtd></mtr></mtable></mrow></mstyle></mrow><annotation>{\displaystyle {\begin{aligned}\operatorname {minimize} \quad &d^{ op }x\\{ ext{subject to}}\quad &f_{j}(x):=x^{ op }A_{j}x+b_{j}^{ op }x+c_{j}\leq 0\quad { ext{ for all }}j=1,\dots ,m,\end{aligned}}}</annotation></semantics></math><img src=$ A _j sont des matrices semi-définies positives . Nous pouvons appliquer des méthodes de suivi de chemin avec la barrière. ${\displaystyle b(x):=-\sum _{j=1}^{m}\ln(-f_{j}(x)). <semantics><mrow><mstyle><mi>b</mi><mo>(</mo><mi>x</mi><mo>)</mo><mo>:=</mo><mo>−</mo><munderover><mo>∑</mo><mrow><mi>j</mi><mo>=</mo><mn>1</mn></mrow><mrow><mi>m</mi></mrow></munderover><mi>ln</mi><mo>⁡</mo><mo>(</mo><mo>−</mo><msub><mi>f</mi><mrow><mi>j</mi></mrow></msub><mo>(</mo><mi>x</mi><mo>)</mo><mo>)</mo><mo>.</mo></mstyle></mrow><annotation>{\displaystyle b(x):=-\sum _{j=1}^{m}\ln(-f_{j}(x)).}</annotation></semantics></math><img src=$ ${\displaystyle b <semantics><mrow><mstyle><mi>b</mi></mstyle></mrow><annotation>{\displaystyle b}</annotation></semantics></math><img src=$ M = m . La complexité de Newton est O( (m+n)n ² ), et la complexité totale d'exécution est O( m ^1/2 (m+n) n ² ).

Approximation de la norme L _p

Considérons un problème de la forme ${\displaystyle {\begin{aligned}\operatorname {minimize} \quad &\sum _{j}|v_{j}-u_{j}^{ op }x|_{p}\end{aligned}}, <semantics><mrow><mstyle><mrow><mtable><mtr><mtd><mi>minimiser</mi><mspace></mspace></mtd><mtd><mi></mi><munder><mo>∑</mo><mrow><mi>j</mi></mrow></munder><mrow><mo>|</mo></mrow><msub><mi>v</mi><mrow><mi>j</mi></mrow></msub><mo>−</mo><msubsup><mi>vous</mi><mrow><mi>j</mi></mrow><mrow><mi>⊤</mi></mrow></msubsup><mi>x</mi><msub><mrow><mo>|</mo></mrow><mrow><mi>p</mi></mrow></msub></mtd></mtr></mtable></mrow><mo>,</mo></mstyle></mrow><annotation>{\displaystyle {\begin{aligned}\operatorname {minimize} \quad &\sum _{j}|v_{j}-u_{j}^{ op }x|_{p}\end{aligned}},}</annotation></semantics></math><img src=$ ${\displaystyle u_{j <semantics><mrow><mstyle><msub><mi>vous</mi><mrow><mi>j</mi></mrow></msub></mstyle></mrow><annotation>{\displaystyle u_{j}}</annotation></semantics></math><img src=$ ${\displaystyle v_{j <semantics><mrow><mstyle><msub><mi>v</mi><mrow><mi>j</mi></mrow></msub></mstyle></mrow><annotation>{\displaystyle v_{j}}</annotation></semantics></math><img src=$ ${\displaystyle |\cdot |_{p <semantics><mrow><mstyle><mrow><mo>|</mo></mrow><mo>⋅</mo><msub><mrow><mo>|</mo></mrow><mrow><mi>p</mi></mrow></msub></mstyle></mrow><annotation>{\displaystyle |\cdot |_{p}}</annotation></semantics></math><img src=$ _p avec ${\displaystyle 1<mrow><mstyle><mn>1</mn><mo><</mo><mi>p</mi><mo><</mo><mi>∞</mi><mo>.</mo></mstyle></mrow><annotation>{\displaystyle 1<p<\infty .}</annotation></semantics></math><img src=$ M = 4 m . La complexité de Newton est O( (m+n)n ² ), et la complexité totale d'exécution est O( m ^1/2 (m+n) n ² ).

Programmes géométriques

Considérons le problème

${\displaystyle {\begin{aligned}\operatorname {minimize} \quad &f_{0}(x):=\sum _{i=1}^{k}c_{i0}\exp(a_{i}^{ op }x)\\{ ext{subject to}}\quad &f_{j}(x):=\sum _{i=1}^{k}c_{ij}\exp(a_{i}^{ op }x)\leq d_{j}\quad { ext{ for all }}j=1,\dots ,m.\end{aligned <semantics><mrow><mstyle><mrow><mtable><mtr><mtd><mi>minimiser</mi><mspace></mspace></mtd><mtd><msub><mi>f</mi><mrow><mn>0</mn></mrow></msub><mo>(</mo><mi>x</mi><mo>)</mo><mo>:=</mo><munderover><mo>∑</mo><mrow><mi>je</mi><mo>=</mo><mn>1</mn></mrow><mrow><mi>k</mi></mrow></munderover><msub><mi>c</mi><mrow><mi>je</mi><mn>0</mn></mrow></msub><mi>exp</mi><mo>⁡</mo><mo>(</mo><msubsup><mi>un</mi><mrow><mi>je</mi></mrow><mrow><mi>⊤</mi></mrow></msubsup><mi>x</mi><mo>)</mo></mtd></mtr><mtr><mtd><mrow><mtext>sous réserve de</mtext></mrow><mspace></mspace></mtd><mtd><msub><mi>f</mi><mrow><mi>j</mi></mrow></msub><mo>(</mo><mi>x</mi><mo>)</mo><mo>:=</mo><munderover><mo>∑</mo><mrow><mi>je</mi><mo>=</mo><mn>1</mn></mrow><mrow><mi>k</mi></mrow></munderover><msub><mi>c</mi><mrow><mi>je</mi><mi>j</mi></mrow></msub><mi>exp</mi><mo>⁡</mo><mo>(</mo><msubsup><mi>un</mi><mrow><mi>je</mi></mrow><mrow><mi>⊤</mi></mrow></msubsup><mi>x</mi><mo>)</mo><mo>≤</mo><msub><mi>d</mi><mrow><mi>j</mi></mrow></msub><mspace></mspace><mrow><mtext> pour tous </mtext></mrow><mi>j</mi><mo>=</mo><mn>1</mn><mo>,</mo><mo>…</mo><mo>,</mo><mi>m</mi><mo>.</mo></mtd></mtr></mtable></mrow></mstyle></mrow><annotation>{\displaystyle {\begin{aligned}\operatorname {minimize} \quad &f_{0}(x):=\sum _{i=1}^{k}c_{i0}\exp(a_{i}^{ op }x)\\{ ext{subject to}}\quad &f_{j}(x):=\sum _{i=1}^{k}c_{ij}\exp(a_{i}^{ op }x)\leq d_{j}\quad { ext{ for all }}j=1,\dots ,m.\end{aligned}}}</annotation></semantics></math><img src=$

Il existe une barrière auto-concordante avec le paramètre 2 k + m . La méthode de suivi de chemin a une complexité de Newton O( mk ² + k ³ + n ³ ) et une complexité totale O(( k+m ) ^1/2 [ mk ² + k ³ + n ³ ]).

Programmes semi-définis

Les méthodes de points intérieurs peuvent être utilisées pour résoudre les programmes semi-définis positifs.