Optimization Online


Cutting-Set Methods for Robust Convex Optimization with Pessimizing Oracles

Almir Mutapcic (almirm***at***stanford.edu)
Stephen Boyd (boyd***at***stanford.edu)

Abstract: We consider a general worst-case robust convex optimization problem, with arbitrary dependence on the uncertain parameters, which are assumed to lie in some given set of possible values. We describe a general method for solving such a problem, which alternates between optimization and worst-case analysis. With exact worst-case analysis, the method is shown to converge to a robust optimal point. With approximate worst-case analysis, which is the best we can do in many practical cases, the method seems to work very well in practice, subject to the errors in our worst-case analysis. We give variations on the basic method that can give enhanced convergence, reduce data storage, or improve other algorithm properties. Numerical simulations suggest that the method finds a quite robust solution within a few tens of steps; using warm-start techniques in the optimization steps reduces the overall effort to a modest multiple of solving a nominal problem, ignoring the parameter variation. The method is illustrated with several application examples.

Keywords: robust optimization, cutting-set methods, semi-infinite programming, minimax optimization

Category 1: Robust Optimization

Citation: Manuscript

Download: [PDF]

Entry Submitted: 04/01/2008
Entry Accepted: 04/01/2008
Entry Last Modified: 04/01/2008

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society