A global dual error bound and its application to the analysis of linearly constrained nonconvex optimization

DOI10.1137/20M135474XMaRDI QIDQ5869816zbMATH OpenOpenAlexFDO

Authors Zhi-Quan Luo, Jiawei Zhang

Publication date 29 September 2022

Published in SIAM Journal on Optimization (Search for Journal in Brave)

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

zbMATH Keywords

first orderglobal error bounditeration complexitynonconvexprimal dual

Mathematics Subject Classification ID

Nonconvex programming, global optimization (90C26) Optimality conditions and duality in mathematical programming (90C46)

Abstract: Error bound analysis, which estimates the distance of a point to the solution set of an optimization problem using the optimality residual, is a powerful tool for the analysis of first-order optimization algorithms. In this paper, we use global error bound analysis to study the iteration complexity of a first-order algorithm for a linearly constrained nonconvex minimization problem. we develop a global dual error bound analysis for a regularized version of this nonconvex problem by using a novel ``decomposition technique. Equipped with this global dual error bound, we prove that a suitably designed primal-dual first order method can generate an $epsilon$-stationary solution of the linearly constrained nonconvex minimization problem within $mathcalO(1/epsilo{n}^2)$ iterations, which is the best known iteration complexity for this class of nonconvex problems.

Recommendations

• New error bounds and their applications to convergence analysis of iterative algorithms
• Error bounds and finite termination for constrained optimization problems
• Error bounds for non-polyhedral convex optimization and applications to linear convergence of FDM and PGM
• Complexity of a quadratic penalty accelerated inexact proximal point method for solving linearly constrained nonconvex composite programs
• Complexity analysis of interior point algorithms for non-Lipschitz and nonconvex minimization

Cites work

• A family of inexact SQA methods for non-smooth convex minimization with provable convergence guarantees based on the Luo-Tseng error bound property
• A proximal alternating direction method of multiplier for linearly constrained nonconvex minimization
• Complexity of a quadratic penalty accelerated inexact proximal point method for solving linearly constrained nonconvex composite programs
• Convergence analysis of alternating direction method of multipliers for a family of nonconvex problems
• Error bounds and convergence analysis of feasible descent methods: A general approach
• Error bounds for analytic systems and their applications
• Error bounds for strongly convex programs and (super)linearly convergent iterative schemes for the least 2-norm solution of linear programs
• Error bounds for support vector machines with application to the identification of active constraints
• Error bounds in mathematical programming
• Global convergence of ADMM in nonconvex nonsmooth optimization
• Global convergence of splitting methods for nonconvex composite optimization
• scientific article; zbMATH DE number 1818892 (Why is no real title available?)
• scientific article; zbMATH DE number 3790208 (Why is no real title available?)
• scientific article; zbMATH DE number 1943822 (Why is no real title available?)
• scientific article; zbMATH DE number 1489807 (Why is no real title available?)
• scientific article; zbMATH DE number 2121575 (Why is no real title available?)
• Lower bounds for finding stationary points I
• On a global error bound for a class of monotone affine variational inequality problems
• On Nonconvex Decentralized Gradient Descent
• On the convergence of the coordinate descent method for convex differentiable minimization
• On the Convergence Rate of Dual Ascent Methods for Linearly Constrained Convex Minimization
• On the Linear Convergence of Descent Methods for Convex Essentially Smooth Minimization
• On the linear convergence of the alternating direction method of multipliers
• Optimal Linear Precoding Strategies for Wideband Non-Cooperative Systems Based on Game Theory—Part II: Algorithms
• Perturbed proximal primal-dual algorithm for nonconvex nonsmooth optimization
• Structured nonconvex and nonsmooth optimization: algorithms and iteration complexity analysis

Cited in

(10)

• New error bounds and their applications to convergence analysis of iterative algorithms
• From error bounds to the complexity of first-order descent methods for convex functions
• scientific article; zbMATH DE number 5283371 (Why is no real title available?)
• Stochastic inexact augmented Lagrangian method for nonconvex expectation constrained optimization
• Dual descent augmented Lagrangian method and alternating direction method of multipliers
• A proximal augmented Lagrangian method for linearly constrained nonconvex composite optimization problems
• A hybrid stochastic alternating direction method of multipliers for nonconvex and nonsmooth composite optimization
• An accelerated semi-proximal ADMM with applications to multi-block sparse optimization problems
• Stochastic ADMM with variance-reduced recursive momentum and its accelerated variant for nonconvex nonsmooth optimization
• The augmented Lagrangian methods: overview and recent advances

This page was built for publication: A global dual error bound and its application to the analysis of linearly constrained nonconvex optimization

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