Lectures

Plenary Lectures

• Tuesday, July 14th: Laurent El Ghaoui, University of California Berkeley

Optimization in the Age of Big Data: Sparsity and Robustness at Scale

The term “big data” is too often associated with the sole task of applying machine learning analytics to large data sets. It seems that optimization has been concerned with large data sets for a long time already, not just as purveyor of algorithms for analytics but also as models for decision-making. What is changing in the interface between learning and decision-making? What is the impact of big data on optimization? I will present various approaches and perspectives stemming from the application of optimization models in a big data context. The talk will focus on sparsity and robustness, both in statistical learning and decision-making problems. Some case studies involving online retail problems, finance and energy resource management will be presented. The emerging picture is that of an ever closer integration between the two fields, at both practical and fundamental levels.

• Monday, July 13th: Jim Geelen, University of Waterloo, Canada

Matroid minors project

Over the past 15 years I have been working withBert Gerards and Geoff Whittle on extending the Graph Minors Project, of Paul Seymour and Neil Robertson, to minor-closed classes of representable matroids. This talk is intended to be a gentle overview of our project, covering the main results and some applications in coding theory. No prior exposure to matroid theory is assumed.

• Thursday, July 16th: Daniel Kuhn, Ecole Polytechnique Fédérale de Lausanne, Switzerland

A Distributionally Robust Perspective on Uncertainty Quantification and Chance Constrained Programming

The objective of uncertainty quantification is to certify that a given physical, engineering or economic system satisfies multiple safety conditions with high probability. A more ambitious goal is to actively influence the system so as to guarantee and maintain its safety, a scenario which can be modeled through a chance constrained program. In this talk we assume that the parameters of the system are governed by an ambiguous distribution that is only known to belong to an ambiguity set characterized through generalized moment bounds and structural properties such as symmetry, unimodality or independence patterns. We delineate the watershed between tractability and intractability in ambiguity-averse uncertainty quantification and chance constrained programming. Using tools from distributionally robust optimization, we derive explicit conic reformulations for tractable problem classes and suggest efficiently computable conservative approximations for intractable ones.

• Friday, July 17th: Daniel A. Spielman, Yale University

Laplacian Matrices of Graphs: Algorithms and Applications

The problem of solving systems of linear equations in the Laplacian matrices of graphs arises in many fields including Optimization, Machine Learning, Computer Vision, and of course Computational Science. We will explain what these matrices are and why they arise in so many applications. We then will survey recently developed algorithms that allow us to solve such systems of linear equations in nearly-linear time. The main tools used in these algorithms are sparse approximations of graphs and approximations of graphs by low-stretch spanning trees. The ability to quickly solve such systems of equations has led to the asymptotically fastest algorithms for computing maximum flows and minimum cost flows. The techniques used in the Laplacian equation solvers have been used to design the fastest algorithms for approximating maximum flows. We will provide an introduction to these recent developments.

• Wednesday, July 15th: Stephen J. Wright, University of Wisconsin-Madison

Coordinate Descent Algorithms

Coordinate descent algorithms solve optimization problems by successively searching along coordinate directions or coordinate hyperplanes. They have been used in applications for many years, and their popularity continues to grow because of their usefulness in data analysis, machine learning, and other areas of current interest. This talk will describe the fundamentals of the coordinate descent approach, together with its variants and extensions. Convergence properties will be described, mostly with reference to convex objectives. We pay particular attention to a certain problem structure that arises commonly in machine learning applications, showing that efficient implementations of accelerated coordinate descent algorithms are possible for such structures. We also describe parallel variants and discuss their convergence properties under several models of parallel execution.

Semi-Plenary Lectures

• Tuesday, July 14th: Samuel A. Burer, University of Iowa

A Gentle, Geometric Introduction to Copositive Optimization

This talk illustrates the fundamental connection between nonconvex quadratic optimization and copositive optimization—a connection that allows the reformulation of nonconvex quadratic problems as convex ones in a unified way. We focus on examples having just a few variables or a few constraints for which the quadratic problem can be formulated as a copositive-style problem, which itself can be recast in terms of linear, second-order-cone, and semidefinite optimization. A particular highlight is the role played by the geometry of the feasible set.

• Monday, July 13th: Roberto Cominetti, Universidad de Chile, Chile

Equilibrium routing under uncertainty

In this talk we review several alternative models that have been used to describe traffic in congested networks, both in urban transport and telecommunications. We focus on situations where travel times are subject to random fluctuations and how this variability affects the traffic flows. We consider both atomic and non-atomic equilibrium models, and we discuss a class of adaptive dynamics that describe the behavior of agents and which provides a plausible micro-foundation for the emergence of equilibrium. We also discuss some recent ideas on how risk aversion to random travel times might be incorporated in the models. In our presentation we use convex optimization to provide a unifying framework for the different concepts of equilibrium.

• Wednesday, July 15th: Michele Conforti, University of Padova, Italy

A geometric approach to cut-generating functions

The cutting-plane approach to integer programming was initiated more that 40 years ago: Gomory introduced the corner polyhedron as a relaxation of a mixed integer set in tableau form and Balas introduced intersection cuts for the corner polyhedron. This line of research was left dormant for several decades until relatively recently, when a paper of Andersen, Louveaux, Weismantel and Wolsey generated renewed interest in the corner polyhedron and intersection cuts. Recent developments rely on tools drawn from convex analysis, geometry and number theory, and constitute an elegant bridge between these areas and integer programming. We survey these results and highlight recent breakthroughs in this area.

