An Algorithm Design Framework for Linearly Constrained Convex Optimization: Proximal and Contractive Perspectives

• 成果类型: Article
• 署名作者: Wu, Zhaolong; Zhao, Xiaowei
• 署名单位: University of Warwick
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2024.3428071
• 发表日期: 2025
• 页码: 495-502
• 关键词: Prediction algorithms; CONVERGENCE; Convex functions; Design methodology; Linear matrix inequalities; linear programming; Lagrangian functions; Augmented Lagrangian method; Contraction theory; Convex Optimization; proximal point method

摘要

This article presents an algorithm design framework for general linearly constrained convex optimization problems. Our approach offers a flexible framework to analyze and design various methods, drawing from proximal and contractive viewpoints. This framework utilizes a predictor-corrector mechanism, in which the predictor's role is to generate a predicted solution through proximally contractive mapping, and the corrector's objective is to refine this predicted solution via an inertial update rule. We proceed to provide a convergence analysis for our algorithm design framework by using proximal-point and contraction inequality techniques. Our analysis demonstrates that methods developed within this framework are guaranteed to converge and achieve an ergodic sublinear convergence rate of O(1/k) in the worst-case scenario. Moreover, our approach is capable of ensuring convergence with a nonergodic rate for the linearly equality-constrained convex optimization problems. Finally, we have verified the effectiveness of our framework and design guidelines via some Lagrangian-based methods for one-block, two-block, and multiblock problems.