Article Contents

2024, Volume 14, Issue 3: 614-635. Doi: 10.3934/naco.2023011

This issue Previous Article Quasi Strongly $ E $-preinvexity and its relationships with non-linear programming Next Article

Optimality conditions and constraint qualifications for cardinality constrained optimization problems

Zhuoyu Xiao^1, and
Jane J. Ye^2, ,

1.
Department of Industrial and Manufacturing Engineering, Pennsylvania State University, State College, PA, USA, 16802
2.
Department of Mathematics and Statistics, University of Victoria, Victoria, B.C., Canada, V8W 2Y2

^*Corresponding author
^*Corresponding author

Received: September 2022

Revised: February 2023

Early access: March 2023

Published: September 2024

Abstract / Introduction Full Text(HTML) Figure(3) / Table(1) Related Papers Cited by

Abstract

The cardinality constrained optimization problem (CCOP) is an optimization problem where the maximum number of nonzero components of any feasible point is bounded. In this paper, by rewriting the cardinality constraint as a constraint requiring that any feasible point must lie in the union of certain subspaces, we consider CCOP as a mathematical program with disjunctive subspaces constraints (MPDSC). Since a subspace is a special case of a convex polyhedral set, MPDSC is a special case of the mathematical program with disjunctive constraints (MPDC). Using the special structure of subspaces, we are able to obtain more precise formulas for the tangent and (directional) normal cones for the disjunctive set of subspaces. We then obtain first and second order optimality conditions by using the corresponding results from MPDC. Thanks to the special structure of the subspace, we are able to obtain some results for MPDSC that do not hold in general for MPDC. In particular we show that the relaxed constant positive linear dependence (RCPLD) is a sufficient condition for the metric subregularity/error bound property for MPDSC which is not true for MPDC in general. Finally we show that under all constraint qualifications presented in this paper, certain exact penalization holds for CCOP.

Keywords:

Cardinality constrained optimization problems,
disjunctive subspaces constraints,
necessary optimality conditions,
constraint qualifications,
metric subregularity,
error bounds property,
RCPLD.

Mathematics Subject Classification: Primary: 49J52, 49J53, 90C26, 90C46.

Citation:

FullText(HTML)

Figure 1. Feasible set for the cardinality constraints: (i) $ \|x\|_{0}\leq 1 $ in $ \mathbb{R}^2 $; (ii) $ \|x\|_{0}\leq 2 $ in $ \mathbb{R}^3 $

Download: Full-size image PowerPoint slide

Figure 2. Relations among various constraint qualifications for MPDSC

Download: Full-size image PowerPoint slide

Figure 3. Relations among new constraint qualifications for CCOP

Download: Full-size image PowerPoint slide

Table 1. Various cones to set $ S $ in CCOP

