A New Homotopy Proximal Variable-Metric Framework for Composite Convex Minimization

• 成果类型: Article
• 署名作者: Quoc Tran-Dinh; Liang, Ling; Toh, Kim-Chuan
• 署名单位: University of North Carolina; University of North Carolina Chapel Hill; National University of Singapore; National University of Singapore
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2021.1138
• 发表日期: 2022
• 页码: 508-539
• 关键词: Augmented Lagrangian method; COVARIANCE ESTIMATION; cubic regularization; Newton method; algorithms; selection; designs

摘要

This paper suggests two novel ideas to develop new proximal variable-metric methods for solving a class of composite convex optimization problems. The first idea is to utilize a new parameterization strategy of the optimality condition to design a class of homotopy proximal variable-metric algorithms that can achieve linear convergence and finite global iteration-complexity bounds. We identify at least three subclasses of convex problems in which our approach can apply to achieve linear convergence rates. The second idea is a new primal-dual-primal framework for implementing proximal Newton methods that has attractive computational features for a subclass of nonsmooth composite convex minimization problems. We specialize the proposed algorithm to solve a covariance estimation problem in order to demonstrate its computational advantages. Numerical experiments on the four concrete applications are given to illustrate the theoretical and computational advances of the new methods compared with other state-of-the-art algorithms.