Analysis and Optimization of Problems with autocorrelation constraints

Analyse et optimisation de problèmes sous contraintes d'autocorrélation

Marc Fuentes (1)

1 IMT - Institut de Mathématiques de Toulouse UMR5219

In this work, we study how to take into account, from the convex analysis and optimization viewpoint, constraint sets of the following type : sets of vectors whose components are autocorrelations lags of finite discrete signals. A set of vectors with autocorrelated components turns out to be a convex cone, for which we etablish many basic properties such as : smoothness or not of the boundary, structure of faces, acuteness, expression of the polar cone, evaluation of the normal cone at a point, etc. Next, we propose some algorithms to solve optimization problems where this type of constraint set appears ; in particular we consider the problem of projecting a point on the convex cone of vectors with autocorrelated constraints. For these purposes, we study three different algorithms : an interior point method, one using alternating projections, and one via a non-convex relaxation of the original problem. Finally, we suggest extensions to the bi-dimensional signals case ; we outline the main difficulties which therefore appear : various possible new definitions, non-convexity of occuring problems, and increase in the computational complexity of the algorithmic procedures.

Dans ce travail de thèse, nous étudions, dans un contexte d'analyse convexe et d'optimisation, la prise en compte des contraintes dites d'autocorrélation, c'est-à-dire : nous considérons les situations où les vecteurs représentant les variables à optimiser sont contraintes à être les coefficients d'autocorrélation d'un signal discret à support fini. Cet ensemble des vecteurs à composantes autocorrélées se trouve être un cône convexe ; nous essayons d'en établir le plus de propriétés possibles : concernant sa frontière (lisse/polyédrale), ses faces, l'acuité, l'expression du cône polaire, l'évaluation du cône normal en un point, etc. Ensuite, nous étudions divers algorithmes pour résoudre des problèmes d'optimisation où le cône des vecteurs à composantes autocorrélées entre en jeu. Notre principal objet d'étude est le problème de la projection sur ce cône, dont nous proposons la résolution par trois algorithmes différents : algorithmes dits de suivi de chemin, celui des projections alternées, et via une relaxation non-convexe. Enfin, nous abordons la généralisation de la situation d'autocorrélation au cas de signaux bi-dimensionnels, avec toute la complexité que cela engendre : multiples définitions possibles, non-convexité des problèmes résultants, et complexité calculatoire accrue pour les algorithmes.

Mots clés: Analyse Convexe; Optimisation; Autocorrélation; Polynômes Trigonométriques Positifs; Optimisation semi-définie positive.; Optimisation semi-définie positive

Mots clés: Convex analysis; Optimization; Nonnegative Trigonometric Polynomials; SDP programming

Domaines: Mathématiques [math]

Marc Fuentes. Analyse et optimisation de problèmes sous contraintes d'autocorrélation. Mathématiques [math]. Université Paul Sabatier - Toulouse III, 2007. Français. ⟨NNT : ⟩. ⟨tel-00195013⟩