Workshop Optimisation: aspects fondamentaux et exploitation de la structure
Workshop Optimisation: aspects fondamentaux
et exploitation de la structure
CIMI Workshop, Toulouse, France
2829 juin 2018
L'optimisation est en plein essor tant au niveau industriel qu'académique, stimulée par les nouveaux défis posés par des applications stratégiques à fort impact sociétal. Ce thème abordera des aspects fondamentaux de l'optimisation tels que la complexité en optimisation convexe et non convexe, les hiérarchies de relaxation, l'étude de convergence d'algorithmes. Une attention particulière sera portée sur la résolution des problèmes de grande taille par exploitation de diverses structures parmi lesquelles la convexité cachée, la séparabilité partielle ou toute autre forme de structure issue d'applications particulières :
 Optimization composite : minimisation de combinaisons de fonctions lisses et de fonctions convexes. Ce domaine a connu des développements significatifs stimulé par les applications nécessitant d’imposer des structures particulières : rang de matrices, caractère creux par exemple.
 Optimization convexe : ce thème recouvre des aspects à la fois fondamentaux, géométriques et algorithmiques autour de la convexité. Il est devenu un outil fondamental notamment pour les problèmes de très grande dimension liés au traitement de données, autour des méthodes du premier ordre qu’il s'agit de mieux comprendre, d’accélérer, de paralléliser par exemple.
 Optimisation conique, hiérarchies : les hiérarchies de Lasserre ont permis d’introduire des outils de relaxation très généraux ayant des propriétés de convergence remarquables, avec des applications notamment pour les problèmes NPdifficiles. Il s’agira ici de faire un focus sur différents aspects liés notamment à la programmation conique et l’extension des hiérarchies de relaxations à d’autres domaines (tenseurs, information quantique, etc.).
 Programmation non linéaire, non convexe : des efforts récents ont été consentis pour mieux comprendre certains aspects fondamentaux autour des algorithmes globalement convergents pour l’optimisation de fonctions nonconvexes. Ces progrès ont donné lieu à une nouvelle génération d’algorithmes et à une mise en perspective d’algorithmes connus. L’objet de ce sousthème est d’explorer ces deux versants : théorie et algorithmes en nonconvexe.
 Etude et exploitation de la géométrie : ce sousthème sera l’occasion de présenter des aspects fondamentaux sur la structure de certains problèmes en très grande dimension.
Le Workshop « Optimisation: aspects fondamentaux et exploitation de la structure » aura lieu à l'auditorium de l'Institut de Recherche en Informatique de Toulouse (IRIT) et fait partie du semestre thématique « Optimisation » organisé par le Labex CIMI. Cet évènement est financé par le Labex CIMI et le GdR MOA.
Inscription
Les inscriptions à la Master Class sont ouvertes jusqu'au vendredi 1er juin 2018. L'inscription est gratuite mais obligatoire.
Date of the Master Class
28  29 June 2018
Orateurs confirmés
 Jérôme Bolte
 PatrickLouis Combettes
 Didier Henrion
 Etienne de Klerk
 Jiawang Nie
 Monique Laurent
 Marc Teboulle
 Justin Romberg
 Anthony Man Cho So
 Zaikun Zhang
Programme
Le workshop de déroulera du jeudi 28 juin à 10h au vendredi 29 juin à 17:30, à l'Auditorium at Institut de Recherche en informatique de Toulouse (IRIT).
Programme détailé :
Thursday June, the 28th 

