Complexity of a Quadratic Penalty Accelerated Inexact Proximal Point Method for Solving Linearly Constrained Nonconvex Composite Programs

DOI10.1137/18M1171011zbMath1504.90101arXiv1802.03504MaRDI QIDQ5237309

WeiWei Kong, Renato D. C. Monteiro, Jefferson G. Melo

Publication date: 17 October 2019

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

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

zbMATH Keywords

iteration complexity; inexact proximal point method; quadratic penalty method; first-order accelerated gradient method; composite nonconvex program

Mathematics Subject Classification ID

90C60: Abstract computational complexity for mathematical programming problems

90C26: Nonconvex programming, global optimization

90C30: Nonlinear programming

65K10: Numerical optimization and variational techniques

47J22: Variational and other types of inclusions

Related Items

First-Order Methods for Problems with $O$(1) Functional Constraints Can Have Almost the Same Convergence Rate as for Unconstrained Problems, A Proximal Alternating Direction Method of Multiplier for Linearly Constrained Nonconvex Minimization, An Average Curvature Accelerated Composite Gradient Method for Nonconvex Smooth Composite Optimization Problems, An Accelerated Inexact Proximal Point Method for Solving Nonconvex-Concave Min-Max Problems, Accelerated Stochastic Algorithms for Nonconvex Finite-Sum and Multiblock Optimization, A Global Dual Error Bound and Its Application to the Analysis of Linearly Constrained Nonconvex Optimization, Reducing the Complexity of Two Classes of Optimization Problems by Inexact Accelerated Proximal Gradient Method, Iteration Complexity of an Inner Accelerated Inexact Proximal Augmented Lagrangian Method Based on the Classical Lagrangian Function, An adaptive superfast inexact proximal augmented Lagrangian method for smooth nonconvex composite optimization problems, An accelerated inexact dampened augmented Lagrangian method for linearly-constrained nonconvex composite optimization problems, Worst-case evaluation complexity of a quadratic penalty method for nonconvex optimization, A Newton-CG Based Augmented Lagrangian Method for Finding a Second-Order Stationary Point of Nonconvex Equality Constrained Optimization with Complexity Guarantees, Average curvature FISTA for nonconvex smooth composite optimization problems, NC-OPT, A FISTA-type accelerated gradient algorithm for solving smooth nonconvex composite optimization problems, QPALM: a proximal augmented Lagrangian method for nonconvex quadratic programs, Extrapolated smoothing descent algorithm for constrained nonconvex and nonsmooth composite problems, Complexity of an inexact proximal-point penalty method for constrained smooth non-convex optimization, Accelerated inexact composite gradient methods for nonconvex spectral optimization problems, An efficient adaptive accelerated inexact proximal point method for solving linearly constrained nonconvex composite problems

Cites Work

• Unnamed Item
• Accelerated gradient methods for nonconvex nonlinear and stochastic programming
• Gradient methods for minimizing composite functions
• Adaptive inexact fast augmented Lagrangian methods for constrained convex optimization
• A block coordinate variable metric forward-backward algorithm
• On the convergence of the proximal algorithm for nonsmooth functions involving analytic features
• Introductory lectures on convex optimization. A basic course.
• A hybrid approximate extragradient-proximal point algorithm using the enlargement of a maximal monotone operator
• Structured nonconvex and nonsmooth optimization: algorithms and iteration complexity analysis
• Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods
• Iteration-complexity of first-order penalty methods for convex programming
• Alternating forward-backward splitting for linearly constrained optimization problems
• Efficiency of minimizing compositions of convex functions and smooth maps
• Splitting methods with variable metric for Kurdyka-Łojasiewicz functions and general convergence rates
• The Rate of Convergence of Nesterov's Accelerated Forward-Backward Method is Actually Faster Than $1/k^2$
• An Accelerated Hybrid Proximal Extragradient Method for Convex Optimization and Its Implications to Second-Order Methods
• A First-Order Smoothed Penalty Method for Compressed Sensing
• On the Complexity of the Hybrid Proximal Extragradient Method for the Iterates and the Ergodic Mean
• Accelerating Block-Decomposition First-Order Methods for Solving Composite Saddle-Point and Two-Player Nash Equilibrium Problems
• An Accelerated HPE-Type Algorithm for a Class of Composite Convex-Concave Saddle-Point Problems
• Accelerated Methods for NonConvex Optimization
• An accelerated non-Euclidean hybrid proximal extragradient-type algorithm for convex–concave saddle-point problems
• Complexity of first-order inexact Lagrangian and penalty methods for conic convex programming
• An Accelerated Linearized Alternating Direction Method of Multipliers
• Iteration-complexity of first-order augmented Lagrangian methods for convex programming