Optimization Online


Optimality and complexity for constrained optimization problems with nonconvex regularization

Wei Bian(bianweilvse520***at***163.com)
Xiaojun Chen(maxjchen***at***polyu.edu.hk)

Abstract: In this paper, we consider a class of constrained optimization problems where the feasible set is a general closed convex set and the objective function has a nonsmooth, nonconvex regularizer. Such regularizer includes widely used SCAD, MCP, logistic, fraction, hard thresholding and non-Lipschitz $L_p$ penalties as special cases. Using the theory of the generalized directional derivative and the Clarke tangent cone, we derive a first order necessary optimality condition for local minimizers of the problem, and define the generalized stationary point of it. The generalized stationary point is the Clarke stationary point when the objective function is Lipschitz continuous at this point, and the scaled stationary point when the objective function is not Lipschitz continuous at this point. We prove the consistency between the generalized directional derivative and the limit of the classic directional derivatives associated with the smoothing function. Moreover we show that finding a global minimizer of such optimization problems is strongly NP-hard and establish positive lower bounds for the absolute value of nonzero entries in every local minimizer of the problem if the regularizer is concave in an open set.

Keywords: Constrained nonsmooth nonconvex optimization; directional derivative consistency; optimality condition; lower bound theory; complexity

Category 1: Nonlinear Optimization (Constrained Nonlinear Optimization )

Category 2: Convex and Nonsmooth Optimization (Nonsmooth Optimization )


Download: [PDF]

Entry Submitted: 02/26/2015
Entry Accepted: 02/26/2015
Entry Last Modified: 02/26/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society