Structured nonconvex and nonsmooth optimization

algorithms and iteration complexity analysis

Bo Jiang, Tianyi Lin, Shiqian Ma, Shuzhong Zhang

Research output: Contribution to journalArticle

4 Citations (Scopus)

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 absence of 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 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 ϵ-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 / ϵ2) 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 and tensor sparse PCA problems.

Original languageEnglish (US)
Pages (from-to)115-157
Number of pages43
JournalComputational Optimization and Applications
Volume72
Issue number1
DOIs
StatePublished - Jan 15 2019

Fingerprint

Nonsmooth Optimization
Nonconvex Optimization
Complexity Analysis
Optimization Algorithm
Stationary Solutions
Iteration
Tensors
Tensor
Gradient
Proximal Methods
Gradient methods
Constrained optimization
Gradient Method
Stationarity
Constrained Optimization
Optimization Model
Variational Inequalities
Immediately
Convergence Rate
Scalability

Keywords

  • Alternating direction method of multipliers
  • Block coordinate descent method
  • Conditional gradient method
  • Iteration complexity
  • Structured nonconvex optimization
  • ϵ-Stationary

Cite this

Structured nonconvex and nonsmooth optimization : algorithms and iteration complexity analysis. / Jiang, Bo; Lin, Tianyi; Ma, Shiqian; Zhang, Shuzhong.

In: Computational Optimization and Applications, Vol. 72, No. 1, 15.01.2019, p. 115-157.

Research output: Contribution to journalArticle

@article{b73bca641f1045a6b0255b28d41491df,
title = "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 absence of 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 dependent on the H{\"o}lderian 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 O(1 / ϵ2) 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 and tensor sparse PCA problems.",
keywords = "Alternating direction method of multipliers, Block coordinate descent method, Conditional gradient method, Iteration complexity, Structured nonconvex optimization, ϵ-Stationary",
author = "Bo Jiang and Tianyi Lin and Shiqian Ma and Shuzhong Zhang",
year = "2019",
month = "1",
day = "15",
doi = "10.1007/s10589-018-0034-y",
language = "English (US)",
volume = "72",
pages = "115--157",
journal = "Computational Optimization and Applications",
issn = "0926-6003",
publisher = "Springer Netherlands",
number = "1",

}

TY - JOUR

T1 - Structured nonconvex and nonsmooth optimization

T2 - algorithms and iteration complexity analysis

AU - Jiang, Bo

AU - Lin, Tianyi

AU - Ma, Shiqian

AU - Zhang, Shuzhong

PY - 2019/1/15

Y1 - 2019/1/15

N2 - 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 absence of 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 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 ϵ-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 / ϵ2) 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 and tensor sparse PCA problems.

AB - 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 absence of 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 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 ϵ-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 / ϵ2) 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 and tensor sparse PCA problems.

KW - Alternating direction method of multipliers

KW - Block coordinate descent method

KW - Conditional gradient method

KW - Iteration complexity

KW - Structured nonconvex optimization

KW - ϵ-Stationary

UR - http://www.scopus.com/inward/record.url?scp=85053930479&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85053930479&partnerID=8YFLogxK

U2 - 10.1007/s10589-018-0034-y

DO - 10.1007/s10589-018-0034-y

M3 - Article

VL - 72

SP - 115

EP - 157

JO - Computational Optimization and Applications

JF - Computational Optimization and Applications

SN - 0926-6003

IS - 1

ER -