Conservatisme (optimisation)

Pour les articles homonymes, voir Conservatisme (homonymie).

Cet article est une ébauche concernant les mathématiques.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

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

## Définition

[modifier | modifier le code]

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

B 1 est moins conservatif que B 2 ⟺ Vol ( sol ( B 1 ) ) ≥ Vol ( sol ( B 2 ) ) {\displaystyle 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 {\displaystyle A} via  B 1 {\displaystyle B_{1}} soit toujours avantageux par rapport à  B 2 {\displaystyle B_{2}} suivant où sont situés les ensembles  sol ( B 1 ) {\displaystyle {\mbox{sol}}(B_{1})} et  sol ( B 2 ) {\displaystyle {\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  sol ( B 2 ) ⊆ sol ( B 1 ) {\displaystyle {\mbox{sol}}(B_{2})\subseteq {\mbox{sol}}(B_{1})} . Dans ce cas, on peut dire que le problème  B 1 {\displaystyle B_{1}} relaxe le conservatisme du problème  B 2 {\displaystyle B_{2}} .

## Exemple

[modifier | modifier le code]

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

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

F i j ( x ) = E i j 0 + ∑ k = 1 n E i j k x k {\displaystyle F_{ij}(x)=E_{ij0}+\sum _{k=1}^{n}E_{ijk}x_{k}}

où  E i j k = E i j k ⊤ ∈ R p × p {\displaystyle E_{ijk}=E_{ijk}^{\top }\in \mathbb {R} ^{p\times p}} pour tout  ( i , j , k ) {\displaystyle (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 {\displaystyle x} solution via les problèmes B1, B2 ou B3[3],[4].

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

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

Problème B3 -- On cherche  x ∈ R n {\displaystyle x\in \mathbb {R} ^{n}} et  G i j {\displaystyle G_{ij}} tels que  G i j = G j i ⊤ {\displaystyle G_{ij}=G_{ji}^{\top }} et que les inégalités matricielles linéaires suivantes soient vérifiées pour tout  1 ≤ i ≤ j ≤ m {\displaystyle 1\leq i\leq j\leq m} F i j ( x ) + F j i ( x ) + G i j + G j i ≺ 0 ( G 11 … G 1 m ⋮ ⋮ G m 1 … G m m ) ≻ 0 {\displaystyle {\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 {\displaystyle x} solution aux problèmes B1, B2 et B3 n'exclut pas qu'une solution existe au problème A.

## Voir aussi

[modifier | modifier le code]

* Technique de relaxation (optimisation)

## Notes et références

[modifier | modifier le code]

1. ↑ (en) Ernst Roos et Dick den Hertog, « Reducing Conservatism in Robust Optimization », INFORMS Journal on Computing, 12 mai 2020 (ISSN 1091-9856 et 1526-5528, DOI 10.1287/ijoc.2019.0913, lire en ligne, consulté le 17 septembre 2024)
2. ↑ a et b (en) Aharon Ben-Tal, Laurent El Ghaoui et Arkadi Nemirovski, « Robust Optimization », Princeton University Press, 31 décembre 2009 (DOI 10.1515/9781400831050, lire en ligne, consulté le 17 septembre 2024)
3. ↑ (en) A. Kruszewski, A. Sala, T.M. Guerra et C. Arino, « A Triangulation Approach to Asymptotically Exact Conditions for Fuzzy Summations », IEEE Transactions on Fuzzy Systems, vol. 17, no 5, octobre 2009, p. 985–994 (ISSN 1063-6706 et 1941-0034, DOI 10.1109/tfuzz.2009.2019124, lire en ligne, consulté le 17 septembre 2024)
4. ↑ (en) A. Kruszewski, A. Sala, T. M. Guerra et C. Arino, « Sufficient and asymptotic necessary conditions for the stabilization of Takagi-Sugeno model », IFAC Proceedings Volumes, 3rd IFAC Workshop on Advanced Fuzzy and Neural Control, vol. 40, no 21, 1er janvier 2007, p. 55–60 (ISSN 1474-6670, DOI 10.3182/20071029-2-FR-4913.00010, lire en ligne, consulté le 17 septembre 2024)

* Portail des mathématiques

*[(en)]: Langue : anglais
*[vol.]: volume
*[no]: numéro
*[p.]: pages
*[1er]: premier