Optimisation non-convexe

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

25 personnes membres du GdR ISIS, et 22 personnes non membres du GdR, sont inscrits à cette réunion.
Capacité de la salle : 100 personnes.

Annonce

La résolution de problèmes non-convexes couvre un large spectre des travaux de la communauté signal/image avec des développements récents sur les thématiques telles que la reconstruction parcimonieuse, la résolution de problèmes inverses non-linéaires ou la segmentation. D'un point de vue théorique, le panel des méthodes dites de résolution de problèmes non-convexes est vaste. On peut par exemple citer les techniques d'optimisation globale, d'optimisation discrète, de relaxation convexe, ou encore les approches basées sur des hypothèses de type inégalité de Kurdyka-Lojasiewicz.

Une première journée a été consacrée à la résolution de problèmes inverses non-linéaires ainsi qu'aux méthodes discrètes et aux algorithmes de brunch-and-bound. Cette seconde journée s'intéressera plus particulièrement à des thèmes qui n'ont pas pu être abordés lors de la première journée, à savoir les approches basées sur des hypothèses de type inégalité de Kurdyka-Lojasiewicz, les métaheuristiques et la programmation DC.

Organisateurs :

Saïd Moussaoui (said.moussaoui@irccyn.ec-nantes.fr) et Nelly Pustelnik (nelly.pustelnik@ens-lyon.fr).

Programme

Résumés des contributions

Jérôme BOLTE
Tutoriel : Optimisation non-convexe et inégalité de Kurdyka- Lojasiewicz

Audrey REPETTI
Algorithme préconditionné explicite-implicite et application à la résolution de problèmes inverses en traitement du signal
(collaboration avec Emilie CHOUZENOUX, Mai QUYEN PHAM, Laurent DUVAL et Jean-Christophe PESQUET)

Résumé -- La résolution d'un problème inverse requiert souvent la minimisation d'un critère composite, somme d'un terme différentiable de gradient Lipschitz et d'un terme non nécessairement différentiable. Ce type de critère peut être minimisé efficacement grâce à un algorithme explicite-implicite (forward-backward) accéléré par l'introduction d'une métrique variable choisie suivant la théorie de la Majoration-Minimisation. La combinaison de cette approche avec une stratégie de minimisation alternée permet de traiter une large classe de problèmes d'optimisation mettant en jeu des données de grandes tailles. La convergence de l'algorithme résultant est démontrée dans le cas d'un critère non nécessairement convexe, grâce à des résultats récents de l'analyse non lisse. Ses performances seront illustrées sur un exemple de démélange de données hyperspectrales et sur un exemple de déconvolution aveugle de signal parcimonieux.

Références --

E. Chouzenoux, J.-C. Pesquet, et A. Repetti. A Block Coordinate Variable Metric Forward-Backward Algorithm. Tech. Rep., 2014. http://www.optimization-online.org/DB_HTML/2013/12/4178.html

A. Repetti, E. Chouzenoux, et J.-C. Pesquet A Preconditioned Forward-Backward Approach with Application to Large-Scale Nonconvex Spectral Unmixing Problems. In Proceedings of the 39th IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP 2014), Florence, Italie, 4-9 mai 2014.

A. Repetti, M. Q. Pham, L. Duval, E. Chouzenoux, et J.-C. Pesquet. Euclid in a Taxicab: Sparse Blind Deconvolution with Smoothed l1/l2 Regularization. Tech. Rep., 2014. http://arxiv.org/abs/1407.5465

Luc LE MAGOAROU
Apprendre des dictionnaires computationellement efficaces, à la manière des transformées rapides

Résumé -- Dictionary learning is a branch of signal processing and machine learning that aims at finding a frame (called dictionary) in which some training data admits a sparse representation. The sparser the representation, the better the dictionary. The resulting dictionary is in general a dense matrix, and its manipulation can be computationally costly both at the learning stage and later in the usage of this dictionary, for tasks such as sparse coding. Dictionary learning is thus limited to relatively small-scale problems. In this paper, inspired by usual fast transforms, we consider a general dictionary structure that allows cheaper manipulation, and propose an algorithm to learn such dictionaries --and their fast implementation-- over training data. The approach is demonstrated experimentally with the factorization of the Hadamard matrix and with synthetic dictionary learning experiments.

Référence -- Le Magoarou, L. & Gribonval, R. Learning computationally efficient dictionaries and their implementation as fast transforms CoRR, 2014, abs/1406.5388

