{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,25]],"date-time":"2026-04-25T14:04:28Z","timestamp":1777125868415,"version":"3.51.4"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2020,2,10]],"date-time":"2020-02-10T00:00:00Z","timestamp":1581292800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,2,10]],"date-time":"2020-02-10T00:00:00Z","timestamp":1581292800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11371103"],"award-info":[{"award-number":["11371103"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Optim Lett"],"published-print":{"date-parts":[[2020,11]]},"DOI":"10.1007\/s11590-020-01541-y","type":"journal-article","created":{"date-parts":[[2020,2,10]],"date-time":"2020-02-10T03:02:34Z","timestamp":1581303754000},"page":"2149-2160","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["The complexity results of the sparse optimization problems and reverse convex optimization problems"],"prefix":"10.1007","volume":"14","author":[{"given":"Zhongyi","family":"Jiang","sequence":"first","affiliation":[]},{"given":"Qiying","family":"Hu","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,2,10]]},"reference":[{"key":"1541_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.orhc.2014.10.001","volume":"4","author":"B Addis","year":"2015","unstructured":"Addis, B., Carello, G., Grosso, A., Lanzarone, E., Mattia, S.: Handling uncertainty in health care management using the cardinality-constrained approach: advantages and remarks. Oper. Res. Health Care 4, 1\u20134 (2015)","journal-title":"Oper. Res. Health Care"},{"key":"1541_CR2","volume-title":"Mathematical Programming in Statistics","author":"TS Arthanari","year":"1993","unstructured":"Arthanari, T.S., Dodge, Y.: Mathematical Programming in Statistics. Wiley, New York (1993)"},{"key":"1541_CR3","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1007\/BF00933745","volume":"15","author":"PP Bansal","year":"1975","unstructured":"Bansal, P.P., Jacobsen, S.E.: Characterization of local solutions for a class of nonconvex programs. J. Optim. Theory Appl. 15, 549\u2013564 (1975)","journal-title":"J. Optim. Theory Appl."},{"key":"1541_CR4","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1287\/opre.1030.0065","volume":"52","author":"D Bertsimas","year":"2004","unstructured":"Bertsimas, D., Sim, M.: The price of robustness. Oper. Res. 52, 35\u201353 (2004)","journal-title":"Oper. Res."},{"key":"1541_CR5","first-page":"121","volume":"74","author":"D Bienstock","year":"1996","unstructured":"Bienstock, D.: Computational study of a family of mixed-integer quadratic programming problems. Math. Program. 74, 121\u2013140 (1996)","journal-title":"Math. Program."},{"key":"1541_CR6","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1137\/060657704","volume":"51","author":"AM Bruckstein","year":"2009","unstructured":"Bruckstein, A.M., Donoho, D.L., Elad, M.: From sparse solutions of systems of equations to sparse modeling of signals and images. SIAM Rev. 51, 34\u201381 (2009)","journal-title":"SIAM Rev."},{"key":"1541_CR7","unstructured":"Bulatov, V.P.: Approximation methods for solving some mathematical programming problems. Applied Mathematics, Irkutsk. SEI SB AS SSSR, pp. 10\u201315 (1969) (in Russian)"},{"key":"1541_CR8","doi-asserted-by":"publisher","first-page":"489","DOI":"10.1109\/TIT.2005.862083","volume":"52","author":"E Cand\u00e8s","year":"2006","unstructured":"Cand\u00e8s, E., Romberg, J., Tao, T.: Robust uncertainty principles: exact signal reconstruction from highly impcomplete frequency information. IEEE Trans. Inf. Theory 52, 489\u2013509 (2006)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"1541_CR9","doi-asserted-by":"publisher","first-page":"1207","DOI":"10.1002\/cpa.20124","volume":"59","author":"E Cand\u00e8s","year":"2006","unstructured":"Cand\u00e8s, E., Romberg, J., Tao, T.: Stable signal recovery from incomplete and inaccurate measurements. Commun. Pure Appl. Math. 59, 1207\u20131223 (2006)","journal-title":"Commun. Pure Appl. Math."},{"key":"1541_CR10","doi-asserted-by":"publisher","first-page":"1271","DOI":"10.1016\/S0305-0548(99)00074-X","volume":"27","author":"TJ Chang","year":"2000","unstructured":"Chang, T.J., Meade, N., Beasley, J.E., Sharaiha, Y.M.: Heuristics for cardinality constrained portfolio optimisation. Comput. Oper. Res. 27, 1271\u20131302 (2000)","journal-title":"Comput. Oper. Res."},{"key":"1541_CR11","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1007\/s10107-012-0613-0","volume":"143","author":"X Chen","year":"2014","unstructured":"Chen, X., Ge, D., Wang, Z., Ye, Y.: Complexity of unconstrained $$L_2-L_p$$ minimization. Math. Program. 143, 371\u2013383 (2014)","journal-title":"Math. Program."},{"key":"1541_CR12","unstructured":"Chen, Y., Ge, D., Wang, M., Wang, Z., Ye, Y.: Strong NP-hardness for sparse optimization with concave penalty functions. In: Proceedings of the 34th International Conference on Machine Learning (2017)"},{"key":"1541_CR13","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1016\/S0377-2217(02)00858-5","volume":"154","author":"D Fortin","year":"2004","unstructured":"Fortin, D., Tsevendorj, I.: Global optimization and multi knapsack: a percolation algorithm. Eur. J. Oper. Res. 154, 46\u201356 (2004)","journal-title":"Eur. J. Oper. Res."},{"key":"1541_CR14","doi-asserted-by":"publisher","first-page":"745","DOI":"10.1287\/opre.2013.1170","volume":"61","author":"JJ Gao","year":"2013","unstructured":"Gao, J.J., Li, D.: Optimal cardinality constrained portfolio selection. Oper. Res. 61, 745\u2013761 (2013)","journal-title":"Oper. Res."},{"key":"1541_CR15","volume-title":"Computers and Intractability: A Guid to the Theorey of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guid to the Theorey of NP-Completeness. W.H. Freeman, San Francisco (1979)"},{"key":"1541_CR16","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1007\/s10107-011-0470-2","volume":"129","author":"D Ge","year":"2011","unstructured":"Ge, D., Jiang, X., Ye, Y.: A note on complexity of $$\\ell _p$$ minimization. Math. Program. 129, 285\u2013299 (2011)","journal-title":"Math. Program."},{"key":"1541_CR17","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1007\/BF00121661","volume":"9","author":"SE Jacobsen","year":"1996","unstructured":"Jacobsen, S.E., Moshirvaziri, K.: Computational experience using an edge search algorithm for linear reverse convex programs. J. Glob. Optim. 9, 153\u2013167 (1996)","journal-title":"J. Glob. Optim."},{"key":"1541_CR18","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1137\/070686676","volume":"31","author":"S Jokar","year":"2008","unstructured":"Jokar, S., Pfetsch, M.E.: Exact and approximate sparse solutions of underdetermined linear equations. SIAM J. Sci. Comput. 31, 23\u201344 (2008)","journal-title":"SIAM J. Sci. Comput."},{"key":"1541_CR19","doi-asserted-by":"publisher","first-page":"1290","DOI":"10.1287\/moor.2017.0905","volume":"43","author":"Z Lu","year":"2018","unstructured":"Lu, Z., Li, X.: Sparse recovery via partial regularization: models, theory and algorithms. Math. Oper. Res. 43, 1290\u20131316 (2018)","journal-title":"Math. Oper. Res."},{"key":"1541_CR20","doi-asserted-by":"publisher","DOI":"10.1201\/9781420035933","volume-title":"Subset Selection in Regression","author":"AJ Miller","year":"2002","unstructured":"Miller, A.J.: Subset Selection in Regression, 2nd edn. Chapman and Hall, Boca Raton (2002)","edition":"2"},{"key":"1541_CR21","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1023\/A:1013361800945","volume":"105","author":"K Moshirvaziri","year":"2001","unstructured":"Moshirvaziri, K., Amouzegar, M.A.: A cutting plane algorithm for linear reverse convex programs. Ann. Oper. Res. 105, 201\u2013212 (2001)","journal-title":"Ann. Oper. Res."},{"key":"1541_CR22","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1137\/S0097539792240406","volume":"24","author":"BK Natarajan","year":"1995","unstructured":"Natarajan, B.K.: Sparse approximate solutions to linear systerms. SIAM J. Comput. 24, 227\u2013234 (1995)","journal-title":"SIAM J. Comput."},{"key":"1541_CR23","doi-asserted-by":"publisher","DOI":"10.1515\/9781400841059","volume-title":"Nonlinear Optimization","author":"A Ruszczynsk","year":"2006","unstructured":"Ruszczynsk, A.: Nonlinear Optimization. Princeton University Press, Princeton (2006)"},{"key":"1541_CR24","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1007\/BF02283685","volume":"25","author":"SB Saad","year":"1990","unstructured":"Saad, S.B., Jacobsen, S.E.: A level set algorithm for a class of reverse convex programs. Ann. Oper. Res. 25, 19\u201342 (1990)","journal-title":"Ann. Oper. Res."},{"key":"1541_CR25","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1080\/10556780701722542","volume":"23","author":"DX Shaw","year":"2008","unstructured":"Shaw, D.X., Liu, S., Kopman, L.: Lagrangian relaxation procedure for cardinality constrained portfolio optimization. Optim. Methods Softw. 23, 411\u2013420 (2008)","journal-title":"Optim. Methods Softw."},{"key":"1541_CR26","doi-asserted-by":"publisher","first-page":"948","DOI":"10.1109\/JPROC.2010.2044010","volume":"98","author":"JA Tropp","year":"2010","unstructured":"Tropp, J.A., Wright, S.J.: Computational methods for sparse solution of linear inverse problems. Proc. IEEE 98, 948\u2013958 (2010)","journal-title":"Proc. IEEE"},{"key":"1541_CR27","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1007\/BF00938217","volume":"52","author":"H Tuy","year":"1987","unstructured":"Tuy, H.: Convex programs with an additional reverse convex constraint. J. Optim. Theory Appl. 52, 463\u2013486 (1987)","journal-title":"J. Optim. Theory Appl."},{"key":"1541_CR28","first-page":"283","volume":"22","author":"H Tuy","year":"2016","unstructured":"Tuy, H.: Convex analysis and global optimization. Nonconvex Optim. Appl. 22, 283\u2013283 (2016)","journal-title":"Nonconvex Optim. Appl."},{"key":"1541_CR29","doi-asserted-by":"publisher","first-page":"1154","DOI":"10.1016\/j.camwa.2007.04.046","volume":"55","author":"Y Wang","year":"2008","unstructured":"Wang, Y., Ying, L.: Global optimization for special reverse convex programming. Comput. Math. Appl. 55, 1154\u20131163 (2008)","journal-title":"Comput. Math. Appl."},{"key":"1541_CR30","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1016\/j.ejor.2011.03.030","volume":"213","author":"M Woodside","year":"2011","unstructured":"Woodside, M., Lucas, C., Beasley, J.E.: Heuristic algorithms for the cardinality constrained efficient frontier. Eur. J. Oper. Res. 213, 538\u2013550 (2011)","journal-title":"Eur. J. Oper. Res."},{"key":"1541_CR31","unstructured":"Zalesski, A.B.: Nonconvexity of feasible domains and optimization of economic decisions, ekonom i mat metody, pp. 1069\u20131080 (1980) (in Russian)"},{"key":"1541_CR32","doi-asserted-by":"publisher","first-page":"1065","DOI":"10.1137\/110847445","volume":"22","author":"YB Zhao","year":"2012","unstructured":"Zhao, Y.B., Li, D.: Reweighted $$\\ell _1$$-minimization for sparse solutions to underdetermined linear systems. SIAM J. Optim. 22, 1065\u20131088 (2012)","journal-title":"SIAM J. Optim."},{"key":"1541_CR33","doi-asserted-by":"publisher","first-page":"690","DOI":"10.1287\/ijoc.2014.0592","volume":"26","author":"XJ Zheng","year":"2014","unstructured":"Zheng, X.J., Sun, X.L., Li, D.: Improving the performance of MIQP solvers for quadratic programs with cardinality and minimum threshold constraints: a semidefinite program approach. Inf. J. Comput. 26, 690\u2013703 (2014)","journal-title":"Inf. J. Comput."}],"container-title":["Optimization Letters"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-020-01541-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11590-020-01541-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-020-01541-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,10]],"date-time":"2021-02-10T01:29:50Z","timestamp":1612920590000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11590-020-01541-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,2,10]]},"references-count":33,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2020,11]]}},"alternative-id":["1541"],"URL":"https:\/\/doi.org\/10.1007\/s11590-020-01541-y","relation":{},"ISSN":["1862-4472","1862-4480"],"issn-type":[{"value":"1862-4472","type":"print"},{"value":"1862-4480","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,2,10]]},"assertion":[{"value":"29 November 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 January 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 February 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}