|
|
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
MIT
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
RPI
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
Princeton
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
Cornell
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.