Proximal minimization algorithms with cutting planes
By: Siriphong Lawphongpanich
Contributors: Naval Postgraduate School (U.S.). Dept. of Operations Research
Publisher: Naval Postgraduate School; Available from National Technical Information Service
Published: 1991
Place of publication: Monterey, Calif; Springfield, Va
Language: eng
Number of pages: 41
Subjects: Convergence; Mathematical programming; Algorithms
Other titles: NPS-OR-92-011.
Description: 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.
Notes: Title from cover.

"NPS-OR-92-011."

"December 1991."

AD A246 436.

Includes bibliographical references (p. 25-27).

aq/aq cc:9116 01/20/98