×

Penalty methods for a class of non-Lipschitz optimization problems. (English) Zbl 1342.90181

Summary: We consider a class of constrained optimization problems with a possibly nonconvex non-Lipschitz objective and a convex feasible set being the intersection of a polyhedron and a possibly degenerate ellipsoid. Such problems have a wide range of applications in data science, where the objective is used for inducing sparsity in the solutions while the constraint set models the noise tolerance and incorporates other prior information for data fitting. To solve this class of constrained optimization problems, a common approach is the penalty method. However, there is little theory on exact penalization for problems with nonconvex and non-Lipschitz objective functions. In this paper, we study the existence of exact penalty parameters regarding local minimizers, stationary points, and \(\epsilon\)-minimizers under suitable assumptions. Moreover, we discuss a penalty method whose subproblems are solved via a nonmonotone proximal gradient method with a suitable update scheme for the penalty parameters and prove the convergence of the algorithm to a KKT point of the constrained problem. Preliminary numerical results demonstrate the efficiency of the penalty method for finding sparse solutions of underdetermined linear systems.

MSC:

90C30 Nonlinear programming
90C26 Nonconvex programming, global optimization

Software:

SPGL1
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] A. Beck and M. Teboulle, {\it A fast gradient-based algorithm for constrained total variation image denosing and deblurring problems,} IEEE Trans. Image Process., 18 (2009), pp. 2419-2434. · Zbl 1371.94049
[2] E. van den Berg and M. P. Friedlander, {\it Probing the Pareto frontier for basis pursuit solutions}, SIAM J. Sci. Comput., 31 (2008), pp. 890-912. · Zbl 1193.49033
[3] A. M. Bruckstein, D. L. Donoho, and M. Elad, {\it From sparse solutions of systems of equations to sparse modeling of signals and images}, SIAM Rev., 51 (2009), pp. 34-81. · Zbl 1178.68619
[4] R. H. Chan, M. Tao, and X. M. Yuan, {\it Constrained total variation deblurring models and fast algorithms based on alternating direction method of multipliers}, SIAM J. Imaging Sci., 6 (2013), pp. 680-697. · Zbl 1279.68322
[5] X. Chen, {\it Smoothing methods for nonsmooth, nonconvex minimization}, Math. Program. Ser. B, 134 (2012), pp. 71-99. · Zbl 1266.90145
[6] X. Chen, D. Ge, Z. Wang, and Y. Ye, {\it Complexity of unconstrained \(L_2-L_p\) minimization}, Math. Program., 143 (2014), pp. 371-383. · Zbl 1285.90039
[7] X. Chen, F. Xu, and Y. Ye., {\it Lower bound theory of nonzero entries in solutions of} \(l_2-l_p\) {\it minimization}., SIAM J. Sci. Comput., 32 (2010), pp. 2832-2852. · Zbl 1242.90174
[8] F. Fachinei and J.-S. Pang, {\it Finite-Dimensional Variational Inequalities and Complementarity Problems}, Springer, New York, 2003.
[9] J. Fan, {\it Comments on “Wavelets in Statistic: A review” by A. Antoniadis}, Stat. Methods Appl., 6 (1997), pp. 131-138. · Zbl 1454.62116
[10] J. Fan and R. Li, {\it Variable selection via nonconcave penalized likelihood and its oracle properties}, J. Amer. Statist. Assoc., 96 (2001), pp. 1348-1360. · Zbl 1073.62547
[11] M. P. Friedlander and P. Tseng, {\it Exact regularization of convex programs}, SIAM J. Optim., 18 (2007), pp. 1326-1350. · Zbl 1176.90457
[12] D. Ge, X. Jiang, and Y. Ye, {\it A note on the complexity of \(L_p\) minimization}, Math. Program., 21 (2011), pp. 1721-1739.
[13] D. Geman and G. Reynolds, {\it Constrained restoration and the recovery of discontinuities}, IEEE Trans. Pattern Anal. Mach. Intell., 14 (1992), pp. 357-383.
[14] P. Gong, C. Zhang, Z. Lu, J. Huang, and J. Ye, {\it A general iterative shrinkage and thresholding algorithm for non-convex regularized optimization problems}, in proceedings of the 30th International Conference on Machine Learning, 2013.
[15] J.-B. Hiriart-Urruty and C. Lemaréchal, {\it Fundamentals of Convex Analysis}, Springer, New York, 2001. · Zbl 0998.49001
[16] J. Huang, J. L. Horowitz, and S. Ma, {\it Asymptotic properties of bridge estimators in sparse high-dimensional regression models}, Ann. Statist., 36 (2008), pp. 587-613. · Zbl 1133.62048
[17] K. Knight and W. J. Fu, {\it Asymptotics for lasso-type estimators}, Ann. Statist., 28 (2000), pp. 1356-1378. · Zbl 1105.62357
[18] H. A. Le Thi, T. P. Dinh, and H. V. Ngai, {\it Exact penalty and error bounds in DC programming}, J. Global Optim., 52 (2012), pp. 509-535. · Zbl 1242.49037
[19] C. Li, K. F. Ng, and T. K. Pong, {\it The SECQ, linear regularity, and the strong CHIP for an infinite system of closed convex sets in normed linear spaces}, SIAM J. Optim., 18 (2007), pp. 643-665. · Zbl 1151.90054
[20] G. Li, A. K. C. Ma, and T. K. Pong, {\it Robust least square semidefinite programming with applications}, Comput. Optim. Appl., 58 (2014), pp. 347-379. · Zbl 1330.90061
[21] Z. Lu, {\it Iterative reweighted minimization methods for \(l_p\) regularized unconstrained nonlinear programming}, Math. Program., 147 (2014), pp. 277-307. · Zbl 1308.90170
[22] X.-D. Luo and Z.-Q. Luo, {\it Extension of Hoffman’s error bound to polynomial systems}, SIAM J. Optim., 4 (1994), pp. 383-392. · Zbl 0821.90113
[23] M. Nikolova, M. K. Ng, S. Zhang, and W. Ching, {\it Efficient reconstruction of piecewise constant images using nonsmooth nonconvex minimization}, SIAM J. Imaging Sci., 1 (2008), pp. 2-25. · Zbl 1207.94017
[24] M. Ng, P. Weiss, and X. Yuan, {\it Solving constrained total-variation image restoration and reconstruction problems via alternating direction methods}, SIAM J. Sci. Comput., 32 (2010), pp. 2710-2736. · Zbl 1217.65071
[25] J. Nocedal and S. J. Wright, {\it Numerical Optimization}, 2nd ed., Springer, New York, 2006. · Zbl 1104.65059
[26] M. Ç. Pinar and S. A. Zenios, {\it On smoothing exact penalty functions for convex constrained optimization}, SIAM J. Optim., 4 (1994), pp. 486-511. · Zbl 0819.90072
[27] R. T. Rockafellar and R. J.-B. Wets, {\it Variational Analysis}, Springer, New York, 1998. · Zbl 0888.49001
[28] S. J. Wright, R. Nowak, and M. A. T. Figueiredo, {\it Sparse reconstruction by separable approximation}, IEEE Trans. Signal Process., 57 (2009), pp. 2479-2493. · Zbl 1391.94442
[29] P. Yin, Y. Lou, Q. He, and J. Xin, {\it Minimization of \(ℓ_{1-2}\) for compressed sensing}, SIAM J. Sci. Comput., 37 (2015), pp. A536-A563. · Zbl 1316.90037
[30] C.-H. Zhang, {\it Nearly unbiased variable selection under minimax concave penalty}, Ann. Statist., 38 (2010), pp. 894-942. · Zbl 1183.62120
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.