Optimality and Complexity for Constrained Optimization Problems with Nonconvex Regularization

Wei Bian () and Xiaojun Chen ()
Additional contact information
Wei Bian: Department of Mathematics, Harbin Institute of Technology, Harbin, China 150001
Xiaojun Chen: Department of Applied Mathematics, The Hong Kong Polytechnic University, Hong Kong, China

Mathematics of Operations Research, 2017, vol. 42, issue 4, 1063-1084

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 a 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 tangent cone, we derive a first order necessary optimality condition for local minimizers of the problem, and define the generalized stationary point of it. We show that the generalized stationary point is the Clarke stationary point when the objective function is Lipschitz continuous at this point, and satisfies the existing necessary optimality conditions when the objective function is not Lipschitz continuous at this point. Moreover, we prove the consistency between the generalized directional derivative and the limit of the classic directional derivatives associated with the smoothing function. Finally, we establish a lower bound property for every local minimizer and show that finding a global minimizer is strongly NP-hard when the objective function has a concave regularizer.

Keywords: constrained nonsmooth nonconvex optimization; optimality condition; generalized directional derivative; directional derivative consistency; numerical property (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
https://doi.org/10.1287/moor.2016.0837 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:42:y:2017:i:4:p:1063-1084

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().