Theoretical and Algorithmic Aspects in Semidefinite Programming.

Aspects théoriques et algorithmiques de l'optimisation semidéfinie.

Hector Ramirez-Cabrera (1)

1 SYDOCO - Dynamic systems, optimisation and optimal command

This work deals with a number of subjects on nonlinear semidefinite programming (SDP). In the first two chapters, we consider the problem from an algorithmic standpoint while in chapters 3 and 4 we study theoretical aspects, in particular, giving a perturbation analysis of the problem. In the first chapter we develop a global algorithm that extends the local S-SDP algorithm. This algorithm is based on a Han penalty function and a line search strategy. The second chapter focuses on penalty and barrier methods for solving convex semidefinite programming problems. We prove the convergence of primal and dual sequences obtained by this method. In addition, we study the two-parameter algorithm and extend results from the usual convex programming setting to the semidefinite case. In the second part, which comprises chapters 3 and 4, we are interested in the characterization of the strong regularity property in terms of second-order optimality conditions. In chapter 3, we restrict our attention to second-order cone programming problems. These are a particular instance of semidefinite programming problems and we are able to obtain a characterization in this particular case. Finally in chapter 4, we give necessary and sufficient conditionsto obtain the strong regularity property in the semidefinite case. However, its characterization in terms of second-order optimality conditions is still an open problem.

Le but de cette thèse est d'étudier des différents sujets de la programmation semidéfinie non linéaire(SDP). Ainsi, dans les deux premiers chapitres nous presentons certains aspects algorithmiques, dans les chapitres 3 et 4 nous travaillons sur des aspects théoriques comme l'analyse de perturbations de ce problème. Le premier chapitre développe un algorithme global qui étend l'algorithme local S-SDP. Cet algorithme est basé sur une fonction de pénalisation de Han et une stratégie de recherche linéaire. Le second chapitre est consacré à l'étude des méthodes de pénalisation ou fonctions barrière pour résoudre des problèmes semidéfinis convexes. Nous démontrons la convergence des suites primale et duale obtenues par cette méthode. De plus, nous étudions l'algorithme à deux paramètres en étendant les résultats connus dans le cadre restreint de la programmation convexe usuelle. Dans une deuxième partie, constituée des chapitres 3 et 4, nous nous intéressons à la caractérisation de la propriété des solutions fortement régulières en fonction des certaines conditions optimales de deuxième ordre. Ainsi, dans le troisième chapitre nous nous consacrons au problème de second-ordre, lequel est un cas particulier du problème SDP, dont on obtient cette caractérisation. Enfin dans la chapitre 4, nous donnons des conditions nécessaires et suffisantes pour la condition de régularité forte dans le cas SDP, en revanche, sa caractérisation reste un problème ouvert.

Mots clés: Nonlinear Semidefinite Programming; Strong Regularity; Penalty Methods

Mots clés: Optimisation Semidéfinie Nonlinéaire; Régularité Forte; Optimisation de Second-ordre; Méthodes de Pénalisation

Domaines: Algorithme et structure de données [cs.DS]

Hector Ramirez-Cabrera. Aspects théoriques et algorithmiques de l'optimisation semidéfinie.. Algorithme et structure de données [cs.DS]. Ecole Polytechnique X, 2005. Français. ⟨NNT : ⟩. ⟨pastel-00001048⟩