Primal-dual incremental gradient method for nonsmooth and convex optimization problems

DOI10.1007/S11590-021-01752-XzbMATH Open1477.90063OpenAlexW3165002395MaRDI QIDQ2230784FDOQ2230784

Authors Afrooz Jalilzadeh 

Publication date 28 September 2021

Published in Optimization Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2011.02059

zbMATH Keywords

convex optimizationnonsmooth optimizationprimal-dual methodincremental gradient

Mathematics Subject Classification ID

Convex programming (90C25)

Abstract: In this paper, we consider a nonsmooth convex finite-sum problem with a conic constraint. To overcome the challenge of projecting onto the constraint set and computing the full (sub)gradient, we introduce a primal-dual incremental gradient scheme where only a component function and two constraints are used to update each primal-dual sub-iteration in a cyclic order. We demonstrate an asymptotic sublinear rate of convergence in terms of suboptimality and infeasibility which is an improvement over the state-of-the-art incremental gradient schemes in this setting. Numerical results suggest that the proposed scheme compares well with competitive methods.

Recommendations

• Incremental subgradient method for nonsmooth convex optimization with fixed point constraints
• On convergence analysis of dual proximal-gradient methods with approximate gradient for a class of nonsmooth convex minimization problems
• Incremental subgradients for constrained convex optimization: A unified framework and new methods
• Incremental proximal gradient scheme with penalization for constrained composite convex optimization problems
• Primal-dual subgradient methods for convex problems

Cites Work

• scientific article; zbMATH DE number 2121575 (Why is no real title available?)
• A Convergent Incremental Gradient Method with a Constant Step Size
• A primal-dual algorithm with line search for general convex-concave saddle point problems
• Algorithms for Fitting the Constrained Lasso
• Compressed sensing
• Incremental subgradient methods for nondifferentiable optimization
• Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
• On smoothing, regularization, and averaging in stochastic approximation methods for stochastic variational inequality problems
• On the Convergence Rate of Incremental Aggregated Gradient Algorithms
• Primal-Dual Stochastic Gradient Method for Convex Programs with Many Functional Constraints
• Stochastic Primal-Dual Hybrid Gradient Algorithm with Arbitrary Sampling and Imaging Applications
• Stochastic primal-dual coordinate method for regularized empirical risk minimization

Cited In (10)

• Running Primal-Dual Gradient Method for Time-Varying Nonconvex Problems
• Perturbed proximal primal-dual algorithm for nonconvex nonsmooth optimization
• The Primal-Dual Hybrid Gradient Method for Semiconvex Splittings
• A dual method for minimizing a nonsmooth objective over one smooth inequality constraint
• Incremental proximal gradient scheme with penalization for constrained composite convex optimization problems
• A primal-dual approach to inexact subgradient methods
• Inexact primal-dual gradient projection methods for nonlinear optimization on convex set
• An incremental primal-dual method for nonlinear programming with special structure
• Non-stationary First-Order Primal-Dual Algorithms with Faster Convergence Rates
• Primal-Dual Stochastic Gradient Method for Convex Programs with Many Functional Constraints

Uses Software

• Saga
• ConstrainedLasso

This page was built for publication: Primal-dual incremental gradient method for nonsmooth and convex optimization problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2230784)