Joint work with Arkadi Nemirovski


We consider the estimation problem as follows: given a noisy indirect  observation $\omega=Ax+\xi$ we want to recover a linear image $Bx$ of a signal $x$ known to belong to a given set $X$. Under some assumptions on $X$ (satisfied, e.g., when $X$ is the intersection of $K$ concentric ellipsoids/elliptic cylinders, or the unit ball of the spectral norm in the space of matrices) and on the norm $\|\cdot\|$ used to measure the recovery error (satisfied, e.g., by $\|\cdot\|_p$-norms, $1\leq p\leq 2$, on $\bR^m$ and by the nuclear norm on the space of matrices), and {\em without imposing any restriction on mappings $A$ and $B$,} we build a {\em linear in observation} estimate which is near-optimal among all (linear and nonlinear) estimates in terms of its worst-case, over $x\in X$, expected $\|\cdot\|$-loss.

These results form an essential extension of the classical results (cf. e.g., Pinsker 1980 and Donoho, Liu and MacGibbon, 1990), which in the case of Euclidean norm $\|\cdot\|$  and diagonal matrices $A$ and $B$ impose more restrictive assumptions on the signal set $X$.

The proposed estimator is built in a computationally efficient way. Furthermore, all theoretical constructs and proofs heavily rely upon the tools of convex optimization.  

Accelerating the Universal Newton Methods.
Yuri Nesterov – University of Catholic Louvaine

In this talk we present new results related to the universal second-order methods, which can automatically adjust the level of smoothness of the objective function. Our methods converge in accordance to the best rates allowed by a Holder condition introduced for the Hessians. As compared with the usual Newton method, the reason for acceleration of our schemes consists in accumulation of global information on the behavior of the objective, represented by a linear model.

Realignment of Sports Leagues
Bill Pulleyblank – United States Military Academy (West Point)

Sports leagues consist of conferences subdivided into divisions. Teams play a number of games within their divisions and fewer games against teams in different divisions and conferences. Usually, a league structure remains stable from one season to the next. However, structures change when growth or contraction occurs, and realignment of the four major professional sports leagues in North America has occurred more than 25 times since 1967.

We describe a method for realigning sports leagues that is flexible, adaptive, and that enables construction of schedules that minimize travel while satisfying other criteria. We do not build schedules; we develop league structures which support the subsequent construction of efficient schedules.

Our initial focus is the NHL, which had a need for realignment following the recent move of the Atlanta Thrashers to Winnipeg, but our methods can be adapted to virtually any situation.

This is joint work with Dr. Brian Macdonald, Director of Analytics, Florida Panthers.

A Mathematical Approach to Living on Sinking Ground
Kees Roos – Delft University

Dike height optimization is of major importance to the Netherlands because a large part of the country lies below sea level and high water levels in rivers can also cause floods. Recently improvements have been made on a cost-benefit model that was introduced by Van Dantzig after a devastating flood in the Netherlands in 1953. We deal with extensions of this model that may also be applicable to other deltas in the world.

Most dike rings consist of several segments that are characterized by different properties. We focus in our presentation on the case of a one-segment (or homogeneous) dike. We show how the optimal solution of our highly nonlinear, nonconvex, and infinite-dimensional model can be obtained analytically. For nonhomogeneous dikes an analytic solution is out of reach. In that case dynamic programming can be used to solve a discretized version of the model if the number of segments is not too large. However, if the number of segments is larger than about five this approach explodes. For that case we developed a mixed integer nonlinear model.


Twenty Years of Sports Scheduling With George
Mike Trick – Carnegie Mellon University

In 1997, a talk I gave at Georgia Tech led to George Nemhauser and I working together to schedule college basketball. Since that talk, the world of sports scheduling has been completely transformed by optimization approaches. I will outline our initial approaches and show how our work has evolved over the years in keeping with major trends in computational integer and constraint programming.  

Parametrization of discrete optimization problems, subdeterminants and matrix-decomposition
Robert Weismantel – ETH Zurich

The central goal of this talk is to identify parameters that explain the complexity of Integer linear programming defined as follows: Let P be a polyhedron. Determine an integral point in P that maximizes a linear function.

It is obvious that the number of integer variables is such a parameter. However, in view of applications in very high dimensions, the question emerges whether we need to treat all variables as integers In other words, can we reparametrize integer programs with significantly less integer variables?

A second much less obvious parameter associated with an integer linear program is the number Delta defined as the maximum absolute value of any square submatrix of a given integral matrix A with m rows and n columns. This leads us to the important open question whether we can solve integer linear programming in a polynomial running time in Delta and the instance size?

Regarding the first question, we exhibit a variety of examples that demonstrate how integer programs can be reformulated using much less integer variables. To this end, we introduce a generalization of total unimodularity called the affine TU-dimension of a matrix and study related theory and algorithms for determining the affine TU-dimension of a matrix.

Regarding the second question, we present several new results that illustrate why Delta is an
important parameter about the complexity of integer linear programs associated with a given matrix A.

Algorithmic Tools for Smooth Nonconvex Optimization
Stephen Wright – University of Wisconsin, Madison

Unconstrained optimization of a smooth nonconvex objective over many variables is a classic problem in optimization. Several effective techniques have been proposed over the years, along with results about global and local convergence. There has been an upsurge of interest recently on techniques with good global complexity properties. (This interest is being driven largely by researchers in machine learning, who want to solve the nonconvex problems arising from neural network training and robust statistics, but it has roots in the optimization literature.) In this talk we describe the algorithmic tools that can be used to design methods with appealing practical behavior as well as provably good global convergence properties. These tools include the conjugate gradient and Lanczos algorithms, accelerated gradient, Newton’s method, cubic regularization, and trust regions. We show how these elements can be assembled into a comprehensive method, and compare a number of proposals that have been made to date. We pay particular attention to the behavior of accelerated gradient methods in the neighborhood of saddle points.

Multi-Block ADMM and its Convergence
Yinyu Ye – Stanford University

We show that the direct extension of alternating direction method of multipliers (ADMM) with three blocks is not necessarily convergent even for solving a square system of linear equations, although its convergence proof was established 40 years ago with one or two blocks. However, we prove that, in each iteration if one randomly and independently permutes the updating order of variable blocks followed by the regular multiplier update, then ADMM will converge in expectation when solving any system of linear equations with any number of blocks. This is probably the first theoretical evidence for applying random permutation in computational optimization, where empirical results have shown the effectiveness of random permutation in either ADMM or block coordinate descent method. We also discuss its extension to solve general convex optimization problems.