Optimization Online


A cutting surface algorithm for semi-infinite convex programming with an application to moment robust optimization

Sanjay Mehrotra (mehrotra***at***iems.northwestern.edu)
David Papp (dpapp***at***iems.northwestern.edu)

Abstract: We first present and analyze a central cutting surface algorithm for general semi-infinite convex optimization problems, and use it to develop an algorithm for distributionally robust optimization problems in which the uncertainty set consists of probability distributions with given bounds on their moments. The cutting surface algorithm is also applicable to problems with non-differentiable semi-infinite constraints indexed by an infinite-dimensional index set. Examples comparing the cutting surface algorithm to the central cutting plane algorithm of Kortanek and No demonstrate the potential of the central cutting surface algorithm even in the solution of traditional semi-infinite convex programming problems, whose constraints are differentiable, and are indexed by an index set of low dimension. Our primary motivation for the higher level of generality is to solve distributionally robust optimization problems with moment uncertainty. After the analysis of the cutting surface algorithm, we extend the authors' moment matching scenario generation algorithm to a probabilistic algorithm that finds optimal probability distributions subject to moment constraints. The combination of this distribution optimization method and the cutting surface algorithm yields a solution to a family of distributionally robust optimization problems that are considerably more general than the ones proposed to date.

Keywords: semi-infinite programming, robust optimization, stochastic programming, moment matching, column generation, cutting surface methods, cutting plane methods, moment problem

Category 1: Infinite Dimensional Optimization (Semi-infinite Programming )

Category 2: Robust Optimization

Category 3: Stochastic Programming

Citation: Unpublished; submitted for publication.

Download: [PDF]

Entry Submitted: 06/14/2013
Entry Accepted: 06/14/2013
Entry Last Modified: 06/17/2013

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 Optimization Society