MATHEMATICAL PROGRAMS WITH CARDINALITY CONSTRAINTS: REFORMULATION BY COMPLEMENTARITY-TYPE CONDITIONS AND A REGULARIZATION METHOD
MATHEMATICAL PROGRAMS WITH CARDINALITY CONSTRAINTS: REFORMULATION BY COMPLEMENTARITY-TYPE CONDITIONS AND A REGULARIZATION METHOD
复制标题
DOI：
10.1137/140978077
复制
发表时间：
2016-01-01
影响因子：
3.1
通讯作者：
Schwartz, Alexandra
中科院分区：
文献类型：
--
作者：
Burdakov, Oleg P.;Kanzow, Christian;Schwartz, Alexandra
具有基数约束的优化问题是非常困难的数学规划，通常通过离散优化的全局技术来解决。在这里，我们介绍了一个混合整数制定的标准松弛仍然有相同的解决方案（在全局最小值的意义上）作为基本的基数约束问题的局部最小值之间的关系也进行了详细讨论。由于我们的重新表述是一个连续变量的最小化问题，它使我们能够将该领域的思想应用于基数约束问题。在这里，特别是，因此，我们也得到合适的平稳性条件，并建议一个适当的正则化方法解决基数约束的优化问题。这种正则化方法被证明是全局收敛到一个Mordukhovich稳定点。大量的数值结果来说明这种方法的行为。
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.