Abstract
In this paper, we study a class of optimization problems, called Mathematical Programs with Cardinality Constraints (MPCaC). This kind of problem is generally difficult to deal with, because it involves a constraint that is not continuous neither convex, but provides sparse solutions. Thereby we reformulate MPCaC in a suitable way, by modeling it as mixed-integer problem and then addressing its continuous counterpart, which will be referred to as relaxed problem. We investigate the relaxed problem by analyzing the classical constraints in two cases: linear and nonlinear. In the linear case, we propose a general approach and present a discussion of the Guignard and Abadie constraint qualifications, proving in this case that every minimizer of the relaxed problem satisfies the Karush–Kuhn–Tucker (KKT) conditions. On the other hand, in the nonlinear case, we show that some standard constraint qualifications may be violated. Therefore, we cannot assert about KKT points. Motivated to find a minimizer for the MPCaC problem, we define new and weaker stationarity conditions, by proposing a unified approach.
Similar content being viewed by others
References
Andreani, R., Haeser, G., Secchin, L.D., Silva, P.J.S.: New sequential optimality conditions for mathematical problems with complementarity constraints and algorithmic consequences. SIAM J. Optim. 29(4), 3201–3230 (2019). https://doi.org/10.1137/18M121040X
Beck, A.: First-Order Methods in Optimization. SIAM, Philadelphia (2017)
Beck, A., Eldar, Y.C.: Sparsity constrained nonlinear optimization: optimality conditions and algorithms. SIAM J. Optim. 23(3), 1480–1509 (2013)
Bienstock, D.: Computational study of a family of mixed-integer quadratic programming problems. Math. Program. 74(2), 121–140 (1996)
Branda, M., Bucher, M., Červinka, M., Schwartz, A.: Convergence of a Scholtes-type regularization method for cardinality-constrained optimization problems with an application in sparse robust portfolio optimization. Comput. Optim. Appl. 70(2), 503–530 (2018)
Bucher, M., Schwartz, A.: Second-order optimality conditions and improved convergence results for regularization methods for cardinality-constrained optimization problems. J. Optim. Theory Appl. 178, 383–410 (2018)
Burdakov, O., Kanzow, C., Schwartz, A.: On a reformulation of mathematical programs with cardinality constraints. In: D. Gao, N. Ruan, W. Xing (eds.) Advances in Global Optimization. Springer Proceedings in Mathematics and Statistics (2015)
Burdakov, O., Kanzow, C., Schwartz, A.: Mathematical programs with cardinality constraints: reformulation by complementarity-type conditions and a regularization method. SIAM J. Optim. 26(1), 397–425 (2016)
Burke, J.V.: A sequential quadratic programming algorithm for potentially infeasible mathematical programs. J. Math. Anal. Appl. 139, 319–351 (1989)
Candès, E.J., Wakin, M.B.: An introduction to compressive sampling. IEEE Signal Process. Mag. 25(2), 21–30 (2008)
Červinka, M., Kanzow, C., Schwartz, A.: Constraint qualifications and optimality conditions for optimization problems with cardinality constraints. Math. Program. 160, 353–377 (2016)
d’Aspremont, A., Bach, F., Ghaoui, L.E.: Optimal solutions for sparse principal component analysis. J. Mach. Learn. Res. 9, 1269–1294 (2008)
Dussault, J.P., Haddou, M., Kadrani, A., Migot, T.: How to compute an M-stationary point of the MPCC. Tech. rep. Université Sherbrooke, Sherbrooke (2019)
Flegel, M.L., Kanzow, C.: On M-stationary points for mathematical programs with equilibrium constraints. J. Math. Anal. Appl. 310(1), 286–302 (2005)
Gill, P.E., Murray, W., Saunders, M.A.: SNOPT: an SQP algorithm for large-scale constrained optimization. SIAM J. Optim. 12(4), 979–1006 (2002)
Hastie, T., Tibshirani, R., Friedman, J.: The Elements of Statistical Learning. Springer, New York Inc., New York (2001)
Hoheisel, T., Kanzow, C., Schwartz, A.: Convergence of a local regularization approach for mathematical programmes with complementarity or vanishing constraints. Optim. Methods Softw. 27(3), 483–512 (2012)
Izmailov, A.F.: Mathematical programs with complementarity constraints: regularity, optimality conditions, and sensitivity. Comput. Math. Math. Phys. 44(7), 1145–1164 (2004)
Li, X., Song, W.: The first-order necessary conditions for sparsity constrained optimization. J. Oper. Res. Soc. China 3, 521–535 (2015)
Markowitz, H.: Portfolio selection. J. Finance 7, 77–91 (1952)
Miller, A.: Subset Selection in Regression. Chapman and Hall/CRC Press, Boca Raton (2002)
Outrata, J.V.: Optimality conditions for a class of mathematical programs with equilibrium constraints. Math. Oper. Res. 24(3), 627–644 (1999)
Pan, L.L., Xiu, N.H., Zhou, S.L.: On solutions of sparsity constrained optimization. J. Oper. Res. Soc. China 3, 421–439 (2015)
Ramos, A.: Mathematical programs with equilibrium constraints: a sequential optimality condition, new constraint qualifications and algorithmic consequences. Optim. Methods Softw. (2019). https://doi.org/10.1080/10556788.2019.1702661
Ribeiro, A.A., Sachine, M., Santos, S.A.: On the augmented subproblems within sequential methods for nonlinear programming. Comput. Appl. Math. 36, 1255–1272 (2017)
Ribeiro, A.A., Sachine, M., Santos, S.A.: On the approximate solutions of augmented subproblems within sequential methods for nonlinear programming. Comput. Appl. Math. 37, 6601–6618 (2018)
Ruiz-Torrubiano, R., García-Moratilla, S., Suárez, A.: Optimization problems with cardinality constraints. In: Tenne, Y., Goh, C.K. (eds.) Computational Intelligence in Optimization, pp. 105–130. Academic Press, Berlin (2010)
Scheel, H., Scholtes, S.: Mathematical programs with complementarity constraints: stationarity, optimality, and sensitivity. Math. Oper. Res. 25(1), 1–22 (2000)
Sun, X., Zheng, X., Li, D.: Recent advances in mathematical programming with semi-continuous variables and cardinality constraint. J. Oper. Res. Soc. China 1, 55–77 (2013)
Svanberg, K.: A class of globally convergent optimization methods based on conservative convex separable approximations. SIAM J. Optim. 12, 555–573 (2002)
Tibshirani, R.: Regression shrinkage and selection via the Lasso. J. R. Stat. Soc. 58, 267–288 (1996)
Acknowledgements
We are thankful to the remarks and suggestions of the reviewers, which helped us to improve the presentation of this work.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
This work was partially supported by CNPq (Grant 309437/2016-4)
Rights and permissions
About this article
Cite this article
Krulikovski, E.H.M., Ribeiro, A.A. & Sachine, M. On the Weak Stationarity Conditions for Mathematical Programs with Cardinality Constraints: A Unified Approach. Appl Math Optim 84, 3451–3473 (2021). https://doi.org/10.1007/s00245-021-09752-0
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00245-021-09752-0
Keywords
- Mathematical programs with cardinality constraints
- Nonlinear programming
- Sparse solutions
- Constraint qualification
- Weak stationarity