Optimisation convexe sous contraintes

Nous vous rappelons que, afin de garantir l'accès de tous les inscrits aux salles de réunion, l'inscription aux réunions est gratuite mais obligatoire.

Inscriptions closes à cette réunion.

Inscriptions

44 personnes membres du GdR ISIS, et 40 personnes non membres du GdR, sont inscrits à cette réunion.
Capacité de la salle : 160 personnes.

Annonce

 

De nombreuses problématiques de traitement du signal et de l'image ont récemment gagné en performances grâce aux outils d'optimisation convexe. Ces outils permettent de gérer des fonctions non-lisses, des fonctions non finies, ou encore des contraintes de type positivité, support fini ou parcimonie structurée. Une grande activité de recherche émane de ces sujets et de nombreuses questions sont soulevées notamment face à l'augmentation de la dimension des problèmes, la diversité des contraintes à respecter et l'adéquation avec les ressources de calcul disponibles. 

Cette journée "optimisation convexe sous contraintes", organisée par le thème A du GdR ISIS, sera consacrée aux dernières avancées relatives à la gestion de contraintes en optimisation convexe. En effet, la mise en oeuvre d'un algorithme d'optimisation efficace dépendra du type de contraintes qui doivent être prises en compte, de leur nombre mais également des propriétés des autres fonctions impliquées dans le critère. Parmi les méthodes permettant de gérer des contraintes on peut citer les méthodes de points intérieurs, la pénalité extérieure, les méthodes de projections alternées ou les méthodes proximales. Les avancées récentes d'un point de vue méthodologique ainsi que les enjeux applicatifs seront présentés durant cette journée.

Les exposés tutoriels seront donnés par :

- Paul Armand (XLIM, Univ. de Limoges) : méthodes de points intérieurs,

- Jean-Christophe Pesquet (LIGM, Univ. Paris-Est): méthodes proximales,

- Eric Thiébaut (Centre de Recherche Astrophysique de Lyon) : reconstruction sous contraintes en imagerie.

Les membres du GdR sont priés de s’inscrire sur le site http://gdr-isis.fr/. Toute autre personne intéressée par cette journée est invitée à contacter les organisateurs : Saïd Moussaoui (said.moussaoui@irccyn.ec-nantes.fr) et Nelly Pustelnik (nelly.pustelnik@ens-lyon.fr).

 

Programme

09h45 : Accueil

10h00 : Eric Thiébaut / Ferréol Soulez (CRAL, Lyon) --  Résolution de problèmes de reconstruction sous contrainte en imagerie.

10h50 : Jean-François Giovannelli  (IMS, Bordeaux) --  Pénalité L2+L1 et algorithme ADMM en synthèse de Fourier et application à la radio-héliographie.

11h10 : Simon Henrot (CRAN, Nancy) --   Restauration positive d'images hyperspectrales avec préservation des contours.

11h30  : Pause

11h50 : Jean-Christophe Pesquet (LIGM, Univ. Paris-Est) --   Tutoriel sur les méthodes proximales.

12h40 :  Repas

13h50 : Giovanni Chierchia  (Télécom ParisTech) --  Décomposition proximale épigraphique: application à la modélisation de réponses impulsionnelles et à la       restauration d'images.

14h10 : Sira Ferradans (CEREMADE, Univ. Paris-Dauphine)  --   Regularized Optimal Transport.

14h30 : Claire Boyer (Institut Mathématiques de Toulouse) --  An algorithm for variable density sampling and constrained acquisition by blocks of measurements.

14h50 : Pause

15h10 : Paul Armand (XLIM, Univ. Limoges) --   Méthodes primales-duales pour l'optimisation non linéaire

16h00 : Emilie Chouzenoux (LIGM, Univ. Paris-Est) --   Algorithme primal-dual de points intérieurs pour l'estimation des cartes d'abondances en imagerie hyperspectrale.

16h20  :  Pause 

16h40 : Zaïd Harchaoui (INRIA Rhône-Alpes)  --   Conditional gradient algorithms for smooth convex optimization with atomic-norm constraints.

17h00 : Raouia Masmoudi (ETIS/ENSEA, Univ. Cergy Pontoise) --   Problème de minimisation de puissance sous contraintes : Cas du canal radio cognitif.

17h20 : Marcello Pereyra (Univ. Bristol, UK) --  Proximal Markov chain Monte Carlo algorithms.

