×

zbMATH — the first resource for mathematics

Mathematical programs with cardinality constraints: reformulation by complementarity-type conditions and a regularization method. (English) Zbl 1332.90220

MSC:
90C27 Combinatorial optimization
90C30 Nonlinear programming
90C46 Optimality conditions and duality in mathematical programming
65K05 Numerical mathematical programming methods
Software:
SNOPT; Gurobi
PDF BibTeX Cite
Full Text: DOI
References:
[1] R. Andreani, J. M. Martínez, and M. L. Schuverdt, The CPLD condition of Qi and Wei implies the quasinormality qualification, J. Optim. Theory Appl., 125 (2005), pp. 473–485. · Zbl 1125.90058
[2] M. S. Bazaraa and C. M. Shetty, Foundations of Optimization, Lecture Notes in Econ. Math. Syst., Springer, New York, 1976. · Zbl 0334.90049
[3] A. Beck and Y. C. Eldar, Sparsity constrained nonlinear optimization: Optimality conditions and algorithms, SIAM J. Optim., 23 (2013), pp. 1480–1509. · Zbl 1295.90051
[4] D. P. Bertsekas and A. E. Ozdaglar, Pseudonormality and a Lagrange multiplier theory for constrained optimization, J. Optim. Theory Appl., 114 (2002), pp. 287–343. · Zbl 1026.90092
[5] D. Bertsimas and R. Shioda, Algorithm for cardinality-constrained quadratic optimization, Comput. Optim. Appl., 43 (2009), pp. 1–22. · Zbl 1178.90262
[6] D. Bienstock, Computational study of a family of mixed-integer quadratic programming problems, Math. Programming, 74 (1996), pp. 121–140. · Zbl 0855.90090
[7] O. Burdakov, C. Kanzow, and A. Schwartz, On a reformulation of mathematical programs with cardinality constraints, in Advances in Global Optimization, D. Y. Gao, N. Ruan, and W. X. Xing, eds., Proceedings of the 3rd World Congress of Global Optimization (Huangshan, China, 2013), Springer, New York, 2015, pp. 3–14. · Zbl 1327.90228
[8] O. Burdakov, C. Kanzow, and A. Schwartz, Mathematical Programs with Cardinality Constraints: Reformulation by Complementarity-type Conditions and a Regularization Method, Preprint 324, Institute of Mathematics, University of Würzburg, Würzburg, Germany, 2014. · Zbl 1332.90220
[9] E. J. Candès and M. B. Wakin, An introduction to compressive sampling, IEEE Trans. Signal Process., 25 (2008), pp. 21–30.
[10] D. Di Lorenzo, G. Liuzzi, F. Rinaldi, F. Schoen, and M. Sciandrone, A concave optimization-based approach for sparse portfolio selection, Optim. Methods Softw., 27 (2012), pp. 983–1000. · Zbl 1250.90070
[11] F. Facchinei and J.-S. Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems, Volumes I and II, Springer Ser. Oper. Res., Springer, New York, 2003. · Zbl 1062.90002
[12] M. Feng, J. E. Mitchell, J.-S. Pang, X. Shen, and A. Wächter, Complementarity Formulation of \( ℓ_0 \)-norm Optimization Problems, Technical Report, Industrial Engineering and Management Sciences, Northwestern University, Evanston, IL, 2013.
[13] A. Frangioni and C. Gentile, SDP diagonalizations and perspective cuts for a class of nonseparable MIQP, Oper. Res. Lett., 35 (2007), pp. 181–185. · Zbl 1149.90379
[14] A. Frangioni and C. Gentile, Mean-variance problem with minimum buy-in constraints, data and documentation, online at http://www.di.unipi.it/optimize/Data/MV.html.
[15] P. E. Gill, W. Murray, and M. A. Saunders, SNOPT: An SQP algorithm for large-scale constrained optimization, SIAM J. Optim., 12 (2002), pp. 979–1006. · Zbl 1027.90111
[16] Gurobi Optimization, Gurobi Optimizer Reference Manual, \burlhttp://www.gurobi.com, 2014.
[17] R. Janin, Directional derivative of the marginal function in nonlinear programming, Math. Program. Stud., 21 (1984), pp. 110–126. · Zbl 0549.90082
[18] C. Kanzow and A. Schwartz, A new regularization method for mathematical programs with complementarity constraints with strong convergence properties, SIAM J. Optim., 23 (2013), pp. 770–798. · Zbl 1282.65069
[19] Z.-Q. Luo, J.-S. Pang, and D. Ralph, Mathematical Programs with Equilibrium Constraints, Cambridge University Press, Cambridge/New York/Melbourne, 1996.
[20] A. Miller, Subset Selection in Regression, 2nd ed., Chapman & Hall/CRC Press, Boca Raton, FL, 2002. · Zbl 1051.62060
[21] W. Murray and H. Shek, A local relaxation method for the cardinality constrained portfolio optimization problem, Comput. Optim. Appl., 53 (2012), pp. 681–709. · Zbl 1264.90133
[22] J. Nocedal and S. J. Wright, Numerical Optimization, Springer Ser. Oper. Res., Springer, New York, 1999. · Zbl 0930.65067
[23] J. V. Outrata, M. Kočvara, and J. Zowe, Nonsmooth Approach to Optimization Problems with Equilibrium Constraints, Kluwer Academic Publishers, Dordrecht, The Netherlands, 1998.
[24] L. Qi and Z. Wei, On the constant positive linear dependence condition and its application to SQP methods, SIAM J. Optim., 10 (2000), pp. 963–981. · Zbl 0999.90037
[25] R. T. Rockafellar and R. J.-B. Wets: Variational Analysis, Grundlehren Math. Wiss. 317, Springer, New York, 1998.
[26] R. Ruiz-Torrubiano, S. García-Moratilla, and A. Suárez, Optimization problems with cardinality constraints, in Computational Intelligence in Optimization, Y. Tenne and C.-K. Goh, eds., Springer, New York, 2010, pp. 105–130.
[27] H. Scheel and S. Scholtes, Mathematical programs with complementarity constraints: Stationarity, optimality, and sensitivity, Math. Oper. Res., 25 (2000), pp. 1–22. · Zbl 1073.90557
[28] S. Scholtes, Convergence properties of a regularization scheme for mathematical programs with complementarity constraints, SIAM J. Optim., 11 (2001), pp. 918–936. · Zbl 1010.90086
[29] S. Steffensen and M. Ulbrich, A new relaxation scheme for mathematical programs with equilibrium constraints, SIAM J. Optim., 20 (2010), pp. 2504–2539. · Zbl 1231.90350
[30] D. Sun and L. Qi, On NCP-functions, Comput. Optim. Appl., 13 (1999), pp. 201–220. · Zbl 1040.90544
[31] X. Sun, X. Zheng, and D. Li, Recent advances in mathematical programming with semi-continuous variables and cardinality constraint, J. Oper. Res. Soc. China, 1 (2013), pp. 55–77. · Zbl 1277.90001
[32] X. Zheng, X. Sun, D. Li, and J. Sun, Successive convex approximations to cardinality-constrained convex programs: A piecewise-linear DC approach, Comput. Optim. Appl., to appear. DOI: 10.1007/s10589-013-9582-3. · Zbl 1302.90157
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.