Structured Nonconvex and Nonsmooth Optimization: Algorithms and Iteration Complexity Analysis

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 $\epsilon$-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ölderian continuity of the gradient of the smooth part of the objective. For the model with coupled affine constraints, we introduce corresponding $\epsilon$-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 $O(1/{\epsilon }^2)$ to reach an $\epsilon$-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.

Section 4.1 is updated

References in corpus (4)

• Nearly unbiased variable selection under minimax concave penalty
• Convergence Rate of Frank-Wolfe for Non-Convex Objectives
• A Distributed, Asynchronous and Incremental Algorithm for Nonconvex Optimization: An ADMM Based Approach
• Decomposing Linearly Constrained Nonconvex Problems by a Proximal Primal Dual Approach: Algorithms, Convergence, and Applications

Cited by in corpus (10)

• Successive Convex Approximation Algorithms for Sparse Signal Estimation with Nonconvex Regularizations
• Gradient Primal-Dual Algorithm Converges to Second-Order Stationary Solutions for Nonconvex Distributed Optimization
• Linearized ADMM for Non-convex Non-smooth Optimization with Convergence Analysis
• Primal-Dual Optimization Algorithms over Riemannian Manifolds: an Iteration Complexity Analysis
• Stochastic Alternating Direction Method of Multipliers with Variance Reduction for Nonconvex Optimization
• A Proximal Alternating Direction Method of Multiplier for Linearly Constrained Nonconvex Minimization
• Stochastic In-Face Frank-Wolfe Methods for Non-Convex Optimization and Sparse Neural Network Training
• An Efficient ADMM-Based Algorithm to Nonconvex Penalized Support Vector Machines
• A Parallel Best-Response Algorithm with Exact Line Search for Nonconvex Sparsity-Regularized Rank Minimization
• Managing Randomization in the Multi-Block Alternating Direction Method of Multipliers for Quadratic Optimization