A VU-algorithm for convex minimization

Claudia Sagastizabal | Mifflin, Robert

Keywords: onvex minimization | proximal points | bundle methods | $\V\U$-decomposition | superlinear convergence.

For convex minimization we introduce an algorithm based on $\V\U$-space decomposition. The method uses a bundle subroutine to generate a sequence of approximate proximal points. When a primal-dual track leading to a solution and zero subgradient pair exists these points approximate the primal track points and give the algorithm's $\V$ or corrector steps. The subroutine also approximates dual track points that are $\U$-gradients needed for the method's $\U$-Newton predictor steps. With the inclusion of a simple line search the resulting algorithm is proved to be globally convergent. The convergence is superlinear if the primal-dual track points and the objective's $\U$-Hessian are approximated well enough.

Anexos:

• NewFormatvualgo.pdf