Convergence Rate of a Penalty Method for Strongly Convex Problems with\n Linear Constraints

2020/04/28 by Angelia Nedich, Nedich, Angelia, Tatiana Tatarenko +1
Computer Science · Engineering · Mathematics · #Advanced Optimization Algorithms Research #FOS: Mathematics #Numerical methods in inverse problems #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.2004.13417

openalex publication_date 2020/04/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We consider an optimization problem with strongly convex objective and linear\ninequalities constraints. To be able to deal with a large number of constraints\nwe provide a penalty reformulation of the problem. As penalty functions we use\na version of the one-sided Huber losses. The smoothness properties of these\nfunctions allow us to choose time-varying penalty parameters in such a way that\nthe incremental procedure with the diminishing step-size converges to the exact\nsolution with the rate O(1/\√ k). To the best of our knowledge, we\npresent the first result on the convergence rate for the penalty-based gradient\nmethod, in which the penalty parameters vary with time.\n

Related

• Huber Loss-Based Penalty Approach to Problems with Linear Constraints
• A Smooth Inexact Penalty Reformulation of Convex Problems with Linear\n Constraints
• Convergence Rates Analysis of The Quadratic Penalty Method and Its Applications to Decentralized Distributed Optimization
• New Penalized Stochastic Gradient Methods for Linearly Constrained Strongly Convex Optimization
• On the Softplus Penalty for Constrained Convex Optimization