en fr Linear Conic Matrix Nearness Problems: Approaches via projections and semidefinite programming Problèmes dapproximation matricielle linéaires coniques: Approches par Projections et via Optimisation sous contraintes de semReportar como inadecuado




en fr Linear Conic Matrix Nearness Problems: Approaches via projections and semidefinite programming Problèmes dapproximation matricielle linéaires coniques: Approches par Projections et via Optimisation sous contraintes de sem - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

1 Laboratoire MIP UMR CNRS 5640

Abstract : 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 $\mathcalP$, 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 \textscHigham 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 $\mathcalP$ 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 \textscBoyle and Dykstra-s modified version of \textscVon 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 \textscBlin-s aggregation of preferences procedure using the nearest doubly stochastic matrix idea.

Résumé : 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é $\mathcalP$, 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 \textscHigham 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é $\mathcalP$ 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 \textscBoyle 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 \textscBlin en utilisant l-approximation par matrices bistochastiques.

en fr

Keywords : 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





Autor: Pawoumodom Ledogada Takouda -

Fuente: https://hal.archives-ouvertes.fr/



DESCARGAR PDF




Documentos relacionados