Résoudre les problèmes SDP de grande taille devient néanmoins très vite difficile avec ces méthodes de points intérieurs qui ont de bonnes propriétés théoriques mais qui s'essouflent en pratique quand la taille des problèmes augmente. Par exemple, les problèmes d'optimisation polynomiale donnent naissance [L09] à des problèmes SDP de très grande taille, vite hors de portée des solveurs classiques. Pourtant de tels problèmes ont de nombreuses applications en automatique, voir par exemple [HG05].
Nous souhaitons développer de nouvelles approches pour résoudre ces problèmes SDP. L'idee est d'éviter les coûteux calculs d'algèbre linéaire, mais au lieu de reformuler les problèmes pour améliorer le conditionnemment, nous souhaitons explorer des nouveaux schémas algorithmiques. De nouveau outils d'optimisation SDP sont en effet apparus récemment : méthodes de moindres carrés semi-définis [M04,QS06], méthodes de points frontières [MPRW09] et méthodes par régularisation [PRW06]. L'approche (à base de projections) est radicalement différente des précédentes et offre ainsi de nouvelles perspectives : la modélisation des problèmes semblent être moins directe, mais les solveurs apparaissent plus robustes et plus efficaces. Ces algorithmes ont déjà été utilisés avec succès dans d'autres disciplines (en combinatoire notamment, voir [MR09]), et dans des applications industrielles (en finance notamment, voir [QS06]). Dans le cadre du projet, de premiers résultats très encourageants sont présentés dans [HM10] pour calculer la décomposition d'un polynôme en somme de carrés (décomposition SOS), cf. ci-dessous.
Ils apparaissent partout où une contrainte de positivité intervient dans un problème avec des données polynomiales ou rationelles. Les cônes de polynômes positifs sont convexes, et par conséquence, les problèmes d'optimisation conique sur les polynômes positifs sont convexes dans un certain sens. Néanmoins, ils sont NP-durs en général, parce que les cônes de polynômes positifs sont difficiles à decrire, à l'exception des polynômes univariés et des quartiques en deux variables, dont une description simple passe par les LMI [L09,L09b].
La facilité de la description du cône des polynômes positifs univariés a une multitude d'applications en commande et dans la théorie des systèmes dynamiques en général. Un élargissement de la classe de polynômes positifs faciles à decrire, même sur les polynômes bivariés seulement, entrainerait un grand progrès dans les algorithmes d'optimisation en commande en rendrait faisable beaucoup de problèmes aujourd'hui considérés comme durs. Il est alors de grande importance d'avancer sur la description par LMI des cônes de polynômes positifs.
Un certificat de positivité pour un polynôme est sa représentabilité comme une somme de carrés (SOS), cf. [N00,L01,P03]. Par conséquence, l'ensemble de sommes de carrés, qui est lui-même un cône convexe, est une approximation intérieure du cône des polynômes positifs. Les cônes SOS possèdent une représentation canonique par LMI, ce qui en fait un outil principal pour le traitement de problèmes d'optimisation conique sur les polynômes positifs. En effet, les cônes de polynômes positifs pour lesquels une description par LMI est connue sont exactement ceux qui coincident avec leur cône de sommes de carrés correspondant.
Nous proposons d'utiliser une nouvelle approche au problème de la description des cônes de polynômes positifs, celle des cônes abstraits. Ici il s'agit de l'observation que le même cône positif, vu comme ensemble abstrait de points dans R^N, est égal à une multitude de cônes concrets de polynômes positifs. Cet ensemble de cônes équivalents est infini et possède une structure naturelle, notamment un ordre partiel. A chaque cône concret correspond un cône SOS, ce qui mène à une hiérarchie infinie, induite par l'ordre partiel, des approximations par LMI du cône abstrait sous considération. Une première étude a montré que cette hiérarchie de cônes SOS peut avoir un plus grand pouvoir descriptif que les hiérarchies utilisées aujourd'hui [H09].
Nous proposons d'étudier plusieurs aspects de la nouvelle approche. La question qui nous semble la plus difficile est de decrire les cônes de polynômes positifs qui possèdent une description par LMI exacte dans le cadre proposé. Une étude préliminaire a montré que la reponse à cette question est non-triviale, dans le sens que notre approche fournit des descriptions par LMI qui ne peuvent pas être générées par les méthodes liées aux sommes de carrés utilisées aujourd'hui.
Une autre question concerne le conditionnement des problèmes semi-définis construits sur les approximations SOS proposées. Il est connu que les hiérarchies d'approximations utilisées aujourd'hui mènent à des problèmes en général mal conditionnés. Avec notre approche, nous envisageons de construire des approximations de type SOS qui ont des meilleures propriétés numériques. Les méthodes principales de cette étude seront issues de la théorie des réseaux arithmétiques.
La troisième question porte sur des bornes de l'erreur de l'approximation et sur l'exactitude asymptotique de l'hiérarchie proposée. Ici nous envisageons d'utiliser des méthodes de la théorie des moments [L09].
Finalement, nous proposons d'appliquer les résultats pour étudier la représentabilité par LMI des ensembles semi-algèbriques [N06,HV07].
Juin 2011