Combinatorial Optimization Research Center


Monday, November 15th, 2004

9:00 AM, C. P. Davis Auditorium, Schapiro Bldg.


Laurent El-Ghaoui
U.C. Berkeley

The curse of uncertainty in dynamic programming, and how to fix it

Optimal solutions to Markov decision problems may be very sensitive with respect to the state transition probabilities. In many practical problems, the estimation of these probabilities is far from accurate. Hence, estimation errors are limiting factors in applying Markov decision processes to real-world problems.

We consider a robust control problem for a finite-state, finite-action Markov decision process, where uncertainty on the transition matrices is described in terms of possibly non-convex sets. We show that perfect duality holds for this problem, and that as a consequence, it can be solved with a variant of the classical dynamic programming algorithm, the ``robust dynamic programming'' algorithm. We show that a particular choice of the uncertainty sets, involving likelihood regions or entropy bounds, leads to both a statistically accurate representation of uncertainty, and a complexity of the robust recursion that is almost the same as that of the classical recursion. Hence, robustness can be added at practically no extra computing cost. We derive similar results for other uncertainty sets, including one with a finite number of possible values for the transition matrices.

We describe in a practical path planning example the benefits of using a robust strategy instead of the classical optimal strategy; even if the uncertainty level is only crudely guessed, the robust strategy yields a much better worst-case expected travel time.

(Joint work with A. Nilim.)

Michel X. Goemans

The benefit of adaptivity in stochastic combinatorial optimization problems

We consider multi-stage stochastic variants of classical combinatorial optimization problems, such as knapsack, set packing and scheduling problems. As an illustrative example, in our multi-stage version of the stochastic knapsack problem, item values are deterministic and item sizes are independent random variables with known, arbitrary distributions. Items are placed in the knapsack sequentially, and the act of placing an item in the knapsack instantiates its size. Our goal is to maximize the expected value of items successfully placed.

For this knapsack and other more complex combinatorial optimization problems, we discuss the complexity of optimal adaptive policies, i.e. policies whose decisions depend on instantiated data from previous stages. We design polynomial-time non-adaptive strategies (which base their decisions on the probability distributions but not on instantiated data) and show they provably approximate the best optimal adaptive strategies. For the knapsack problem and the scheduling problems we consider, this benefit of adaptivity is proved to be a constant factor, while for set packing, the benefit of adaptivity matches the square root inapproximability result. Our analysis is based on the derivation of good linear programming bounds on the expected value of the best adaptive strategy.

(Joint work with Brian Dean and Jan Vondr\'ak.)

Michael Overton
New York University

A robust gradient sampling algorithm for nonsmooth, nonconvex optimization

Let f: R^n -> R be nonconvex, continuous, and continuously differentiable on an open dense subset of $R^n$ where its gradient is easily computed. We present a practical, robust algorithm to locally minimize such functions based on gradient sampling. We present both an outline of our convergence theory and numerical results for a variety of interesting problems that have not, to our knowledge, been solved previously.

(Joint work with James V. Burke and Adrian S. Lewis.)

Jong-Shi Pang

Topics in complementarity systems

A complementarity system is a time-dependent dynamical system comprising of an ordinary differential equation (ODE) that is coupled with a finite-dimensional complementarity problem. Such a system arises from the modeling of ODEs with discontinuous and piecewise smooth right-hand sides, from engineering hybrid systems, and from open-loop dynamic Nash games, among other applications. This talk discusses several topics in linear and nonlinear complementarity systems, including Zeno states, solution sensitivity on initial conditions, and boundary-value problems.

Paul Seymour

The Structure of Claw-Free Graphs

A graph is "claw-free" if no vertex has three pairwise nonadjacent neighbours. Line graphs are claw-free, and there has been a great deal of work on extending various theorems about line graphs to claw-free graphs. Claw-free graphs are more general than line graphs, but how much more general are they? Certainly there are claw-free graphs that are not line graphs; for instance, the icosahedron is claw-free, and so is the Schlafli graph, and so is every graph with stability number at most two. Another type of claw-free graph is made as follows: arrange vertices in a circular order, choose some intervals from this circular order, and make two vertices adjacent if and only if one of these intervals contains them both. In general none of these examples are line graphs. In joint work with Maria Chudnovsky, we found an explicit construction for all claw-free graphs. We showed that there are a few "basic" types, such as those described above, and every claw-free graph can be built starting from graphs of these types by piecing them together using simple composition operations. We explain this work.

Michael Todd

Conic linear optimization

In the last decade, there has been considerable interest in solving optimization problems that resemble linear programming problems, except that the nonnegative orthant constraint is replaced by membership in a so-called self-scaled cone. Such problems are of interest because of their wide range of applications, and because (at least for problems of medium scale) there are efficient interior-point methods for their solution. From a mathematical point of view, these cones coincide with symmetric (self-dual and homogeneous) cones, have been characterized, and also arise as cones of squares of Euclidean Jordan algebras. These viewpoints all have implications for solution algorithms.