A Unifying Polyhedral Approximation Framework for Convex Optimization
Author(s)
Bertsekas, Dimitri P.; Yu, Huizhen
DownloadBertsekas-2011-A UNIFYING POLYHEDRAL APPROXIMATION FRAMEWORK.pdf (1.046Mb)
PUBLISHER_POLICY
Publisher Policy
Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use.
Terms of use
Metadata
Show full item recordAbstract
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 for the general case where outer and inner linearization are combined in the same algorithm.
Date issued
2011-03Department
Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science; Massachusetts Institute of Technology. Laboratory for Information and Decision SystemsJournal
SIAM Journal on Optimization
Publisher
Society for Industrial and Applied Mathematics
Citation
Bertsekas, Dimitri P., and Huizhen Yu. “A Unifying Polyhedral Approximation Framework for Convex Optimization.” SIAM Journal on Optimization 21 (2011): 333. © 2011 Society for Industrial and Applied Mathematics.
Version: Final published version
ISSN
1052-6234
1095-7189