Preprint A301/2004
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.