Linear Conic Matrix Nearness Problems: Approaches via projections and semidefinite programming

Problèmes d'approximation matricielle linéaires coniques: Approches par Projections et via Optimisation sous contraintes de semi-définie positivité

Pawoumodom Ledogada Takouda (1)

1 MIP - Mathématiques pour l'Industrie et la Physique

In this thesis, we consider the study of the so-called linear conic nearness problems and the derivation of differents numerical approachs for solving them. We focused our attention on the projections based approach and the SemiDefinite Programming (SDP) one. In a normed vector space of matrices, a matrix nearness problem consists in finding a matrix having a known property $\mathcal(P)$, that is nearest, according to the space's norm, to a given matrix $A$. These problems, which appear in numerous differents fields, have been studied by \textsc(Higham) who proposed the following three-step solving procedure : existence and unicty of (optimal) solutions, caracterisation and explicit form of solutions, if possible, efficients algorithms for computing these solution. We have taken an euclidean framework, and considered the cases where the set of matrices having property $\mathcal(P)$ is described by affine and conic (convex) constraints. We call those problems (\it linear conic matrix nearness problems). We have taken as examples two nearness problems corresponding to convex sets well known in Convex Analysis for their "good" structure, but where an explicit solution of the nearness problem is hard. The first of these example is motivated by problems from Operations Researchs and Quantum Mechanics. It consists in finding the nearest doubly stochastic matrix to a given square matrix. The second one is the problem of calibrating a correlation matrice. This have a major importance in the analysis of the financial risk taken with a given choice of a stock asset. We study and derive for these linear conic matrix nearness problems two differents approachs. The first is primal : it consists in rewritting the problem as the one of finding a projection onto a convex set which is the intersection of "simple" convexs, meaning projections onto are easy. It allow us to propose an alternating projections algorithm, inspired by \textsc(Boyle and Dykstra)'s modified version of \textsc(Von Neumann)'s classical algorithm. The second is primal-dual, and is in the lineage of the recents advances in SemiDefinite Programming. It consists in deriving an interior point algorithm, within a new framework where Gauss-Newton search directions, computed by preconditionned conjugated gradients, are used insead of Newton ones and a crossover technique is introduced at the end of the algorithm leading asymptotically to a superlinear convergence. Numerical tests are performed as an illustration of the differents approachs and show the comparison between them from differents points of view. As an application, we present a generalization of \textsc(Blin)'s aggregation of preferences procedure using the nearest doubly stochastic matrix idea.

Dans cette thèse, nous considérons l'étude et la mise en \oe uvre de différentes approches numériques de résolution de problèmes dits d'approximation linéaire conique, en nous concentrant sur les approches par projections et par optimisation sous contraintes de semi-définie positivité. Un problème d'approximation matricielle consiste dans un espace normé de matrices à chercher la matrice ayant une certaine propriété $\mathcal(P)$, la plus proche au sens de la norme de l'espace, d'une matrice $A$ donnée. Ces problèmes apparaissent dans différents domaines, et ont été étudiés par \textsc(Higham) qui en propose un procédure de résolution consistant en les trois points suivants : existence et unicité des solutions, caractérisation et solution explicite éventuelles, algorithmes efficaces de calculs de ces solutions. Nous nous plaçons dans un cadre euclidien, et considérons les cas où les matrices vérifiant la propriété $\mathcal(P)$ forment un ensemble convexe déterminé par des contraintes affines et coniques. Nous parlons alors d'(\it approximation matricielle linéaire conique). Nous prenons comme exemples d'application deux problèmes d'approximation correspondant à des ensembles connus en Analyse convexe pour leur "bonne" structure, mais pour lesquels la résolution explicite d'un problème d'approximation s'avère ardu. Le premier exemple provient d'applications en Recherche opérationnelle ou en Mécanique quantique, et consiste à trouver la matrice bistochastique la plus proche d'une matrice donnée. Le second problème est celui de la calibration de matrices de corrélation, qui est d'une importance majeure en analyse du risque financier encouru avec un choix de portefeuille d'actions boursières donné. Nous étudions et mettons en \oe uvre pour les problèmes d'approximation matricielle linéaire conique deux approches de nature différente. La première est primale : elle consiste à interpréter le problème comme étant celui de la projection sur un convexe qui est l'intersection de convexes plus simples sur lesquels les projections sont faciles. Cela nous permet de proposer un algorithme de projections alternées, inspiré des modifications apportées par \textsc(Boyle et Dykstra) à l'algorithme classique de Von Neumann. La seconde est de type primal-dual, et s'inscrit dans la lignée des récentes avancées obtenues en optimisation sous contraintes de semi-définie positivité ((\it Semidefinite Programming)). Elle consiste en la mise en \oe uvre d'un algorithme de points intérieurs, en utilisant une démarche novatrice consistant en l'utilisation de directions de recherches de Gauss-Newton, obtenues par gradients conjugués et en l'introduction en fin d'algorithme d'une étape de "crossover" permettant d'obtenir asymptotiquement de la convergence superlinéaire. Nous présentons pour chacun des problèmes d'approximation pris en exemples des résultats numériques illustrant les différentes approches ci-dessus et les comparant entre elles de différents points de vue. En application, nous proposons aussi une généralisation de la procédure d'agrégation de préférences de \textsc(Blin) en utilisant l'approximation par matrices bistochastiques.

Mots clés: Matrix nearness problem; Projection onto convex sets; Projections algorithms on convexs; Doubly stochatic matrices; Aggregation of Preferences; SemiDefinite Programming; Interiors points methods; correlation matrices; Preconditionned Conjugated Gradients

Mots clés: Approximation matricielle; Projections sur des convexes; algorithmes de projections sur des convexes; matrices bistochastiques; agrégation de préférences; optimisation sous contraintes de semi-définie positivité; méthodes de points interieurs; matrices de corrélations; méthodes de gradients conjugués préconditionnés

Domaines: Mathématiques [math]

Pawoumodom Ledogada Takouda. Problèmes d'approximation matricielle linéaires coniques: Approches par Projections et via Optimisation sous contraintes de semi-définie positivité. Mathématiques [math]. Université Paul Sabatier - Toulouse III, 2003. Français. ⟨NNT : ⟩. ⟨tel-00005469⟩