Berkeley Optimization Day
Saturday, October 1, 2011
Department of Mathematics at UC Berkeley
The second Berkeley Optimization Day will take place in
Evans Hall on Saturday, October 1,
2011. The talks will be from 10:00am to 6:00pm in 60 Evans Hall. This event is part of the Mathematics Department's
Optimization Initiative which is sponsored by
Jeffrey Bohn.
There is no registration fee,
but all participants are kindly requested to register before September 22 by send an email to tran@stat.berkeley.edu. Please let us know your name, affiliation, email address, and whether you have any dietary restrictions.
Schedule
Modern probability theory, whose foundation is based on the axioms set forth
by Kolmogorov, is currently the major tool for performance analysis in
stochastic systems. While it offers insights in understanding such systems,
probability theory is really not a computationally tractable theory.
Correspondingly, some of its major areas of application remain unsolved when
the underlying systems become multidimensional: Queueing networks, network
information theory, pricing multi-dimensional financial contracts, auction
design in multi-item, multi-bidder auctions among others.
We propose a new approach to analyze stochastic systems based on robust
optimization. The key idea is to replace the Kolmogorov axioms as
primitives of
probability theory, with some of the asymptotic implications of probability
theory: the central limit theorem and law of large numbers and to define
appropriate robust optimization problems to perform performance analysis. In
this way, the performance analysis questions become highly structured
optimization problems (linear, conic, mixed integer) for which there exist
efficient, practical algorithms that are capable of solving truly large scale
systems.
We demonstrate that the proposed approach achieves computationally
tractable
methods for (a) analyzing multiclass queueing networks, (b) characterizing
the capacity region of network information theory and associated coding and
decoding methods generalizing the work of Shannon, (c) pricing
multi-dimensional financial contracts generalizing the work of Black, Scholes
and Merton, (d) designing multi-item, multi-bidder auctions generalizing the
work of Myerson.
This is joint work with my doctoral student at MIT Chaitanya Bandi.
An important question at the intersection of optimization and geometry is
whether a given (usually complicated) convex body can be expressed as the
projection of another convex body that is easy to optimize over. In many
interesting cases, this ``lifting'' technique provides polynomial time
algorithms for optimization over the original body. In the past few decades
several lifting techniques have been proposed for combinatorial and
polynomial optimization and all of them have the common feature that they
are intersections of closed convex cones with affine spaces. In this talk I
will formulate the precise conditions that allow a closed convex cone to
admit a lift of a given convex body, generalizing earlier results of Mihalis
Yannakakis. The methods lead to several applications and examples and offer
a uniform view of the existing lift-and-project methods.
Joint work with Joao Gouveia and Pablo Parrilo
I will give a general introduction to PDE-constrained optimization and
high-order accurate numerical methods for fluid and solid mechanics. The
techniques will be demonstrated by a number of examples, from areas such
as topology optimization and structural vibration control. Finally I will
show how to do practical optimal control for the highly challenging
problem of flapping flight, using a combination of computational tools
with varying levels of fidelity.
Nanostructures have been proposed for many applications including solar cells for
renewable energy, new materials for batteries, and biomedical imaging. To fully
explore these ideas however, requires ab initio materials simulations. Today, these
codes are usually based on Density Functional Theory (DFT) that are used for
computing the ground state energy and the corresponding single particle wave
functions associated with a many-electron atomistic system. At the heart of these
codes, one typically finds a Self Consistent Field (SCF) iteration. In this talk, we
propose an optimization procedure that minimizes the Kohn-Sham total energy
directly. We point out the similarities between our new approach and SCF and show
how the SCF iteration can fail. However, by introducing a trust region technique we
can improve the robustness of both methods. Numerical examples demonstrate the
combination of these approaches on several model problems.