Workshop Optimization: Fundamentals and Algorithms for Structured Problems

Workshop Optimization: Fundamentals and

Algorithms for Structured Problems

CIMI Workshop, Toulouse, France

28-29th june 2018


Optimization is booming at both the industrial and academic levels, stimulated by the new challenges posed by strategic applications with high societal impact. This workshop will deal with fundamental aspects of optimization such as complexity in convex and non-convex optimization, relaxation hierarchies, algorithm convergence study. Particular attention will be paid to the resolution of large-scale problems by exploiting various structures including hidden convexity, partial separability or any other form of structure resulting from particular applications. The main subtopics are the following:

  • Composite Optimization : minimization of combinations of smooth functions and convex functions. This area has experienced significant developments stimulated by applications requiring some particular structures: row matrices, sparsity for example.
  • Convex Optimization : this sub-theme covers both fundamental, geometrica and algorothmic aspects around convexity. It has become a fundamental tool, especially for very high dimensional problems related to data processing, around first order methods that nedd to be better understood, accelerated and parallelized for example.
  • Conic Optimization and Hierarchies : the Lasserre Hierarchies have introduced very general relaxation tools with remakarble convergence properties and applications especially for NP-hard problems. This sub-theme will focus on different aspects related to conic programming and the extension the hierarchies of relaxations to other domains (tensor, quantum information, etc.)
  • Nonlinear and Nonconvex Programming : recent efforts have been made to better understand some fundamental aspects around globally convergent algorithms for the optimization of non-convex functions. These advances have given rise to a new generation of algorithms and a perspective of known algorithms. The purpose of this sub-theme is to explore these two aspects: non-convex theory and algorithms.
  • Analysis and exploitation of the geometry. This sub-theme will be an opportunity to present fundamental aspects on the structure of some very large problems.

The « Optimization: Fundamentals and Algorithms dor Structured Problem » workshop will take place at Institut de Recherche en Informatique de Toulouse (IRIT) and is part of the thematic semester « Optimization » organized by Labex CIMI. This event is sponsorded by the Labex CIMI and the GdR MOA.   


Registration to attend the Workshop is now open till Friday 1st of June. Please note that the registration is free but mandatory.

Register now

Date of the Master Class

28 - 29 June 2018

Confirmed speakers


The workshop will start on Thursday June 28, at 9:30 and will end on Friday June 29 at 17:30. It will take place in the Auditorium at Institut de Recherche en informatique de Toulouse (IRIT). Click here for a Google Map link.

Thursday June, the 28th

9:30 - 10:00 Welcome coffee

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


11:30 - 12:30

Didier Henrion : Moment and sums of squares for polynomial hyperbolic PDEs

The moment-sums-of-squares 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 Hamilton-Jacobi-Bellman 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 moment-sums-of-squares 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 measure-valued solution, as well as entropy inequalities, to prove that a specific moment-sums-of-squares 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


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 first-order descent methods for convex functions

We show that error bounds can be used as effective tools for deriving complexity results for first-order 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 one-dimensional 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(qk)  where the constituents of the bound only depend on error bound constants obtained for an arbitrary least squares objective with   l1 regularization.

16:00 - 16:30


16:30 - 17:30

Zaikun Zhang : Trust-region method based on inexact first-order information

As a fundamental tool in nonlinear optimization, trust-region method is considered to be classical and well understood. Its global convergence was established by Powell more than 40 years ago, and its worst-case 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 trust-region 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 trust-region 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 measure-based 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 sums-of-squares 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/d2) 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 sums-of-squares 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 sum-of-squares density functions with respect to a given finite, positive Borel measure. Our approach relies heavily on the theoretical properties of a measure-based hierarchy for polynomial optimization introduced by Lasserre [SIAM J. Optim. 21(3) (2011), pp. 864--885]. 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


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 non-convex 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 optimization-theoretic viewpoints. Our contribution is twofold. First, we show that the \ell_2- and \ell_\infty-bounds 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 non-convex 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.

This is joint work with Sohail Bahmani.

16:00 - 16:30


16:30 - 17:30

Marc Teboulle : Non-convex Lagrangian-based Optimization: monitoring schemes and global convergence

We introduce a novel approach addressing global analysis of a difficult class of nonconvex-nonsmooth 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 step-sizes of the algorithm for the final converging regime. Then, despite the min-max 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 Lagrangian-based 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.

Organizing commitee

Sébastien Gadat (UT1), Serge Gratton (IRIT), Aude Rondepierre (IMT), Pierre Weiss (ITAV / IMT).

Scientific commitee

Sébastien Gadat (UT1), Serge Gratton (IRIT), Jean_Bernard Lasserre (LAAS-CNRS), François Malgouyres (IMT), Aude Rondepierre (IMT), Pierre Weiss (ITAV / IMT).



For any questions, please contact us : send an email