Global aspects of the continuous reformulation for cardinality-constrained optimization problems. (English) Zbl 07925678
Summary: The main goal of this paper is to relate the topologically relevant stationary points of a cardinality-constrained optimization problem and its continuous reformulation up to their type. For that, we focus on the non-degenerate M- and T-stationary points, respectively. Their M-index and T-index, respectively, which uniquely determine the global and local structure of optimization problems under consideration in algebraic terms, are traced. As novelty, we suggest to regularize the continuous reformulation for this purpose. The main consequence of our analysis is that the number of saddle points of the regularized continuous reformulation grows exponentially as compared to that of the initial cardinality-constrained optimization problem. This growth appears to be inherent and is reproduced in other relaxation attempts.
MSC:
| 90C26 | Nonconvex programming, global optimization |
| 90C46 | Optimality conditions and duality in mathematical programming |
Keywords:
cardinality-constrained optimization problem; continuous reformulation; non-degenerate stationarity; index; genericityReferences:
| [1] | Donoho, DL.Compressed sensing. IEEE Trans Inf Theory. 2006;52(4):1289-1306. doi: · Zbl 1288.94016 |
| [2] | Tibshirani, R.Regression shrinkage and selection via the lasso. J R Stat Soc Series B. 1996;58:267-288. · Zbl 0850.62538 |
| [3] | Shechtman, Y, Eldar, YC, Szameit, A, et al. Sparsity-based sub-wavelength imaging with partially spatially incoherent light via quadratic compressed sensing. Opt Express. 2011;19(16):14807-14822. doi: |
| [4] | Burdakov, O, Kanzow, C, Schwartz, A.Mathematical programs with cardinality constraints: reformulation by complementarity-type conditions and a regularization method. SIAM J Optim. 2016;26(1):397-425. doi: · Zbl 1332.90220 |
| [5] | Jongen, HT, Jonker, P, Twilt, F.Nonlinear optimization in finite dimensions. Dordrecht: Kluwer Academic Publishers; 2000. · Zbl 0985.90083 |
| [6] | Lämmel, S, Shikhman, V. Cardinality-constrained optimization problems in general position and beyond. Pure and Applied Functional Analysis; 2021. To appear, arXiv:2106.08083. |
| [7] | Lämmel, S, Shikhman, V.Optimality conditions for mathematical programs with orthogonality type constraints. Set-Valued and Variational Analysis. 2023;31(9):1-21. doi: . · Zbl 1518.90076 |
| [8] | Červinka, M, Kanzow, C, Schwartz, A.Constraint qualifications and optimality conditions for optimization problems with cardinality constraints. Math Program. 2016;160(1-2):353-377. doi: · Zbl 1356.90146 |
| [9] | Bucher, M, Schwartz, A.Second-order optimality conditions and improved convergence results for regularization methods for cardinality-constrained optimization problems. J Optim Theory Appl. 2018;178(2):383-410. doi: · Zbl 1394.90475 |
| [10] | Scholtes, S.Convergence properties of a regularization scheme for mathematical programs with complementarity constraints. SIAM J Optim. 2001;11(4):918-936. doi: · Zbl 1010.90086 |
| [11] | Branda, M, Bucher, M, Červinka, M, et al. Convergence of a Scholtes-type regularization method for cardinality-constrained optimization problems with an application in sparse robust portfolio optimization. Comput Optim Appl. 2018;70(2):503-530. doi: · Zbl 1418.90252 |
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.
