We consider minimization of functions that are compositions of convex or prox-regular functions (possibly extended-valued) with smooth vector functions. A wide variety of important optimization problems fall into this framework. We describe an algorithmic framework based on a subproblem constructed from a linearized approximation to the objective and a regularization term. Properties of local solutions of this subproblem underlie both a global convergence result and an identification property of the active manifold containing the solution of the original problem. Preliminary computational results on both convex and nonconvex examples are promising.
Mifflin and Sagastiz 'abal @cite_17 describe an algorithm in which an approximate solution of the subproblem prox.gen is obtained, again for the case of a convex objective, by making use of a piecewise linear underapproximation to their objective @math . The approach is most suitable for a bundle method in which the piecewise-linear approximation is constructed from subgradients gathered at previous iterations. Approximations to the manifold of smoothness for @math are constructed from the solution of this approximate proximal point calculation, and a Newton-like step for the Lagrangian is taken along this manifold, as envisioned in earlier methods. Daniilidis, Hare, and Malick @cite_34 use the terminology predictor-corrector'' to describe algorithms of this type. Their predictor'' step is the step along the manifold of smoothness for @math , while the corrector'' step ) eventually returns the iterates to the correct active manifold (see [Theorem 28] DanHM06 ). Miller and Malick @cite_4 show how algorithms of this type are related to Newton-like methods that have been proposed earlier in various contexts.
@cite_34 @cite_4 @cite_17
1601741115 2139313686 2094993225
Basic notation.- Introduction.- Background material.- Optimality conditions.- Basic perturbation theory.- Second order analysis of the optimal value and optimal solutions.- Optimal Control.- References. This paper studies Newton-type methods for minimization of partly smooth convex functions. Sequential Newton methods are provided using local parameterizations obtained from **-Lagrangian theory and from Riemannian geometry. The Hessian based on the **-Lagrangian depends on the selection of a dual parameter g; by revealing the connection to Riemannian geometry, a natural choice of g emerges for which the two Newton directions coincide. This choice of g is also shown to be related to the least-squares multiplier estimate from a sequential quadratic programming (SQP) approach, and with this multiplier, SQP gives the same search direction as the Newton methods. For convex minimization we introduce an algorithm based on **-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 **, or corrector, steps. The subroutine also approximates dual track points that are **-gradients needed for the method's **-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 **-Hessian are approximated well enough.