Berkeley Optimization Day

Saturday, October 1, 2011
Department of Mathematics at UC Berkeley

Organizers: Craig Evans and Bernd Sturmfels

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

Dmitris Bertsimas: A robust optimization based theory of performance analysis in stochastic


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.



Rekha Thomas: Lifts of Convex Sets and Cone Factorizations


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



Per-Olof Persson: High-Fidelity Simulation of Flapping Wings Designed for Energetically Optimal Flight


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.



Juan Meza: A Direct Constrained Optimization Method for the Kohn-Sham Equations


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.