Conservatisme (optimisation)

En optimisation, introduire du conservatisme dans un problème d'optimisation $A$ consiste à introduire un problème d'optimisation $B$, généralement plus simple à résoudre que $A$, et dont la résolution permet d'obtenir une solution admissible (éventuellement sub-optimale) au problème initial $A$. On dit alors que $B$ est une version conservative de $A$. L'absence de solution à $B$ ne permet cependant pas de conclure sur la faisabilité du problème initial $A$. Pour le dire autrement, une solution admissible au problème $B$ implique l'existence d'une solution admissible au problème $A$, mais la réciproque n'est pas vérifiée.

Définition

Le conservatisme est une notion dont la définition formelle est souvent relative à son contexte d'utilisation. Par exemple, si $B_{1}$ et $B_{2}$ sont deux problèmes d'optimisation de même dimension cherchant à résoudre un même problème initial $A$, on dit généralement que $B_{1}$ est moins conservatif que $B_{2}$ si ${\mbox{sol}}(B_{1})$, l'ensemble des solutions admissibles de $B_{1}$, occupe un volume plus grand que ${\mbox{sol}}(B_{2})$, l'ensemble des solutions admissibles de $B_{2}$. Formellement :

$B_{1}{\mbox{ est moins conservatif que }}B_{2}\Longleftrightarrow {\mbox{Vol}}({\mbox{sol}}(B_{1}))\geq {\mbox{Vol}}({\mbox{sol}}(B_{2}))$

En particulier, cela ne signifie pas forcément que résoudre $A$ via $B_{1}$ soit toujours avantageux par rapport à $B_{2}$ suivant où sont situés les ensembles ${\mbox{sol}}(B_{1})$ et ${\mbox{sol}}(B_{2})$. De plus, la comparaison en terme de volume n'a pas forcément de sens dans tous les contextes (par exemple ce volume est toujours nul en optimisation discrète). On compare parfois uniquement les ensembles solutions en terme d'inclusion, soit ${\mbox{sol}}(B_{2})\subseteq {\mbox{sol}}(B_{1})$. Dans ce cas, on peut dire que le problème $B_{1}$ relaxe le conservatisme du problème $B_{2}$.

Exemple

Problème A — On cherche $x\in \mathbb {R} ^{n}$ tel que l'inégalité matricielle suivante soit vérifiée pour tout $\lambda \in \mathbb {R} _{\geq 0}^{m}$ tel que $\lambda _{1}+\dots +\lambda _{m}=1$$\sum _{i=1}^{m}\sum _{j=1}^{m}\lambda _{i}\lambda _{j}F_{ij}(x)\prec 0$

avec $F_{ij}$ des fonctions affines à valeur dans l'espace des matrices symétriques réelles, c'est-à-dire de la forme

$F_{ij}(x)=E_{ij0}+\sum _{k=1}^{n}E_{ijk}x_{k}$

où $E_{ijk}=E_{ijk}^{\top }\in \mathbb {R} ^{p\times p}$ pour tout $(i,j,k)$.

Ce problème A est connu pour être particulièrement difficile à résoudre. Il est néanmoins possible d'introduire du conservatisme dans sa formulation afin de le résoudre à l'aide de techniques d'optimisation SDP, par exemple en trouvant un tel $x$ solution via les problèmes B1, B2 ou B3.

Problème B1 — On cherche $x\in \mathbb {R} ^{n}$ tel que l'inégalité matricielle linéaire suivante soit vérifiée pour tout $1\leq i\leq j\leq m$ $F_{ij}(x)+F_{ji}(x)\prec 0$

Problème B2 — On cherche $x\in \mathbb {R} ^{n}$ tel que l'inégalité matricielle linéaire suivante soit vérifiée pour tout $1\leq i\leq j\leq m$ ${\frac {2}{m-1}}F_{ii}(x)+F_{ij}(x)+F_{ji}(x)\prec 0$

Problème B3 — On cherche $x\in \mathbb {R} ^{n}$ et $G_{ij}$ tels que $G_{ij}=G_{ji}^{\top }$ et que les inégalités matricielles linéaires suivantes soient vérifiées pour tout $1\leq i\leq j\leq m$ ${\begin{aligned}F_{ij}(x)+F_{ji}(x)+G_{ij}+G_{ji}&\prec 0\\\left({\begin{array}{ccc}G_{11}&\dots &G_{1m}\\\vdots &&\vdots \\G_{m1}&\dots &G_{mm}\end{array}}\right)&\succ 0\end{aligned}}$

Trouver une solution à un seul de ces problèmes d'optimisation fournit une solution au problème A. En général, le problème d'optimisation B3 est considéré comme moins conservatif que le problème d'optimisation B2, lui-même étant moins conservatif que le problème d'optimisation B1. Dans tous les cas, ne pas trouver de $x$ solution aux problèmes B1, B2 et B3 n'exclut pas qu'une solution existe au problème A.

Voir aussi

• Technique de relaxation (optimisation)