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