Strong Metric (Sub)regularity of Karush-Kuhn-Tucker Mappings for Piecewise Linear-Quadratic Convex-Composite Optimization and the Quadratic Convergence of Newton's Method

• 成果类型: Article
• 署名作者: Burke, James, V; Engle, Abraham
• 署名单位: University of Washington; University of Washington Seattle
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2019.1027
• 发表日期: 2020
• 页码: 1164-1192
• 关键词: optimality conditions; local properties; algorithms; 2ND-ORDER; constraints

摘要

This work concerns the local convergence theory of Newton and quasi-Newton methods for convex composite optimization: where one minimizes an objective that can be written as the composition of a convex function with one that is continuiously differentiable. We focus on the case in which the convex function is a potentially infinite-valued piecewise linear-quadratic function. Such problems include nonlinear programming, minimax optimization, and estimation of nonlinear dynamics with non-Gaussian noise as well as many modem approaches to large-scale data analysis and machine learning. Our approach embeds the optimality conditions for convex-composite optimization problems into a generalized equation. We establish conditions for strong metric subregularity and strong metric regularity of the corresponding set-valued mappings. This allows us to extend classical convergence of Newton and quasi-Newton methods to the broader class of nonfinite valued piecewise linear quadratic convex-composite optimization problems. In particular, we establish local quadratic convergence of the Newton method under conditions that parallel those in nonlinear programming.