10:00  11:00 
Jiawang Nie : Symmetric Tensor Nuclear Norms This talk is about nuclear norms of symmetric tensors. As recently shown by Friedland and Lim, the nuclear norm of a symmetric tensor can be achieved at a symmetric decomposition. We propose an algorithm for computing symmetric tensor nuclear norms, as well as nuclear decompositions. Lasserre relaxations are used for the computation. The convergence properties are proved. The method can also be extended to nonsymmetric tensors. 
11:00  11:30 
Coffee 
11:30  12:30 
Didier Henrion : Moment and sums of squares for polynomial hyperbolic PDEs The momentsumsofsquares or Lasserre hierarchy, originally developed for polynomial optimization in the early 2000s, has found many applications, in particular for the optimal control of polynomial ordinary differential equations. It can be used to generate a sequence of polynomial subsolutions of the HamiltonJacobiBellman equation with a guarantee of L1 convergence to the value function along optimal trajectories. Instrumental to the convergence proof are occupation measures supported on trajectories. In our talk, we extend further the scope of the momentsumsofsquares hierarchy to evaluate functionals on solutions of polynomial hyperbolic conservation laws. This class of nonlinear partial differential equations (PDEs) may have no solutions among smooth functions, as shocks (discontinuities) may appear after some time for smooth initial conditions. We use a weak formulation and the notion of measurevalued solution, as well as entropy inequalities, to prove that a specific momentsumsofsquares hierarchy provides guarantees of convergence for evaluating functionals, or for solving the inverse problem of approximating the set of all initial conditions consistent with a given terminal condition. This is joint work with Jean Bernard Lasserre, Swann Marx and Tillmann Weisser. 
12:30  14:00 
Lunch 
14:00  15:00 
Patrick Louis Combettes : Proximal activation of smooth functions in splitting algorithms for convex minimization (Joint work with L. Glaudin, Paris 6). Structured convex optimization problems typically involve a mix of smooth and nonsmooth functions. The common practice is to activate the smooth functions via their gradient and the nonsmooth ones via their proximity operator. We show that, although intuitively natural, this approach is not necessarily the most efficient numerically and that, in particular, activating all the functions proximally may be advantageous. To make this viewpoint viable computationally, we derive the proximity operators of various smooth convex functions arising in applications. Various applications and numerical examples will be presented. 
15:00  16:00 
Jérôme Bolte : From error bounds to the complexity of firstorder descent methods for convex functions
We show that error bounds can be used as effective tools for deriving complexity results for firstorder descent methods in convex minimization. To this end, we provide an equivalence between Holderian error bounds and the Lojasiewicz inequality. In a second stage, we show how Lojasiewicz inequalities can in turn be employed to compute new complexity bounds for a wealth of descent methods for convex problems (including the proximal gradient method). As a byproduct of our study, we also provide new results for the globalization of KL inequalities in the convex framework. Our main results inaugurate a simple method: derive an error bound, compute the desingularizing function whenever possible, identify essential constants in the descent method and finally compute the complexity using the onedimensional worst case proximal sequence. Our method is illustrated through projection methods for feasibility problems, and through the famous iterative shrinkage thresholding algorithm (ISTA), for which we show that the complexity bound is of the form O(q^{k}) where the constituents of the bound only depend on error bound constants obtained for an arbitrary least squares objective with l^{1} regularization. 
16:00  16:30 
Coffee 
16:30  17:30 
Zaikun Zhang : Trustregion method based on inexact firstorder information As a fundamental tool in nonlinear optimization, trustregion method is considered to be classical and well understood. Its global convergence was established by Powell more than 40 years ago, and its worstcase complexity has been well studied recently. However, in the era of Data Science, we often find ourselves in scenarios that are not fully covered by such classical analysis. For example, the information required by the method may not always be available or reliable. Worse still, we may even feed the method with completely wrong information without being aware. These scenarios urge us to have a new look at the old method and understand it when classical assumptions fail. We will discuss the behavior of trustregion method assuming that the objective function is smooth yet its gradient information available to us is inaccurate or even completely wrong. Both deterministic and stochastic cases will be investigated. It turns out that trustregion method is remarkably robust with respect to gradient inaccuracy. The method converges even if the gradient is evaluated with only one correct significant digit, and even if the gradient evaluation encounters random failures with probability 1/2. Indeed, in both situations, the worst case complexity of the method is essentially the same as when the gradient evaluation is always accurate. This talk is based on joint works with Clément W. Royer (Wisconsin Madison), Serge Gratton (University of Toulouse, INPT/ENSEEIHT), and Luis Nunes Vicente (University of Coimbra and Lehigh University). 
Friday June the 29th 

