Mathematical programs with cardinality constraints: reformulation by complementarity-type conditions and a regularization method. (English) Zbl 1332.90220
Summary: Optimization problems with cardinality constraints are very difficult mathematical programs which are typically solved by global techniques from discrete optimization. Here we introduce a mixed-integer formulation whose standard relaxation still has the same solutions (in the sense of global minima) as the underlying cardinality-constrained problem; the relation between the local minima is also discussed in detail. Since our reformulation is a minimization problem in continuous variables, it allows us to apply ideas from that field to cardinality-constrained problems. Here, in particular, we therefore also derive suitable stationarity conditions and suggest an appropriate regularization method for the solution of optimization problems with cardinality constraints. This regularization method is shown to be globally convergent to a Mordukhovich-stationary point. Extensive numerical results are given to illustrate the behavior of this method.
MSC:
| 90C27 | Combinatorial optimization |
| 90C30 | Nonlinear programming |
| 90C46 | Optimality conditions and duality in mathematical programming |
| 65K05 | Numerical mathematical programming methods |
Keywords:
cardinality constraints; global minima; local minima; stationary points; M-stationarity; relaxation; regularization methodReferences:
| [1] | R. Andreani, J. M. Martínez, and M. L. Schuverdt, {\it 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, {\it Foundations of Optimization}, Lecture Notes in Econ. Math. Syst., Springer, New York, 1976. · Zbl 0334.90049 |
| [3] | A. Beck and Y. C. Eldar, {\it 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, {\it 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, {\it Algorithm for cardinality-constrained quadratic optimization}, Comput. Optim. Appl., 43 (2009), pp. 1-22. · Zbl 1178.90262 |
| [6] | D. Bienstock, {\it 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, {\it 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, {\it 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, {\it 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, {\it 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, {\it 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, {\it 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, {\it 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, {\it 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, {\it SNOPT: An SQP algorithm for large-scale constrained optimization}, SIAM J. Optim., 12 (2002), pp. 979-1006. · Zbl 1027.90111 |
| [16] | Gurobi Optimization, {\it Gurobi Optimizer Reference Manual}, \burlhttp://www.gurobi.com, 2014. |
| [17] | R. Janin, {\it 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, {\it 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, {\it Mathematical Programs with Equilibrium Constraints}, Cambridge University Press, Cambridge/New York/Melbourne, 1996. |
| [20] | A. Miller, {\it Subset Selection in Regression}, 2nd ed., Chapman & Hall/CRC Press, Boca Raton, FL, 2002. · Zbl 1051.62060 |
| [21] | W. Murray and H. Shek, {\it 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, {\it Numerical Optimization}, Springer Ser. Oper. Res., Springer, New York, 1999. · Zbl 0930.65067 |
| [23] | J. V. Outrata, M. Kočvara, and J. Zowe, {\it Nonsmooth Approach to Optimization Problems with Equilibrium Constraints}, Kluwer Academic Publishers, Dordrecht, The Netherlands, 1998. · Zbl 0947.90093 |
| [24] | L. Qi and Z. Wei, {\it 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: {\it Variational Analysis}, Grundlehren Math. Wiss. 317, Springer, New York, 1998. · Zbl 0888.49001 |
| [26] | R. Ruiz-Torrubiano, S. García-Moratilla, and A. Suárez, {\it Optimization problems with cardinality constraints}, in Computational Intelligence in Optimization, Y. Tenne and C.-K. Goh, eds., Springer, New York, 2010, pp. 105-130. · Zbl 1200.90127 |
| [27] | H. Scheel and S. Scholtes, {\it Mathematical programs with complementarity constraints: Stationarity, optimality, and sensitivity}, Math. Oper. Res., 25 (2000), pp. 1-22. · Zbl 1073.90557 |
| [28] | S. Scholtes, {\it 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, {\it 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, {\it On NCP-functions}, Comput. Optim. Appl., 13 (1999), pp. 201-220. · Zbl 1040.90544 |
| [31] | X. Sun, X. Zheng, and D. Li, {\it 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, {\it 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. 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.
