Structured nonconvex and nonsmooth optimization: algorithms and iteration complexity analysis
From MaRDI portal
Publication:1734769
Abstract: Nonconvex and nonsmooth optimization problems are frequently encountered in much of statistics, business, science and engineering, but they are not yet widely recognized as a technology in the sense of scalability. A reason for this relatively low degree of popularity is the lack of a well developed system of theory and algorithms to support the applications, as is the case for its convex counterpart. This paper aims to take one step in the direction of disciplined nonconvex and nonsmooth optimization. In particular, we consider in this paper some constrained nonconvex optimization models in block decision variables, with or without coupled affine constraints. In the case of without coupled constraints, we show a sublinear rate of convergence to an -stationary solution in the form of variational inequality for a generalized conditional gradient method, where the convergence rate is shown to be dependent on the H"olderian continuity of the gradient of the smooth part of the objective. For the model with coupled affine constraints, we introduce corresponding -stationarity conditions, and apply two proximal-type variants of the ADMM to solve such a model, assuming the proximal ADMM updates can be implemented for all the block variables except for the last block, for which either a gradient step or a majorization-minimization step is implemented. We show an iteration complexity bound of to reach an -stationary solution for both algorithms. Moreover, we show that the same iteration complexity of a proximal BCD method follows immediately. Numerical results are provided to illustrate the efficacy of the proposed algorithms for tensor robust PCA.
Recommendations
- Primal-dual optimization algorithms over Riemannian manifolds: an iteration complexity analysis
- Global convergence of ADMM in nonconvex nonsmooth optimization
- Perturbed proximal primal-dual algorithm for nonconvex nonsmooth optimization
- A proximal alternating direction method of multiplier for linearly constrained nonconvex minimization
- Block-coordinate and incremental aggregated proximal gradient methods for nonsmooth nonconvex problems
Cites work
- A Distributed, Asynchronous, and Incremental Algorithm for Nonconvex Optimization: An ADMM Approach
- A forward–backward splitting algorithm for the minimization of non-smooth convex functionals in Banach space
- A generalized conditional gradient method and its connection to an iterative shrinkage method
- A smoothing SQP framework for a class of composite L_q minimization over polyhedron
- 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
- Alternating direction method of multipliers for a class of nonconvex and nonsmooth problems with applications to background/foreground extraction
- Alternating direction method of multipliers for penalized zero-variance discriminant analysis
- Alternating proximal gradient method for sparse nonnegative Tucker decomposition
- An adaptive cubic regularization algorithm for nonconvex optimization with convex constraints and its function-evaluation complexity
- An improved algorithm for the \(L_2-L_p\) minimization problem
- Analysis of multi-stage convex relaxation for sparse regularization
- Approximate KKT points and a proximity measure for termination
- Augmented Lagrangian alternating direction method for matrix separation based on low-rank factorization
- Characterizations of Łojasiewicz inequalities: Subgradient flows, talweg, convexity
- Clarke Subgradients of Stratifiable Functions
- Complexity analysis of interior point algorithms for non-Lipschitz and nonconvex minimization
- Complexity of unconstrained \(L_2 - L_p\) minimization
- Conditional gradient algorithms for norm-regularized smooth convex optimization
- Conditional gradient algorithms for rank-one matrix approximations with a sparsity constraint
- Conditional gradient sliding for convex optimization
- Convergence analysis of alternating direction method of multipliers for a family of nonconvex problems
- Cubic-regularization counterpart of a variable-norm trust-region method for unconstrained minimization
- Distributed optimization and statistical learning via the alternating direction method of multipliers
- Duality between subgradient and conditional gradient methods
- Enhancing sparsity by reweighted \(\ell _{1}\) minimization
- Extensions of Fréchet -subdifferential calculus and applications
- First-order methods of smooth convex optimization with inexact oracle
- Generalized conditional gradient for sparse estimation
- Global convergence of splitting methods for nonconvex composite optimization
- Global convergence of unmodified 3-block ADMM for a class of convex minimization problems
- Introductory lectures on convex optimization. A basic course.
- Iteration complexity analysis of multi-block ADMM for a family of convex minimization without strong convexity
- Linearly convergent away-step conditional gradient for non-strongly convex functions
- Mini-batch stochastic approximation methods for nonconvex stochastic composite optimization
- Multi-stage convex relaxation for feature selection
- Nearly unbiased variable selection under minimax concave penalty
- New analysis and results for the Frank-Wolfe method
- On gradients of functions definable in o-minimal structures
- On the complexity of steepest descent, Newton's and regularized Newton's methods for nonconvex unconstrained optimization problems
- On the information-adaptive variants of the ADMM: an iteration complexity perspective
- Proximal alternating linearized minimization for nonconvex and nonsmooth problems
- Proximal Alternating Minimization and Projection Methods for Nonconvex Problems: An Approach Based on the Kurdyka-Łojasiewicz Inequality
- Scalable robust matrix recovery: Frank-Wolfe meets proximal methods
- Solving a low-rank factorization model for matrix completion by a nonlinear successive over-relaxation algorithm
- Tensor and its Tucker core: the invariance relationships.
- The Łojasiewicz Inequality for Nonsmooth Subanalytic Functions with Applications to Subgradient Dynamical Systems
- Variable Selection via Nonconcave Penalized Likelihood and its Oracle Properties
- Variational Analysis
- Worst-case complexity of smoothing quadratic regularization methods for non-Lipschitzian optimization
Cited in
(56)- Generalized pattern search methods for a class of nonsmooth optimization problems with structure
- Nonlinear structure methods in optimization problems: A survey of the work of N. N. Redkovskij
- 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
- 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
- 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
- Primal-dual optimization algorithms over Riemannian manifolds: an iteration complexity analysis
- 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
- Convergence of linear Bregman ADMM for nonconvex and nonsmooth problems with nonseparable structure
- Alternating direction method of multipliers for nonconvex log total variation image restoration
- A two-level distributed algorithm for nonconvex constrained optimization
- A proximal alternating direction method of multiplier for linearly constrained nonconvex minimization
- A unified adaptive tensor approximation scheme to accelerate composite convex optimization
- Conditional Gradient Methods for Convex Optimization with General Affine and Nonlinear Constraints
- 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
- A global dual error bound and its application to the analysis of linearly constrained nonconvex optimization
- 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
- 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
- A linear approximate Bregman-type Peaceman-Rachford splitting method for nonconvex nonseparable optimization
- Decomposition methods for global solution of mixed-integer linear programs
- A proximal alternating direction method of multipliers for DC programming with structured constraints
- Dual descent augmented Lagrangian method and alternating direction method of multipliers
- Splitting augmented Lagrangian-type algorithms with partial quadratic approximation to solve sparse signal recovery problems
- A partial Bregman ADMM with a general relaxation factor for structured nonconvex and nonsmooth optimization
- A proximal augmented Lagrangian method for linearly constrained nonconvex composite optimization problems
- Sequential inertial linear ADMM algorithm for nonconvex and nonsmooth multiblock problems with nonseparable structure
- Stochastic linearized generalized alternating direction method of multipliers: expected convergence rates and large deviation properties
- An inexact majorized proximal alternating direction method of multipliers for diffusion tensors
- Two linear proximal Peaceman-Rachford splitting algorithms for nonconvex and nonsmooth nonseparable optimization
- Alternating direction method of multipliers for a class of nonconvex bilinear optimization: convergence analysis and applications
- Stochastic ADMM with batch size adaptation for nonconvex nonsmooth optimization
- Convergence rates for an inexact linearized ADMM for nonsmooth nonconvex optimization with nonlinear equality constraints
- Sparse kernel sufficient dimension reduction
- Research on the convergence rate of Bregman ADMM for nonconvex multiblock optimization
- Accelerated symmetric ADMM and its applications in large-scale signal processing
- Blind hyperspectral and multispectral images fusion: a unified tensor fusion framework from coupled inverse problem perspective
- Managing randomization in the multi-block alternating direction method of multipliers for quadratic optimization
This page was built for publication: Structured nonconvex and nonsmooth optimization: algorithms and iteration complexity analysis
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1734769)
