基数约束优化问题的松弛正线性约束规范

A Relaxed Constant Positive Linear Dependence Constraint Qualification for Cardinality-Constrained Optimization Problems

摘要: 基数约束优化问题在投资组合和统计回归等领域都有着广泛的应用。由于基数约束优化问题带有非凸非连续的约束，所以这类问题往往是难于求解的。为了处理较难的基数约束，可以通过引入连续变量将其改写为连续的非线性规划问题。但是大多数标准的约束规范并不适用于改写后的问题，因此有必要研究基数约束优化问题的约束规范。本文给出了基数约束优化问题的一个新的约束规范并证明了该约束规范可以保证最优性条件的成立。此外，还进一步讨论了新旧约束规范之间的强弱关系。

Abstract: Cardinality-Constrained (CC) optimization problems are widely used in many fields such as portfolio optimization and statistical regression. Such problems are difficult to deal with, because it involves a constraint that is not continuous neither convex. A classical way to deal with this difficult cardi-nality constraint consists of introducing continuous variables and then rewriting this kind of prob-lem as a continuous nonlinear problem. The standard constraint qualifications are usually violated for the NLP-reformulation. It is necessary to consider suitable constraint qualifications for cardinal-ity-constrained optimization problems. In this paper, we first define a new constraint qualification for cardinality constrained problems. We show that this constraint qualification ensures optimality conditions for constrained problems. Moreover, we discuss the relations between the old and new constraint qualifications.