Nicolas Auget - Optimisation sur le cône du second ordre - Résultats

De Ensiwiki
Aller à : navigation, rechercher


Optimisation sur le cône du second ordre

Labo LJK
Equipe BIPOP
Encadrants jerome.malick@inria.fr,florent.cadoux@inria.fr

Etudiant

Auget, Nicolas

Introduction

En ingénierie, les problèmes d’optimisation apparaissent dans de nombreux domaines. L’ingénieur selon son champ de compétence cherche très souvent à maximiser ou minimiser des grandeurs (physiques,économiques ...) qui peuvent être de nature très différentes : maximiser un flux magnétique, minimiser une force de frottement, minimiser un risque, maximiser la productivité. Si la fonction mathématique sous-jacente est importante, il en est de même pour les contraintes sous lesquelles s’opère cette optimisation. On peut facilement deviner qu’un plan peut être un domaine de contrainte, mais qu’en est t-il d’un cône ? En effet, les contraintes peuvent être parfois sous la forme de cône du second ordre de dimension i, ie de la forme :

 K_i = \{ x = (x_1...x_i) \in R^i : \sqrt{x_2^2 + ... + x_n^2} \leq x_1 \}

Comme, par exemple, quand une force est astreinte à rester dans un cône de Coulomb dans les problèmes de mécanique. L’équipe de recherche BIPOP que j’ai rejoint, dont le champ de travail se situe dans la mécanique et l’interaction des solides, s’intéressent à ce type de problème. Plus surprenant, en finance, les contraintes qui sous-tendent l’optimisation d’un portefeuille ( typiquement minimisation du risque ou maximisation de l’espérance de rentabilité) font également apparaître ces cônes. Mon intérêt commun pour le monde économique et les mathématiques de l’optimisation, m’ont ainsi conduit à comprendre comment apparaissaient ces contraintes coniques. Si l'on sait bien résoudre des problèmes linéaires de type simplex, ou quadratique, avec des contraintes "simples", notre problème a besoin d'être transformé si on veut le résoudre numériquement avec MATLAB et un module existant. Des méthodes numériques existent donc, utilisant des techniques de "points intérieurs" (que l'on ne développera pas ici, typiquement la résolution avec le module SEDUMI) mais elles semblent peu performantes surtout quand on considère comme contraintes un produit cartésien de cône. Jérôme Malick a commencé le développement d'une méthode par dualité pour résoudre ce problème, dans le but notamment, d'augmenter les performances en temps de calculs. Ce Travail Encadré de Recherche a pour but de poursuivre l'étude sur le problème de minimisation d'une fonction objectif de type quadratique sur un produit de cônes. L'étude que je prolonge a été réalisée avec un seule cône, il s'agit de montrer la possibilité de son extension, à un produit cartésien de cône du second ordre. Mon approche a consisté à, tout d'abord étudier attentivement le comportement du problème résolu à 1 cône, de tester et comparer les résultats obtenus avec la dualité à ceux obtenus par des méthodes plus générales (utilisées notamment par SEDUMI, module de Matlab), et dans un second temps de prolonger l'utilisation de la dualité dans le cas de plusieurs cônes. Ce travail comporte une partie théorique concernant les propriétés des outils de la dualité dans ce problème et une partie pratique visant à tester et comparer les performances.


Eléments de pré-requis

Je décris ici le problème en jeu, et les notations du problèmes :

 
(P) \quad \min \frac{1}{2} \|x-c\|^2{
\{\begin{array}{l}
A x = b \\
x\in K_{p_{1}}\times K_{p_{2}}\times...\times K_{p_{k}}
\end{array}}


Travail réalisé

Mon travail a consisté en :

  • Reprendre le problème dans le cas d'un seul cône.
  • Comparer avec SEDUMI les résultats obtenus par dualité.
  • Etendre les résultats théoriques et numériques dans le cas du produit cartésien de cône.

Je donne ici les grandes lignes du travail réalisé, on se référera au rapport pour de plus amples détails.

Dualité

Les contraintes du problèmes formant un espace convexe fermé et la fonction duale ayant des propriétés suffisante de convexité de régularité et de coercivité, nous sommes assurés de l'existence de la solution. la fonction duale en jeu valable dans le cas générale et obtenue en dualisant la contrainte linéaire( on obtient celle pour le problème simple en réduisant le produit cartésien à un seul cône de contraintes )est la suivante:


\theta(\lambda)=-d_{K_{p{1}} \times K_{p_{2}} \times ... \times K_{p_{k}}}(p(\lambda))+ ~^t\lambda b

On peut se placer dans le cas où  \theta est régulière on a dans ce cas une expression explicite du hessien, on introduit la fonction  \delta et on a :


\delta(z) := \frac{1}{2} \|P_{K_{p{1}}\times K_{p_{2}}\times ...\times K_{p_{n}}}(z)\|^{2} 
\nabla^2\theta(\lambda) = -A(\nabla^2\delta(p(\lambda))~^tA

On connaît explictement l'expression de la projection sur le produit de cônes.

Cas à 1 cône

Dans ce cas on trouve :


\nabla^2\delta(z) = \frac{1}{\|z_{i > 1}\|}<br />


\begin{pmatrix}
\| z_{i > 1} \| & ~^t z_{i > 1} \\
z_{i > 1} & M
\end{pmatrix}

avec des notation implicites pour désignées le vecteur de taille n-1 désignant les n-1 dernière composantes de z. On obtient ensuite le hessien de \theta, M étant une matrice connue explicitement.

Cas du produit cartésien

On étend alors les résultats :


\delta(z):= \frac{1}{2} \sum_{i=1}^{k}\| P_{K}(z_{k}) \| ^2

En se plaçant dans le cas de régularité, on obtient :


\delta(z):= \frac{1}{2} \sum_{i=1}^{k}\| P_{K}(z_{k}) \| ^2


\nabla^2\delta(z)= \begin{pmatrix}
\nabla^2\delta(z_{1}) & & 0 \\
 & \ddots & \\
0 & & \nabla^2\delta(z_{k}) \\
\end{pmatrix}

On a encore une fois une expression explicite de la hessienne de \theta.

Méthodes de descente

Le but est donc de maximiser la fonction duale pour résoudre notre problème, en s'appuyant le hessien précédemment calculé. Ainsi nous utilisons principalement 3 méthodes :

  • La méthode de Newton "pure"
  • La méthode de Quasi-Newton
  • La méthode d' Inexacte Newton

Nous comparons ensuite les résultats et les performances de ces méthodes avec les résultats obtnus avec SEDUMI auquel nous aurons préalablement "passé" le problème sous une forme acceptable.

Résultats Numériques

On se référera au rapport pour les tableaux de résultats, voici les conclusions obtenues :

  • SEDUMI est battu dans la résolution de se problème par la méthodes duales.
  • La méthode Inexacte Newton est, dans notre problème, la méthode la plus efficace.



Conclusion

On a donc poursuivi avec succès l’étude à un cône, en étendant les résultats, et en dans une certaine mesure les propriétés théoriques pour le produit cartésien de cônes. On peut noter finalement quelques points à retenir :

  • le passage à Sedumi fait augmenter de façon importante les dimensions du

problème pour le solveur ce qui dégrade évidemment le temps de calcul du module.

  • il serait intéressant d’étudier les cas où la fonction duale n’est pas C2 et regarder

les propriétés du Hessien généralisé.

  • il reste maintenant à trouver quelques raffinement à l’algorithme, sur les produits

matriciels et les itérations.
Je remercie ici l’équipe BIPOP, notamment Jérôme Malick et Floran Cadoux pour leur encadrement et leur soutien. Ce stage a été très enrichissant tant d’un point de vue personnel que pédagogique, cette une expérience positive que je referais volontiers.

Références

  • Boyd et Vandenberghe , Convex Optimization , Cambridge University Press.
  • Nocedal et Wright, Numerical Optimiztion, Springer.
  • Malick, Dual Newton methods to solve second order least squares.
  • Fylstra, Introducing Convex and Conic Optimization for the Quantitative Finance Professional , Wilmott magazine.

Documents additionnels