• Wednesday, July 15th: Tamara G. Kolda, Sandia National Laboratories

Optimization Challenges in Tensor Factorization

Tensors are multiway arrays, and tensor decomposition is a powerful tool for compression and data interpretation. In this talk, we demonstrate the utility of tensor decomposition with several examples and explain the optimization challenges, both theoretical and practical. The optimization problems are nonconvex, but they can typically be solved via an alternating approach that yields convex subproblems. We consider open problems such as determining the model complexity, tensor completion, incorporating symmetries and other constraints, handling ambiguities in scaling and permutation, enforcing structure like sparsity, and considering alternative objective functions.

• Thursday, July 16th: Andrea Lodi, University of Bologna, Italy

On Mathematical Programming with Indicator Constraints

In this paper we review the relevant literature on mathematical optimization with logical implications, i.e., where constraints can be either active or disabled depending on logical conditions to hold. In the case of convex functions, the theory of disjunctive programming allows one to formulate these logical implications as convex nonlinear programming problems in a space of variables lifted with respect to its original dimension. We concentrate on the attempt of avoiding the issue of dealing with large NLPs. In particular, we review some existing results that allow to work in the original space of variables for two relevant special cases where the disjunctions corresponding to the logical implications have two terms. Then, we significantly extend these special cases in two different directions, one involving more general convex sets and the other with disjunctions involving three terms. Computational experiments comparing disjunctive programming formulations in the original space of variables with straightforward bigM ones show that the former are computationally viable and promising. (Joint work with Pierre Bonami, Andrea Tramontani and Sven Wiese)

• Tuesday, July 14th: Asu Özdaglar, Massachusetts Institute of Technology

Fast Distributed Algorithms for Multi-agent Optimization

Motivated by today’s data processing needs over large networks with local collection and processing of information, we consider a multi agent optimization problem where a network of agents collectively solves a global optimization problem with the objective function given by the sum of locally known convex functions. We present new distributed algorithms drawing on two different approaches: The first is based on Alternating Direction Method of Multipliers (ADMM), which is a classical method for sequentially decomposing optimization problems with coupled constraints. We show that convergence rate of distributed ADMM-based algorithms is O(1/k) (where k is the iteration number), which is faster than the O(1/sqrt(k)) rate of subgradient-based methods, and highlight the dependence on the network structure. The second approach develops an incremental Newton (IN) method, which accesses problem data sequentially. Under strong convexity of local objective functions, a gradient growth condition, and with proper stepsize rules, we show that convergence rate of the IN method is linear.

• Thursday, July 16th: Werner Römisch, Humboldt Universität Berlin, Germany

Quasi-Monte Carlo methods for linear two-stage stochastic programming problems

Quasi-Monte Carlo algorithms are studied for generating scenarios to solve two-stage linear stochastic programming problems. Their integrands are piecewise linear-quadratic, but do not belong to the function spaces considered for QMC error analysis. We show that under some weak geometric condition on the two-stage model all terms of their ANOVA decomposition, except the one of highest order, are continuously differentiable and second order mixed derivatives exist almost everywhere and belong to $L_{2}$. This implies that randomly shifted lattice rules may achieve the optimal rate of convergence $O(n^{-1+\delta})$ with $\delta\in(0,\frac{1}{2})$ and a constant not depending on the dimension if the effective superposition dimension is less than or equal to two. The geometric condition is shown to be satisfied for almost all covariance matrices if the underlying probability distribution is normal. We discuss effective dimensions and techniques for dimension reduction. Numerical experiments for a production planning model with normal inputs show that indeed convergence rates close to the optimal rate are achieved when using randomly shifted lattice rules or scrambled Sobol’ point sets accompanied with principal component analysis for dimension reduction.

• Friday, July 17th: Frank Vallentin, University of Köln, Germany

Mathematical optimization for packing problems

How densely can one pack given objects into a given container? Such packing problems are fundamental problems in geometric optimization. Next to being classical mathematical challenges there are many applications in diverse areas such as information theory, materials science, physics, logistics, approximation theory. Studying packing problems one is facing two basic tasks: Constructions: How to construct packings which are conjecturally optimal? Obstructions: How to prove that a given packing is indeed optimal? For the first basic task researchers in mathematics and engineering found many heuristics which often work well in practice. In the talk I want explain computational tools for the second basic task. These tools are a blend of tools coming from infinite-dimensional semidefinite optimization and harmonic analysis, together with computational techniques coming from real algebraic geometry and polynomial optimization. I will report on computational results, which are frequently the best-known.

• Monday, July 13th: Pascal van Hentenryck, NICTA, Australia

Complexity, Approximation, and Relaxation of the Power Flow Equations

The design, control, and operation of the power grid, probably the largest and most expansive system ever engineered, require the solving of optimization problems over the steady-state power flow equations. The resulting mixed nonconvex programs are often computationally challenging and increasingly so with the increased stochasticity in generation and load. This talk presents some new complexity results, as well as a number of advances in approximating and relaxing the power flow equations to address emerging applications in power systems, including large-scale power restoration after blackouts, the design of resilient networks, and the integration of renewable generation. Extensive computational results demonstrate some of the benefits of the proposed techniques.

• Friday, July 17th: Ya-xiang Yuan, Chinese Academy of Sciences, China