10:00  11:00 
Monique Laurent : Convergence analysis of Lasserre's measurebased bounds for polynomial optimization We consider the problem of minimizing a multivariate polynomial f over a compact region K. As shown by Lasserre, this can be reformulated as searching for a measure mu with positive density function for which the expected value of f over K is mininimized, and hierarchies of upper bounds converging to the minimum of f over K can be obtained by selecting sumsofsquares density functions with growing degrees 2d. We discuss several recent results about the convergence rate of these hierarchies. For general convex bodies K and selecting mu to be the Lebesgue measure we show a convergence rate in O(1/d). When K is the hypercube [1,1]^{n} and mu is the product measure having the Chebyshev polynomials as orthogonal polynomials, we can show a stronger convergence rate in O(1/d^{2}) and that this bound is tight for linear polynomials. Moreover, these results still hold if we allow a richer class of density functions (conic combinations of the constraints with sumsofsquares coefficients). 
11:00  11:30  Coffee 
11:30  12:30 
Etienne de Klerk : New semidefinite programming approaches for the generalized problem of moments: error bounds and examples We consider the generalized problem of moments, and show how to construct approximate solutions using semidefinite programming. These approximate solutions have polynomial sumofsquares density functions with respect to a given finite, positive Borel measure. Our approach relies heavily on the theoretical properties of a measurebased hierarchy for polynomial optimization introduced by Lasserre [SIAM J. Optim. 21(3) (2011), pp. 864885]. We will demonstrate various error bounds for the approximate solutions depending on the reference measure and its support. Finally, we will demonstrate the practicality by way of examples in portfolio optimization, insurance loss estimation, and global optimization of rational functions. This talk will be based on joint work with Monique Laurent, and separate joint work with Krzysztof Postek and Daniel Kuhn. 
12:30  14:00 
Lunch 
14:00  15:00 
Anthony Man Cho So Generalized Power Method for Phase Synchronization with Provable Estimation and Convergence Guarantees The problem of phase synchronization with its numerous applications has attracted much research in recent years. Currently, there are two main approaches for computing the maximum likelihood estimator of the unknown phase vector. One is semidefinite relaxation and the other is to directly solve the nonconvex maximum likelihood formulation by the generalized power method (GPM). In this talk, we focus on the latter approach and study it from both statistical and optimizationtheoretic viewpoints. Our contribution is twofold. First, we show that the \ell_2 and \ell_\inftybounds on the estimation error of the GPM decrease geometrically to the best provable bound under the least restrictive noise level requirement. Second, we prove that the objective value and the sequence of iterates of GPM converge linearly to the optimal value and the unique global optimizer, respectively, under a less restrictive requirement compared with that in the literature. This answers an open question raised in a recent work of Boumal. 
15:00  16:00 
Justin Romberg : Solving Nonlinear Equations using Convex Programming We consider the question of estimating a solution to a system of equations that involve convex nonlinearities, a problem that is common in machine learning and signal processing. Because of these nonlinearities, conventional estimators based on empirical risk minimization generally involve solving a nonconvex optimization program. We propose a method (called "anchored regression”) that is based on convex programming and amounts to maximizing a linear functional (perhaps augmented by a regularizer) over a convex set. The proposed convex program is formulated in the natural space of the problem, and avoids the introduction of auxiliary variables, making it computationally favorable. Working in the native space also provides us with the flexibility to incorporate structural priors (e.g., sparsity) on the solution. For our analysis, we model the equations as being drawn from a fixed set according to a probability law. Our main results provide guarantees on the accuracy of the estimator in terms of the number of equations we are solving, the amount of noise present, a measure of statistical complexity of the random equations, and the geometry of the regularizer at the true solution. We also provide recipes for constructing the anchor vector (that determines the linear functional to maximize) directly from the observed data. We will discuss applications of this technique to nonlinear problems including phase retrieval, blind deconvolution, and inverting the action of a neural network. 
16:00  16:30 
Coffee 
16:30  17:30 
Marc Teboulle : Nonconvex Lagrangianbased Optimization: monitoring schemes and global convergence We introduce a novel approach addressing global analysis of a difficult class of nonconvexnonsmooth optimization problems in modern disparate fields of applications. It features complex geometries, qualification conditions, and other regularity properties do not hold everywhere. To address these issues we work along several research lines to develop an original general Lagrangian methodology which can deal, all at once, with the above obstacles. A first innovative feature of our approach is to introduce the concept of Lagrangian sequences for a broad class of algorithms. Central to this methodology is the idea of turning an arbitrary descent method into a multiplier method. Secondly, we provide these methods with a transitional regime allowing us to identify in finitely many steps a zone where we can tune the stepsizes of the algorithm for the final converging regime. Then, despite the minmax nature of Lagrangian methods, using an original Lyapunov method we prove that each bounded sequence generated by the resulting monitoring schemes are globally convergent to a critical point for some fundamental Lagrangianbased methods in the broad semialgebraic setting, which to the best of our knowledge, are the first of this kind. Joint work with Jerome Bolte and Shoham Sabach.

Comité d'organisation
Sébastien Gadat (UT1), Serge Gratton (IRIT), Aude Rondepierre (IMT), Pierre Weiss (ITAV / IMT).
Comité scientifique
Sébastien Gadat (UT1), Serge Gratton (IRIT), Jean_Bernard Lasserre (LAASCNRS), François Malgouyres (IMT), Aude Rondepierre (IMT), Pierre Weiss (ITAV / IMT).
Contact
Pour toute question, merci de nous contacter : send us an email