Proximal minimization algorithms with cutting planes
Abstract
This paper examines a class of proximal minimization algorithms in which the objective function of the underlying convex program is approximated by cutting planes. This class includes algorithms such as cutting plane, cutting plane with line search and bundle methods. Among these algorithms, the bundle methods can be viewed as a quadratic counterpart of the cutting plane algorithm with line search, for they both attempt to decrease the true objective function at every iteration. On the other hand, the cutting plane algorithm does not explicitly and/or directly attempt to decrease the true objective function. However, it relies on the monotonicity of the approximating function to guarantee convergence to an optimal solution. This prompts the question of whether there exists a quadratic counterpart for the cutting plane algorithm. To provide an affirmative answer, this paper constructs a new convergent algorithm which resembles, but is different from, the bundle methods. Also, to make the relationship between bundle methods and proximal minimization more concrete, this paper also supplies a convergence proof for a variant of the bundle methods which utilizes analysis common to proximal minimization
NPS Report Number
NPS-OR-92-011Related items
Showing items related by title, author, creator and subject.
-
Route Optimization for Multiple Searchers
Royset, J.O.,; Sato, H. (2010);We consider a discrete time-and-space route-optimization problem across a finite time horizon in which multiple searchers seek to detect one or more probabilistically mov- ing targets. The paper formulates a novel convex ... -
A cascade approach for staircase linear programs with an application to Air Force mobility optimization
Baker, Steven F. (Monterey, California. Naval Postgraduate School, 1997-06);We develop a method to approximately solve a large staircase linear program that optimizes decisions over time. Also developed is a method to bound that approximation's error. A feasible solution is derived by a proximal ... -
Nucleate pool boiling performance of finned and high flux tube bundles in R-114/oil mixtures
Akcasayar, Nezih (Monterey, California. Naval Postgraduate School, 1989-12);The heat transfer characteristics of pure R-114 and R-114/oil mixtures during nucleate pool boiling from a small bundle of finned and High Flux tubes were measured. The bundles had 5 instrumented and 10 additional heated ...