Structured nonconvex and nonsmooth optimization: algorithms and iteration complexity analysis

DOI10.1007/s10589-018-0034-yzbMath1411.90274arXiv1605.02408OpenAlexW2964271484WikidataQ129193937 ScholiaQ129193937MaRDI QIDQ1734769

Bo Jiang, Shu-Zhong Zhang, Tian-Yi Lin, Shi-Qian Ma

Publication date: 27 March 2019

Published in: Computational Optimization and Applications (Search for Journal in Brave)

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

zbMATH Keywords

block coordinate descent methodalternating direction method of multipliersconditional gradient methoditeration complexity\(\epsilon\)-stationarystructured nonconvex optimization

Mathematics Subject Classification ID

Large-scale problems in mathematical programming (90C06) Abstract computational complexity for mathematical programming problems (90C60) Nonconvex programming, global optimization (90C26)

Related Items

On inexact stochastic splitting methods for a class of nonconvex composite optimization problems with relative error, Iteration Complexity of an Inner Accelerated Inexact Proximal Augmented Lagrangian Method Based on the Classical Lagrangian Function, Managing randomization in the multi-block alternating direction method of multipliers for quadratic optimization, Complexity of an inexact proximal-point penalty method for constrained smooth non-convex optimization, A survey on some recent developments of alternating direction method of multipliers, Fast and stable nonconvex constrained distributed optimization: the ELLADA algorithm, Douglas-Rachford splitting and ADMM for nonconvex optimization: accelerated and Newton-type linesearch algorithms, A truncated Newton algorithm for nonconvex sparse recovery, Moreau envelope augmented Lagrangian method for nonconvex optimization with linear constraints, Convergence of linear Bregman ADMM for nonconvex and nonsmooth problems with nonseparable structure, An adaptive superfast inexact proximal augmented Lagrangian method for smooth nonconvex composite optimization problems, A nonlinear kernel SVM Classifier via \(L_{0/1}\) soft-margin loss with classification performance, An accelerated inexact dampened augmented Lagrangian method for linearly-constrained nonconvex composite optimization problems, Convergence analysis of an improved Bregman-type Peaceman-Rachford splitting algorithm for nonconvex nonseparable linearly constrained optimization problems, Complexity analysis of a stochastic variant of generalized alternating direction method of multipliers, Global Complexity Bound of a Proximal ADMM for Linearly Constrained Nonseparable Nonconvex Composite Programming, Convergence of Bregman Peaceman-Rachford splitting method for nonconvex nonseparable optimization, Alternating direction method of multipliers for nonconvex log total variation image restoration, A two-level distributed algorithm for nonconvex constrained optimization, Primal-dual optimization algorithms over Riemannian manifolds: an iteration complexity analysis, A Proximal Alternating Direction Method of Multiplier for Linearly Constrained Nonconvex Minimization, A Unified Adaptive Tensor Approximation Scheme to Accelerate Composite Convex Optimization, Unnamed Item, An incremental aggregated proximal ADMM for linearly constrained nonconvex optimization with application to sparse logistic regression problems, Multi-block nonconvex nonsmooth proximal ADMM: convergence and rates under Kurdyka-Łojasiewicz property, Conditional Gradient Methods for Convex Optimization with General Affine and Nonlinear Constraints, Alternating direction method of multipliers for a class of nonconvex bilinear optimization: convergence analysis and applications, Complexity of proximal augmented Lagrangian for nonconvex optimization with nonlinear equality constraints, Local linear convergence of the alternating direction method of multipliers for nonconvex separable optimization problems, Tractable ADMM schemes for computing KKT points and local minimizers for \(\ell_0\)-minimization problems, An extended proximal ADMM algorithm for three-block nonconvex optimization problems, ADMM for multiaffine constrained optimization, A Proximal Minimization Algorithm for Structured Nonconvex and Nonsmooth Problems, Complexity of a Quadratic Penalty Accelerated Inexact Proximal Point Method for Solving Linearly Constrained Nonconvex Composite Programs, An adaptive high order method for finding third-order critical points of nonconvex optimization, An inertial proximal partially symmetric ADMM-based algorithm for linearly constrained multi-block nonconvex optimization problems with applications, Convergence and rate analysis of a proximal linearized ADMM for nonconvex nonsmooth optimization, A Global Dual Error Bound and Its Application to the Analysis of Linearly Constrained Nonconvex Optimization