17h40  : Discussion

18h00  : Fin de la journée

Résumés des contributions

 

Paul ARMAND (XLIM, Univ. Limoges)

Titre : Méthodes primales-duales pour l'optimisation non linéaire 

Résumé : Nous présentons les méthodes primales-duales pour la résolution numérique de problèmes d'optimisation non linéaire. Nous présentons en particulier une formulation de ces méthodes à partir de l'introduction d'un lagrangien augmenté et montrons comment ce type d'approche introduit une régularisation naturelle de ces méthodes et permet ainsi la résolution de certains problèmes dégénérés.

 

Claire BOYER (Institut Mathématiques de Toulouse)

Titre : An algorithm for variable density sampling and constrained acquisition by blocks of measurements

Auteurs : Claire Boyer, Pierre Weiss et Jérémie Bigot

Résumé : Reducing acquisition time is of fundamental importance in various imaging modalities. A typical example is Magnetic Resonance Imaging where faster acquisitions could drastically improve the patient comfort, the time and space resolution or reduce the (huge) acquisition costs. The concept of variable density sampling provides a nice framework to reduce the acquisition times. It was justified recently from a theoretical point of view in the compressed sensing (CS) literature. Unfortunately, the sampling schemes suggested by current CS theories are often of little relevance since they do not take the acquisition constraints into account. For instance, a typical constraint met in MRI is that measurements should be contiguous in the Fourier domain. In this talk, we will propose a numerical method to perform variable density sampling with block constraints. Our main contribution is to propose a new way to draw the blocks in order to imitate CS strategies based on isolated measurements. The basic idea is to minimize a tailored distance between a probability defined on the set of isolated measurements and a probability defined on a set of blocks of measurements. This problem turns out to be a convex problem in high dimension. Our second contribution is to define an efficient minimization algorithm based on Nesterov accelerated gradient descent in metric spaces. We study carefully the choice of the metrics and of the prox function. We will conclude the talk by giving some practical results.

 

Giovanni CHIERCHIA (Télécom ParisTech)  

Titre : Décomposition proximale épigraphique: application à la modélisation de réponses impulsionnelles et à la restauration d'images

Auteurs : Giovanni Chierchia, Nelly Pustelnik, Jean-Christophe Pesquet et Béatrice Pesquet-Popescu

Résumé : Dans cette présentation, nous nous intéressons à la gestion de contraintes convexes non-linéaires à l'aide d'algorithmes proximaux et de projections épigraphiques. La classe des contraintes convexes qui nous intéresse correspond aux contraintes pouvant s'exprimer comme une somme de fonctions convexes évaluées sur des blocs (ces derniers pouvant présenter des recouvrements). Pour de telles contraintes, l'opérateur de projection associé n'a en général pas de forme explicite. Dans ce travail, nous contournons cette difficulté en décomposant la contrainte en un ensemble de contraintes épigraphiques et une contrainte de demi-espace. La difficulté réside alors dans le calcul de la projection épigraphique dont nous proposons des formes explicites pour des fonctions de types distances et normes. Les performances de l a méthode proposée seront évaluées sur un exemple de modélisation de réponse impulsionnelle ainsi que sur un exemple de restauration d'images.

Emilie CHOUZENOUX (LIGM, Univ. Paris-Est)

Titre : Algorithme primal-dual de points intérieurs pour l'estimation des cartes d'abondances en imagerie hyperspectrale

Abstract : L'estimation des cartes d'abondances en imagerie hyperspectrale nécessite de résoudre un problème d'optimisation sous des contraintes de non-négativité et d'additivité. Nous nous plaçons dans le cadre où les spectres des composants présents au sein de l'image ont été préalablement estimés par un algorithme d'extraction des pôles de mélange et nous proposons un algorithme rapide de points intérieurs de type primal-dual pour l'estimation des cartes. Cet algorithme présente l'avantage de pouvoir traiter un large choix de critères et de contraintes. Un second avantage est son fort potentiel de parallélisation. Des exemples sur des données synthétiques et réelles illustrent les performances de cet algorithme.

Sira FERRADANS  (CEREMADE, Univ. Paris-Dauphine)

Titre : Regularized Optimal Transport 
 
Auteurs : Sira Ferradans, Nicolas Papadakis, Julien Rabin, Gabriel Peyré, and Jean-François Aujol

