A VU-algorithm for convex minimization

✍ Scribed by Robert Mifflin; Claudia Sagastizábal

• Publisher: Springer-Verlag
• Year: 2005
• Tongue: English
• Weight: 278 KB
• Volume: 104
• Category: Article
• ISSN: 0025-5610
• DOI: 10.1007/s10107-005-0630-3

✦ Synopsis

For convex minimization we introduce an algorithm based on VU-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.