Uses Software

• LMaFit

Cites Work

• Unnamed Item
• Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers
• Alternating direction method of multipliers for penalized zero-variance discriminant analysis
• Nearly unbiased variable selection under minimax concave penalty
• A smoothing SQP framework for a class of composite \(L_q\) minimization over polyhedron
• Iteration complexity analysis of multi-block ADMM for a family of convex minimization without strong convexity
• First-order methods of smooth convex optimization with inexact oracle
• Proximal alternating linearized minimization for nonconvex and nonsmooth problems
• Conditional gradient algorithms for norm-regularized smooth convex optimization
• A trust region algorithm with a worst-case iteration complexity of \(\mathcal{O}(\epsilon ^{-3/2})\) for nonconvex optimization
• Adaptive cubic regularisation methods for unconstrained optimization. II: Worst-case function- and derivative-evaluation complexity
• Enhancing sparsity by reweighted \(\ell _{1}\) minimization
• A generalized conditional gradient method and its connection to an iterative shrinkage method
• On gradients of functions definable in o-minimal structures
• Introductory lectures on convex optimization. A basic course.
• Extensions of Fréchet \(\varepsilon\)-subdifferential calculus and applications
• Global convergence of unmodified 3-block ADMM for a class of convex minimization problems
• On the information-adaptive variants of the ADMM: an iteration complexity perspective
• Cubic-regularization counterpart of a variable-norm trust-region method for unconstrained minimization
• An improved algorithm for the \(L_2-L_p\) minimization problem
• Solving a low-rank factorization model for matrix completion by a nonlinear successive over-relaxation algorithm
• Alternating proximal gradient method for sparse nonnegative Tucker decomposition
• Linearly convergent away-step conditional gradient for non-strongly convex functions
• Approximate KKT points and a proximity measure for termination
• Multi-stage convex relaxation for feature selection
• Complexity of unconstrained \(L_2 - L_p\) minimization
• Complexity analysis of interior point algorithms for non-Lipschitz and nonconvex minimization
• Conditional Gradient Sliding for Convex Optimization
• Scalable Robust Matrix Recovery: Frank--Wolfe Meets Proximal Methods
• Worst-Case Complexity of Smoothing Quadratic Regularization Methods for Non-Lipschitzian Optimization
• Duality Between Subgradient and Conditional Gradient Methods
• Convergence Analysis of Alternating Direction Method of Multipliers for a Family of Nonconvex Problems
• On the Complexity of Steepest Descent, Newton's and Regularized Newton's Methods for Nonconvex Unconstrained Optimization Problems
• Proximal Alternating Minimization and Projection Methods for Nonconvex Problems: An Approach Based on the Kurdyka-Łojasiewicz Inequality
• Global Convergence of Splitting Methods for Nonconvex Composite Optimization
• Clarke Subgradients of Stratifiable Functions
• Characterizations of Łojasiewicz inequalities: Subgradient flows, talweg, convexity
• A forward–backward splitting algorithm for the minimization of non-smooth convex functionals in Banach space
• Variational Analysis
• Variable Selection via Nonconcave Penalized Likelihood and its Oracle Properties
• A Distributed, Asynchronous, and Incremental Algorithm for Nonconvex Optimization: An ADMM Approach
• Generalized Conditional Gradient for Sparse Estimation
• An adaptive cubic regularization algorithm for nonconvex optimization with convex constraints and its function-evaluation complexity
• Conditional Gradient Algorithmsfor Rank-One Matrix Approximations with a Sparsity Constraint
• Alternating Direction Method of Multipliers for a Class of Nonconvex and Nonsmooth Problems with Applications to Background/Foreground Extraction
• Tensor and its tucker core: The invariance relationships
• The Łojasiewicz Inequality for Nonsmooth Subanalytic Functions with Applications to Subgradient Dynamical Systems
• Augmented Lagrangian alternating direction method for matrix separation based on low-rank factorization
• New analysis and results for the Frank-Wolfe method
• Mini-batch stochastic approximation methods for nonconvex stochastic composite optimization