Cones	$ \|I_{\pm}(x^{\ast})\|<s $ (or $ \|I_{\pm}(x^{\ast})\cup I_{\pm}(d)\|<s $)	$ \|I_{\pm}(x^{\ast})\|=s $ (or $ \|I_{\pm}(x^{\ast})\cup I_{\pm}(d)\|=s $)
$ T_{S}(x^{\ast}) $	$ \bigcup\limits_{{I_{\pm}(x^{\ast})\subseteq \mathcal{I} \in \mathcal{I}_{s}}} \mathbb{R}_{\mathcal{I}} $	$ \mathbb{R}_{{I_{\pm}(x^{\ast})}} $
$ \hat{N}_{S}(x^{\ast}) $	$ \{0\} $	$ \mathbb{R}_{{I_{\pm}(x^{\ast})}}^{\perp} $
$ N_{S}(x^{\ast}) $	$ \bigcup\limits_{{I_{\pm}(x^{\ast})\subseteq \mathcal{I} \in \mathcal{I}_{s}}} \mathbb{R}_{\mathcal{I}}^{\perp} $	$ \mathbb{R}_{{I_{\pm}(x^{\ast})}}^{\perp} $
$ N_{S}(x^{\ast};d) $	$ \bigcup\limits_{{I_{\pm}(x^{\ast})\cup I_{\pm}(d) \subseteq \mathcal{I} \in \mathcal{I}_{s}}} \mathbb{R}_{\mathcal{I}}^{\perp} $	$ \mathbb{R}_{{I_{\pm}(x^{\ast})\cup I_{\pm}(d)}}^{\perp} $
$ \hat{N}_{T_{S}(x^{\ast})}(d) $	$ \{0\} $	$ \mathbb{R}_{{I_{\pm}(x^{\ast})\cup I_{\pm}(d)}}^{\perp} $

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	W. Achtziger and C. Kanzow, Mathematical programs with vanishing constraints: optimality conditions and constraint qualifications, Math. Program., 114 (2008), 69-99. doi: 10.1007/s10107-006-0083-3.
[2]	L. Adam, M. Červinka and and M. Pištěk, Normally admissible stratifications and calculation of normal cones to a finite union of polyhedral sets, Set-Valued Var. Anal., 24 (2016), 207-229. doi: 10.1007/s11228-015-0325-8.
[3]	J-P. Aubin and H. Frankowska, Set-valued Analysis, Boston, Birkhäuser, 2009. doi: 10.1007/978-0-8176-4848-0.
[4]	K. Bai, J. J. Ye and J. Zhang, Directional quasi-/pseudo-normality as sufficient conditions for metric subregularity, SIAM J. Optim., 29 (2019), 2625-2649. doi: 10.1137/18M1232498.
[5]	H. H. Bauschke, D. R. Luke, H. M. Phan and X. Wang, Restricted normal cones and sparsity optimization with affine constraints, Found. Comput. Math., 14 (2014), 63-83. doi: 10.1007/s10208-013-9161-0.
[6]	A. Beck and Y. C. Eldar, Sparsity constrained nonlinear optimization: Optimality conditions and algorithms, SIAM J. Optim., 23 (2013), 1480-1509. doi: 10.1137/120869778.
[7]	A. Beck and N. Hallak, On the minimization over sparse symmetric sets projections, optimality conditions, and algorithms, Math. Oper. Res., 41 (2016), 196-223. doi: 10.1287/moor.2015.0722.
[8]	M. Benko, M. Červinka and T. Hoheisel, Sufficient conditions for metric subregularity of constraint systems with applications to disjunctive and ortho-disjunctive programs, Set-Valued Var. Anal., 30 (2022), 143-177. doi: 10.1007/s11228-020-00569-7.
[9]	M. Benko and H. Gfrerer, On estimating the regular normal cone to constraint systems and stationarity conditions, Optim., 66 (2017), 61-92. doi: 10.1080/02331934.2016.1252915.
[10]	M. Benko and H. Gfrerer, New verifiable stationarity concepts for a class of mathematical programs with disjunctive constraints, Optim., 67 (2018), 1-23. doi: 10.1080/02331934.2017.1387547.
[11]	M. Benko, H. Gfrerer and and J. Outrata, Calculus for directional limiting normal cones and subdifferentials, Set-Valued Var. Anal., 27 (2019), 713-745. doi: 10.1007/s11228-018-0492-5.
[12]	M. Benko, H. Gfrerer, J. J. Ye, J. Zhang and J. Zhou, Second-order optimality conditions for general nonconvex optimization problems and variational analysis of disjunctive systems, arXiv: 2203.10015.
[13]	D. Bertsimas and R. Shioda, Algorithm for cardinality-constrained quadratic optimization, Comput. Optim. Appl., 43 (2009), 1-22. doi: 10.1007/s10589-007-9126-9.
[14]	J. F. Bonnans and A. Shapiro, Perturbation Analysis of Optimization Problems, Springer, New York, 2000. doi: 10.1007/978-1-4612-1394-9.
[15]	M. Bucher and A. Schwartz, Second-order optimality conditions and improved convergence results for regularization methods for cardinality-constrained optimization problems, J. Optim. Theory Appl., 178 (2018), 383-410. doi: 10.1007/s10957-018-1320-7.
[16]	O. P. Burdakov, C. Kanzow and and A. Schwartz, Mathematical programs with cardinality constraints: reformulation by complementarity-type conditions and a regularization method, SIAM J. Optim., 26 (2016), 397-425. doi: 10.1137/140978077.
[17]	M. Červinka, C. Kanzow and and A. Schwartz, Constraint qualifications and optimality conditions for optimization problems with cardinality constraints, Math. Program., 160 (2016), 353-377. doi: 10.1007/s10107-016-0986-6.
[18]	F. H. Clarke, Optimization and Nonsmooth Analysis, Classics Appl. Math. 5, SIAM, Philadelphia, PA, 1990. doi: 10.1137/1.9781611971309.
[19]	M. L. Flegel, C. Kanzow and J. Outrata, Optimality conditions for disjunctive programs with application to mathematical programs with equilibrium constraints, Set-Valued Var. Anal., 15 (2007), 139-162. doi: 10.1007/s11228-006-0033-5.
[20]	H. Gfrerer, On directional metric subregularity and second-order optimality conditions for a class of nonsmooth mathematical programs, SIAM J. Optim., 23 (2013), 632-665. doi: 10.1137/120891216.
[21]	H. Gfrerer, Optimality conditions for disjunctive programs based on generalized differentiation with application to mathematical programs with equilibrium constraints, SIAM J. Optim., 24 (2014), 898-931. doi: 10.1137/130914449.
[22]	H. Gfrerer, Linearized M-stationarity conditions for general optimization problems, Set-Valued Var. Anal., 27 (2019), 819-840. doi: 10.1007/s11228-018-0491-6.
[23]	I. Ginchev and B. S. Mordukhovich, On directionally dependent subdifferentials, C. R. Bulg. Acad. Sci., 64 (2011), 497-508.
[24]	R. Henrion and J. Outrata, On calculating the normal cone to a finite union of convex polyhedra, Optim., 57 (2008), 57-78. doi: 10.1080/02331930701778874.
[25]	C. Kanzow, A. B. Raharja and A. Schwartz, Sequential optimality conditions for cardinality-constrained optimization problems with applications, Comput. Optim. Appl., 80 (2021), 185-211. doi: 10.1007/s10589-021-00298-z.
[26]	E. H. M. Krulikovski, A. A. Ribeiro and M. Sachine, On the weak stationarity conditions for mathematical programs with cardinality constraints: a unified approach, Appl. Math. Optim., 84 (2021), 3451-3473. doi: 10.1007/s00245-021-09752-0.
[27]	Y.-C. Liang and J. J. Ye, Optimality conditions and exact penalty for mathematical programs with switching constraints, J. Optim. Theory Appl., 190 (2021), 1-31. doi: 10.1007/s10957-021-01879-y.
[28]	Z. Lu, Optimization over sparse symmetric sets via a nonmonotone projected gradient method, arXiv: 1509.08581.
[29]	Z. Q. Luo, J. S. Pang and D. Ralph, Mathematical Programs with Equilibrium Constraints, Cambridge University Press, Cambridge, 1996. doi: 10.1017/CBO9780511983658.
[30]	P. Mehlitz, On the linear independence constraint qualification in disjunctive programming, Optim., 69 (2020), 2241-2277. doi: 10.1080/02331934.2019.1679811.
[31]	P. Mehlitz, Stationarity conditions and constraint qualifications for mathematical programs with switching constraints, Math. Program., 181 (2020), 149-186. doi: 10.1007/s10107-019-01380-5.
[32]	P. Mehlitz, Asymptotic stationarity and regularity for nonsmooth optimization problems, J. Nonsmooth Anal. Optim., 1 (2020), 6575. doi: 10.46298/jnsao-2020-6575.
[33]	B. S. Mordukhovich, Variational Analysis and Generalized Differentiation, Vol. 1: Basic Theory, Vol. 2: Applications, Springer, Berlin, 2006. doi: 10.1007/3-540-31247-1.
[34]	B. S. Mordukhovich, Variational Analysis and Applications, Monographs in Mathematics, Springer, Cham, Switzerland, 2018. doi: 10.1007/978-3-319-92775-6.
[35]	L. L. Pan, N. H. Xiu and S. L. Zhou, On solutions of sparsity constrained optimization, J. Oper. Res. Soc. China, 3 (2015), 421-439. doi: 10.1007/s40305-015-0101-3.
[36]	L. L. Pan, N. H. Xiu and J. Fan., Optimality conditions for sparse nonlinear programming, Sci. China Math., 60 (2017), 759-776. doi: 10.1007/s11425-016-9010-x.
[37]	R. T. Rockafellar and R. J. Wets, Variational Analysis, Springer, Berlin, 1998. doi: 10.1007/978-3-642-02431-3.
[38]	A. M. Tillmann, D. Bienstock, A. Lodi and A. Schwartz, Cardinality minimization, constraints, and regularization: a survey, arXiv: 2106.09606.
[39]	M. Xu and J. J. Ye, Relaxed constant positive linear dependence constraint qualification for disjunctive programs., arXiv: 2204.09869.
[40]	J. J. Ye, The exact penalty principle, Nonlinear. Anal., 75 (2012), 1642-1654. doi: 10.1016/j.na.2011.03.025.
[41]	J. J. Ye and J. Zhou, Verifiable sufficient conditions for the error bound property of second-order cone complementarity problems, Math. Program., 171 (2018), 361-395. doi: 10.1007/s10107-017-1193-9.