Résumé : We introduce a generalization of discrete Optimal Transport that includes a regularity penalty and a relaxation of the bijectivity constraint. The corresponding transport plan is solved by minimizing an energy which is a convexication of an integer optimization problem. We propose to use a proximal splitting scheme to perform the minimization on large scale imaging problems. For un-regularized relaxed transport, we show that the relaxation is tight and that the transport plan is an assignment. In the general case, the regularization prevents the solution from being an assignment, but we show that the corresponding map can be used to solve imaging problems. We show an illustrative application of this discrete regularized transport to color transfer between images. This imaging problem cannot be solved in a satisfying manner without relaxing the bijective assignment constraint because of mass variation across image color palettes. Furthermore, the regularization of the transport plan helps remove colorization artifacts due to noise amplication.

  

Jean-François GIOVANNELLI (IMS, Bordeaux)

Titre : Pénalité L2+L1 et algorithme ADMM en synthèse de Fourier et application à la radio-héliographie

Résumé : Le travail présenté est motivé par une application en radio-héliographie (imagerie du soleil dans les longueurs d'onde radio) par interférométrie (à partir d'un réseau d'antenne). Dans cette modalité, la reconstruction des images pose un problème de synthèse de Fourier ou de déconvolution. Par ailleurs, les objets d'intérêt présentent la particularité de posséder une composante impulsionnelle et une composante étendue superposées. Nous présentons une méthode permettant la reconstruction de deux cartes reposant sur une double pénalité convexe : un terme L1 pour la composante impulsionnelle et un terme de L2 pour la composante étendue. A cela s'ajoutent des contraintes de positivité et de support. L'optimisation repose sur un algorithme de lagrangien augmenté et une desc ente de alternée (ADMM). Les résultats présentés montrent les capacités à la fois de séparation des deux composantes et de sur-résolution de la composante impulsionnelle.

Publication -- Le travail a été publié il y a quelques temps déjà dans J.-F. Giovannelli and A. Coulais, "Positive deconvolution for superimposed extended sources and point sources", Astronomy and astrophysics, vol. 439, pp. 401-412, 2005 et il est disponible là : http://giovannelli.free.fr/Papers/AetAParu.pdf

 

Zaïd HARCHAOUI (INRIA Rhône-Alpes)

Titre : Conditional gradient algorithms for smooth convex optimization with atomic-norm constraints

Résumé : We consider high-dimensional convex optimization problems arising in machine learning, that enjoy a particular constraint structure, namely that constraints can be described with atomic-decomposition norms. We describe a family of algorithms, akin to the conditional gradient algorithm, suitable for large-scale problems, and derive their finite-time convergence guarantees. Experimental results are presented on two large-scale real-world datasets.

 
Simon HENROT (CRAN, Nancy)

Titre : Restauration positive d'images hyperspectrales avec préservation des contours 

Auteurs : Simon Henrot, Charles Soussen, Saïd Moussaoui, David Brie

Résumé : Nous considérons un problème de restauration d'images hyperspectrales sous contrainte de positivité, en s'attachant à préserver les contours de l'image. L'estimée est obtenue par minimisation contrainte d'un critère convexe incorporant des informations a priori sur la régularité spatiale et spectrale de l'image. Nous présentions dans un travail précédent une méthode rapide de restauration avec régularisation quadratique. Nous proposons ici d'adapter cette technique à des termes de régularisation convexes non quadratiques. Les performances de l'algorithme sont validées par des résultats sur des images réelles de microscopie en fluorescence de biocapteurs bactériens.

Raouia MASMOUDI (ETIS/ENSEA, Univ. Cergy Pontoise)

Titre : Problème de minimisation de puissance sous contraintes : Cas du canal radio cognitif

Auteurs : Raouia Masmoudi, E. Veronica Belmega , Inbar Fijalkow, Noura Sellami

Résumé : Dans cet exposé, nous étudions un problème d?optimisation convexe sous contraintes. Plus spécifiquement, nous nous intéressons au problème de minimisation de puissance à travers plusieurs bandes de fréquences orthogonales dans le cadre des réseaux de communications numériques "green".
Nous considérons un canal radio cognitif composé de plusieurs utilisateurs primaires, les propriétaires du spectre fréquentiel, qui autorisent l'accès au spectre à un utilisateur opportuniste dit secondaire sous réserve de ne pas gêner les communications primaires. Les contraintes considérées sont : des seuils maximaux des puissances d'interférence crête et moyenne tolérés par les utilisateurs primaires (fonctions linéaires) et une contrainte de débit minimale pour la communication opportuniste au secondaire (fonction concave).
La solution de notre problème est de type "water-filling", c'est-à-dire solution d'un système des équations de point fixe. Dans le cas particulier de deux bandes de fréquence, une solution analytique est trouvée [1]. Par contre, ceci n'est pas possible dans le cas général de plusieurs bandes de fréquences. La difficulté est posée par l'existence de plusieurs contraintes de puissance moyenne et de débit moyen [2], [3].
Dans le cas général, nous proposons un algorithme itératif de point fixe pour calculer la solution optimale. Dans le cas où l'algorithme converge, il converge nécessairement vers un point optimal du problème. Cependant, l'étude de la convergence de cet algorithme s'avère non triviale. Les résultats numériques des simulations effectuées montrent la bonne convergence de l'algorithme. [4]

[1] R. Masmoudi, E.V. Belmega, I. Fijalkow, and N. Sellami, "A Closed-Form Solution to the Power Minimization Problem over Two Orthogonal Frequency Bands under QoS and Cognitive Radio Interference Constraints", IEEE Dynamic Spectrum Access Networks (DySpan), Bellevue, Washington, USA,pp. 1- 11, Oct. 2012.
[2] J.-S. Pang, G. Scutari, F. Facchinei, and C. Wang, "Distributed power allocation with rate constraints in gaussian parallel interference channels," IEEE Trans. Inf. Theory, vol. 54, no. 8, pp. 3471-3489, Aug. 2008.
[3] D. Palomar, M. A. Lagunas, and J. M. Cioffi, "Optimum linear joint transmit-receive processing for MIMO channels with QoS constraints," IEEE Trans. Signal Process., vol. 52, no. 5, pp. 1179-1197, May. 2004.
[4] R. Masmoudi, E.V. Belmega, I. Fijalkow, and N. Sellami, "Power minimization problem under QoS and Cognitive Radio interference constraints", article de revue en cours de préparation

 

Marcelo PEREYRA (Univ. Bristol, UK)

Titre : Proximal Markov chain Monte Carlo algorithms

Abstract : This talk presents a new class of Metropolis-adjusted Langevin algorithms (MALA) that combines stochastic simulation with modern convex optimisation to simulate samples from high-dimensional convex distributions that are not smooth. This is achieved by considering discretizations of Langevin diffusions associated with smooth Moreau approximations of the target density. The resulting algorithms exploit the proximity mappings of the target to efficiently explore the parameter space, in a similar manner to how the conventional MALA uses gradients. The proposed methodology is demonstrated on challenging optimisation problems that involve maximising intractable cost functions such as expectations and marginal likelihoods subject to constraints.

Jean-Christophe PESQUET (LIGM, Univ. Paris-Est)

Titre : Tutoriel sur les méthodes proximales

Abstract : Dans  cet exposé, nous ferons un rapide tour d'horizon des approches proximales, qui ont rencontré récemment un grand succès en optimisation convexe non lisse. Nous montrerons que deux d'entre elles, l'algorithme explicite-implicite (forward-backward) et celui de Douglas-Rachford sont les briques de base de la construction de méthodes plus élaborées. Dans un second temps, nous donnerons quelques résultats récents sur le cas non convexe.

 

Eric THIEBAUT / Ferréol SOULEZ (CRAL, Lyon)

Titre : Résolution de problèmes de reconstruction sous contrainte en imagerie

Résumé : La restauration d'image (ou plus généralement de fonctions de distribution) est un problème inverse mal conditionné et à très grand nombre de paramètres. La résolution du problème nécessite de prendre en compte des contraintes de régularité imposées de façon relachée mais aussi des contraintes strictes comme la positivité ou la normalisation de la solution. Au moins à cause du champ limité et de la dépendance du bruit avec le signal, le problème direct même s'il peut être linéaire n'est généralement pas stationnaire. La résolution du problème est donc nécessairement itérative. Nous présenteront différentes approches itératives pour résoudre, en pratique, des problèmes com me la reconstruction d'image en interférométrie, la déconvolution aveugle, etc. Les méthodes mises en œuvre allant des méthodes de descente les plus simples (méthodes multiplicatives) à ADMM (alternating direction method of multipliers) en passant par les méthodes de sous-espace ou de projection de gradient.