Newton methods for nonsmooth convex minimization: connections among U-Lagrangian, Riemannian Newton and SQP methods

Scott A. Miller (1) , Jérôme Malick (2)

1 MAE - UC San Diego - Department of Mechanical and Aerospace Engineering [Univ California San Diego]
2 BIPOP - Modelling, Simulation, Control and Optimization of Non-Smooth Dynamical Systems

This paper studies Newton-type methods for minimization of partly smooth convex functions. Sequential Newton methods are provided using local parameterizations obtained from U-Lagrangian theory and from Riemannian geometry. The Hessian based on the U-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 become identical. 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.

Mots clés: NON-SMOOTH OPTIMIZATION; CONVEX ANALYSIS; PARTIAL SMOOTHNESS; U-LAGRANGIAN; RIEMANNIAN GEOMETRY; GEODESICS

Domaines: Autre [cs.OH]

Scott A. Miller, Jérôme Malick. Newton methods for nonsmooth convex minimization: connections among U-Lagrangian, Riemannian Newton and SQP methods. Mathematical Programming, 2005, 104, ⟨10.1007/s10107-005-0631-2⟩. ⟨inria-00071403v2⟩