标题： 凸二次集与混合整数凸二次规划的复杂性 显示英文标题

标题： Convex quadratic sets and the complexity of mixed integer convex quadratic programming

摘要： 在纯整数线性规划中，通常希望处理满维度的多面体，众所周知，可以在多项式时间内将任意多面体约化为满维度的多面体。 更确切地说，利用Hermite标准型，可以通过映射到较低维度空间中的一个同构满维度多面体，从而将非满维度多面体转换为满维度的多面体，同时保留整数向量。 本文同时从两个方向扩展了上述结果。首先，我们利用“整数反射广义逆”的概念，考虑混合整数向量而不是整数向量。其次，我们将多面体替换为凸二次集，这些集合是通过在一个额外的凸二次不等式约束下从多面体获得的。 我们研究了凸二次集的结构特性，并利用这些特性得到了多项式时间算法，用于识别满维度的凸二次集，以及找到一个仿射函数，该函数可以将非满维度的凸二次集映射到较低维度空间中的同构满维度凸二次集，同时保留混合整数向量。 我们通过证明这些结果可以用来证明混合整数凸二次规划在参数为整数变量数量的情况下是固定参数可处理的，展示了这些结果的应用价值和潜在影响。我们的算法统一并扩展了固定维度下的纯整数凸二次规划和凸二次规划的已知多项式时间可解性。 显示英文摘要

摘要： In pure integer linear programming it is often desirable to work with polyhedra that are full-dimensional, and it is well known that it is possible to reduce any polyhedron to a full-dimensional one in polynomial time. More precisely, using the Hermite normal form, it is possible to map a non full-dimensional polyhedron to a full-dimensional isomorphic one in a lower-dimensional space, while preserving integer vectors. In this paper, we extend the above result simultaneously in two directions. First, we consider mixed integer vectors instead of integer vectors, by leveraging on the concept of "integer reflexive generalized inverse." Second, we replace polyhedra with convex quadratic sets, which are sets obtained from polyhedra by enforcing one additional convex quadratic inequality. We study structural properties of convex quadratic sets, and utilize them to obtain polynomial time algorithms to recognize full-dimensional convex quadratic sets, and to find an affine function that maps a non full-dimensional convex quadratic set to a full-dimensional isomorphic one in a lower-dimensional space, while preserving mixed integer vectors. We showcase the applicability and the potential impact of these results by showing that they can be used to prove that mixed integer convex quadratic programming is fixed parameter tractable with parameter the number of integer variables. Our algorithm unifies and extends the known polynomial time solvability of pure integer convex quadratic programming in fixed dimension and of convex quadratic programming.