Gilles GASSO
Tutoriel : Pénalités non-convexes et programmation DC

Sébastien BOURGUIGNON
Optimisation globale déterministe pour la résolution de problèmes parcimonieux en norme L0 (collaboration Jordan NININ, Hervé CARFANTAN et Marcel MONGEAU)

Résumé -- L’approximation parcimonieuse consiste à rechercher, sous un modèle y=Ax+bruit, une solution x possédant un grand nombre de composantes nulles (de faible norme L0), approchant des données y. Le problème, essentiellement combinatoire, est généralement abordé de manière sous-optimale, soit par la relaxation convexe de la norme L0 par la norme L1, soit par des démarches heuristiques d'exploration combinatoire. Dans de nombreux contextes, les conditions d'optimalité de telles approches vis-à-vis du problème initial se révèlent excessivement restrictives ou ne débouchent que sur des résultats de convergence locale. C'est le cas par exemple des problèmes de déconvolution de trains d'impulsions, où l'opérateur A ne satisfait pas les hypothèses issues de la théorie de l'approximation parcimonieuse et de l'échantillonnage comprimé.
Nous étudions l'optimisation de critères parcimonieux formulés à partir de la norme L0 au moyen d'algorithmes d’optimisation globale déterministe, visant simultanément à calculer la solution et à prouver son optimalité. L'optimisation globale a fait d’énormes progrès ces dernières années, rendant possibles l'utilisation de telles approches sur des problèmes de taille modérée, malgré la combinatoire exponentielle du problème formulé. Nous nous intéressons plus particulièrement aux algorithmes de programmation mixte en nombres entiers, mêlant variables continues et discrètes. Différentes reformulations du problème initial sont proposées et comparées en termes de coût calculatoire. Nous concluons à l'efficacité de certaines formulations, qui permettent d'aborder des classes de problèmes pour lesquels la recherche combinatoire exhaustive reste impossible et les méthodes classiques échouent dans des minima locaux.

Julien LEPAGNOT
Tutoriel : Métaheuristiques
(collaboration avec Patrick SIARRY)

Résumé -- Les « métaheuristiques », telles que les algorithmes évolutionnaires, l’optimisation par essaims particulaires, l’optimisation par colonie de fourmis et les algorithmes à estimation de distribution, sont désormais reconnues comme une approche efficace de résolution pour de nombreux problèmes d’ « optimisation difficile », en traitement d’images comme dans beaucoup d’autres domaines. Cette présentation a pour but de décrire quelques-unes des principales métaheuristiques, regroupées en deux catégories : les métaheuristiques à solution unique et les métaheuristiques à population de solutions. Les principaux concepts et composants de ces algorithmes seront présentés, ainsi que des applications et des références. Les tendances récentes seront également évoquées, notamment l’hybridation de métaheurisiques. En effet, les métaheuristiques hybrides ont suscité un intérêt croissant ces dernières années. Dans cette nouvelle famille d’algorithmes, une combinaison intelligente de concepts et de techniques issues de différentes méthodes d’optimisation est utilisée. L’hybridation permet de bénéficier des avantages de différents algorithmes.

Ali MOUKADEM
Stockwell transform optimization: Applied on the detection of split in Heart sounds
(collaboration avec Zied BOUGUILA, Djaffar OULD ABDESLAM and Alain DIETERLEN)

Résumé -- The Stockwell Transform (S-transform) can be considered as a hybrid between the Short Time Frequency Transform (STFT) and the wavelet transform (WT). Classically the S-transform uses a Gaussian window, whose standard deviation varies over frequency. Whatever the analyzed signal, the width of the Gaussian window will decrease as the frequency increases. However, the S-transform can suffer from poor energy concentration in time-frequency domain; the window width of the classic S-transform can be considered as limitation since it doesn’t take into consideration the nature of analyzed signal.
We propose a technique to improve the energy concentration of the Stockwell transform in the time-frequency domain. A modified S-transform is proposed with several parameters to control the Gaussian window width. A genetic algorithm is applied to select the optimal parameters which maximize the energy concentration measure. An application presented in this study consists to detect split in heart sounds and calculate its duration which is valuable medical information. Comparison with other famous time-frequency transforms such as Short-time Fourier transforms (STFT) and smoothed-pseudo Wigner-Ville distribution (SPWVD) is performed and discussed.