Optimization Online


A Unifying Polyhedral Approximation Framework for Convex Optimization

Dimitri Bertsekas(dimitrib***at***mit.edu)
Huizhen Yu(janey.yu***at***cs.helsinki.fi)

Abstract: We propose a unifying framework for polyhedral approximation in convex optimization. It subsumes classical methods, such as cutting plane and simplicial decomposition, but also includes new methods, and new versions/extensions of old methods, such as a simplicial decomposition method for nondifferentiable optimization, and a new piecewise linear approximation method for convex single commodity network flow problems. Our framework is based on an extended form of monotropic programming, a broadly applicable model, which includes as special cases Fenchel duality and Rockafellar's monotropic programming, and is characterized by an elegant and symmetric duality theory. Our algorithm combines flexibly outer and inner linearization of the cost function. The linearization is progressively refined by using primal and dual differentiation, and the roles of outer and inner linearization are reversed in a mathematically equivalent dual algorithm. We provide convergence results and error bounds for the general case where outer and inner linearization are combined in the same algorithm.

Keywords: Convex optimization, monotropic programming, cutting plane, simpicial decomposition

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Category 2: Network Optimization

Citation: Lab. for Information and Decision Systems Report LIDS-P-2820, MIT, September 2009

Download: [PDF]

Entry Submitted: 10/02/2009
Entry Accepted: 10/02/2009
Entry Last Modified: 10/02/2009

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