Workshop Optimization: Fundamentals and Algorithms for Structured Problems

Thursday June, the 28th

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.

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.

Lunch

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

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(q^k)  where the constituents of the bound only depend on error bound constants obtained for an arbitrary least squares objective with   l¹ regularization.

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

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]ⁿ and mu is the product measure having the Chebyshev polynomials as orthogonal polynomials, we can show a stronger convergence rate in O(1/d²) 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).

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.

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.

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.

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