Stochastic Halfspace Approximation Method for Convex Optimization With Nonsmooth Functional Constraints

• 成果类型: Article
• 署名作者: Singh, Nitesh Kumar; Necoara, Ion
• 署名单位: National University of Science & Technology POLITEHNICA Bucharest
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2024.3426888
• 发表日期: 2025
• 页码: 479-486
• 关键词: convergence; Convex functions; linear programming; Approximation algorithms; Signal processing algorithms; optimization; Systems engineering and theory; Convex Optimization; nonsmooth functional constraints; stochastic halfspace approximation; stochastic projection gradient methods

摘要

In this work, we consider convex optimization problems with smooth objective function and nonsmooth functional constraints. We propose a new stochastic gradient algorithm, called the stochastic halfspace approximation method (SHAM), to solve this problem, where at each iteration we first take a gradient step for the objective function and then we perform a projection step onto one halfspace approximation of a randomly chosen constraint. We propose various strategies to create this stochastic halfspace approximation and we provide a unified convergence analysis that yields new convergence rates for the SHAM algorithm in both optimality and feasibility criteria evaluated at some average point. In particular, we derive convergence rates of order O(1/root k) , when the objective function is only convex, and O(1/k) when the objective function is strongly convex. The efficiency of SHAM is illustrated through detailed numerical simulations.