Optimality and Complexity for Constrained Optimization Problems with Nonconvex Regularization

References

• Audet C, Dennis JE Jr (2006) Mesh adaptive direct search algorithms for constrained optimization. SIAM J. Optim. 17(1):188–217.Crossref, Google Scholar
• Auslender A (1997) How to deal with the unbounded in optimization: Theory and algorithms. Math. Program. 79(1):3–18.Crossref, Google Scholar
• Beck A, Teboulle M (2012) Smoothing and first order methods: A unified framework. SIAM J. Optim. 22(2):557–580.Crossref, Google Scholar
• Bertsekas DP (1976) On the Goldstein-Levitin-Polyak gradient projection method. IEEE Trans. Autom. Control 21(2):174–184.Crossref, Google Scholar
• Bian W, Chen X (2013) Worst-case complexity of smoothing quadratic regularization methods for non-Lipschitzian optimization. SIAM J. Optim. 23(3):1718–1741.Crossref, Google Scholar
• Bian W, Chen X (2014) Optimality conditions and complexity for non-Lipschitz constrained optimization problems. Preprint, The Hong Kong Polytechnic University, Hong Kong.Google Scholar
• Bian W, Chen X (2015) Linearly constrained non-Lipschitz optimization for image restoration. SIAM J. Imaging Sci. 8(4):2294–2322.Crossref, Google Scholar
• Bian W, Chen X, Ye Y (2015) Complexity analysis of interior point algorithms for non-Lipschitz and nonconvex minimization. Math. Program. 149(1):301–327.Crossref, Google Scholar
• Borwein JM, Lewis AS (2000) Convex Analysis and Nonlinear Optimization. Theory and Examples (Springer, New York).Crossref, Google Scholar
• Brodie J, Daubechies I, De Mol C, Giannone D, Loris I (2009) Sparse and Stable Markowitz portfolios. Proc. Nat. Acad. Sci. 106(30):12267–12272.Crossref, Google Scholar
• Bruckstein AM, Donoho DL, Elad M (2009) From sparse solutions of systems of equations to sparse modeling of signals and images. SIAM Rev. 51(1):34–81.Crossref, Google Scholar
• Burke JV, Hoheisel T (2013) Epi-convergent smoothing with applications to convex composite functions. SIAM J. Optim. 23(3):1457–1479.Crossref, Google Scholar
• Burke JV, Hoheisel T, Kanzow C (2013) Gradient consistency for integral-convolution smoothing. Set-Valued Variational Anal. 21(2):359–376.Crossref, Google Scholar
• Burke JV, Lewis AS, Overton ML (2002) Approximating subdifferentials by random samplying of gradients. Math. Oper. Res. 27(3):567–584.Link, Google Scholar
• Chan RH, Liang HX (2014) Half-quadratic algorithm for lp-lq problems with applications to TV-l1 image restoration and compressive sensing. Bruhn A, Pock T, Tai X-C, eds. Efficient Algorithms for Global Optimization Methods in Computer Vision. Lecture Notes Computer Science, vol. 8293 (Springer, Berlin), 78–103.Crossref, Google Scholar
• Chartrand R, Staneva V (2008) Restricted isometry properties and nonconvex compressive sensing. Inverse Probl. 24(3):1–14.Crossref, Google Scholar
• Chen C, Li X, Tolman C, Wang S, Ye Y (2014) Sparse portfolio selection via quasi-norm regularization. Preprint arXiv: 1312.6350.Google Scholar
• Chen X (2012) Smoothing methods for nonsmooth, nonconvex minimization. Math. Program. 134(1):71–99.Crossref, Google Scholar
• Chen X, Ng M, Zhang C (2012) Nonconvex lp regularization and box constrained model for image restoration. IEEE Trans. Image Processing 21(12):4709–4721.Crossref, Google Scholar
• Chen X, Niu L, Yuan Y (2013) Optimality conditions and smoothing trust region Newton method for non-Lipschitz optimization. SIAM J. Optim. 23(3):1528–1552.Crossref, Google Scholar
• Chen X, Xu F, Ye Y (2010) Lower bound theory of nonzero entries in solutions of l2-lp minimization. SIAM J. Sci. Comput. 32(5):2832–2852.Crossref, Google Scholar
• Chen X, Ge D, Wang Z, Ye Y (2014) Complexity of unconstrained L2-Lp minimization. Math. Program. 143(1–2):371–383.Crossref, Google Scholar
• Clarke FH (1983) Optimization and Nonsmooth Analysis (John Wiley & Sons, New York).Google Scholar
• Curtis FE, Overton ML (2012) A sequential quadratic programming algorithm for nonconvex, nonsmooth constrained optimization. SIAM J. Optim. 22(2):474–500.Crossref, Google Scholar
• Fan J (1997) Comments on “Wavelets in statistics: A review” by A. Antoniadis. Stat. Methods Appl. 6:131–138.Google Scholar
• Fan J, Li R (2001) Variable selection via nonconcave penalized likelihood and its oracle properties. J. Amer. Statist. Assoc. 96(456):1348–1360.Crossref, Google Scholar
• Fan J, Peng H (2004) Nonconcave penalized likelihood with a diverging number of parameters. Ann. Stat. 32(3):928–961.Crossref, Google Scholar
• Garey MR, Johnson DS (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness (W. H. Freeman & Co., New York).Google Scholar
• Ge D, Jiang X, Ye Y (2011) A note on the complexity of Lp minimization. Math. Program. 129(2):285–299.Crossref, Google Scholar
• Ge D, Wang Z, Ye Y, Yin H (2015) Strong NP-hardness result for regularized Lq-minimization problems with concave penalty functions. Preprint arXiv:1501.00622.Google Scholar
• Hiriart-Urruty J-B, Strodiot J-J, Nguyen VH (1984) Generalized Hessian matrix and second-order optimality conditions for problems with C1, 1 data. Appl. Math. Optim. 11(1):43–56.Crossref, Google Scholar
• Huang J, Horowitz JL, Ma S (2008) Asymptotic properties of bridge estimators in sparse high-dimensional regression models. Ann. Statist. 36(1):587–613.Crossref, Google Scholar
• Huang J, Ma S, Xue H, Zhang C (2009) A group bridge approach for variable selection. Biometrika 96(2):339–355.Crossref, Google Scholar
• Huber P (1981) Robust Estimation (John Wiley & Sons, New York).Google Scholar
• Jahn J (1996) Introduction to the Theory of Nonlinear Optimization (Springer, Berlin).Crossref, Google Scholar
• Knight K, Fu WJ (2000) Asymptotics for lasso-type estimators. Ann. Stat. 28(5):1356–1378.Crossref, Google Scholar
• Levitin ES, Polyak BT (1966) Constrained minimization problems. USSR Comput. Math. Math. Phys. 6(5):1–50.Crossref, Google Scholar
• Liu YF, Dai YH, Ma S (2013) Joint power and admission control via linear programming deflation. IEEE Trans. Signal Processing 61(6):1327–1338.Crossref, Google Scholar
• Liu YF, Ma S, Dai YH, Zhang SZ (2016) A smoothing SQP framework for a class of composite Lq minimization over polyhedron. Math. Program. 158(1):467–500.Crossref, Google Scholar
• Loh P, Wainwright MJ (2015) Regularized M-estimators with nonconvexity: Statistical and algorithmic theory for local optima. J. Mach. Learn. Res. 16:559–616.Google Scholar
• Lu Z (2014) Iterative reweighted minimization methods for lp regularized unconstrained nonlinear programming. Math. Program. 147(1–2):277–307.Crossref, Google Scholar
• Natarajan BK (1995) Sparse approximate solutions to linear systems. SIAM J. Comput. 24(2):227–234.Crossref, Google Scholar
• Nikolova M, Ng MK, Zhang S, Ching WK (2008) Efficient reconstruction of piecewise constant images using nonsmooth nonconvex minimization. SIAM J. Imaging Sci. 1(1):2–25.Crossref, Google Scholar
• Nocedal J, Wright SJ (2006) Numerical Optimization (Springer, New York).Google Scholar
• Rockafellar RT (1970) Convex Analysis (Princeton University Press, Princeton, NJ).Crossref, Google Scholar
• Rockafellar RT, Wets RJ-B (1998) Variational Analysis (Springer, Berlin).Crossref, Google Scholar
• Spingarn JE, Rockafellar RT (1979) The genaric nature of optimality conditions in nonlinear programming. Math. Oper. Res. 4(4):425–430.Link, Google Scholar
• Sun WY, Yuan Y (2006) Optimization Theory and Methods: Nonlinear Programming (Springer, New York).Google Scholar
• Tibshirani R (1996) Shrinkage and selection via the Lasso. J. Roy. Statist. Soc. Ser. B 58:267–288.Google Scholar
• Vazirani V (2003) Approximation Algorithms (Springer, Berlin).Crossref, Google Scholar
• Wang Z, Liu H, Zhang T (2014) Optimal computational and statistical rates of convergence for sparse nonconvex learning problems. Ann. Stat. 42(6):2164–2201.Crossref, Google Scholar
• Ye Y (1997) Interior Point Algorithms: Theory and Analysis (John Wiley & Sons, New York).Crossref, Google Scholar
• Zhang CH (2010) Nearly unbiased variable selection under minimax concave penalty. Ann. Statist. 38(2):894–942.Crossref, Google Scholar