半定规划松弛方法在无约束0-1二次规划问题中的理论研究及应用

Semidefinite Programming (SDP) is a prominent research object in optimization theory and applications, especially in nonlinear integer programming. We are interested in the applications of semidefinite programming for unconstrained quadratic 0-1 program (UQP). ..In this project, we will concentrate on the applications of SDP for the study of the properties optimal solutions of UQP, including constructing algorithms for UQP via the geometric properties of SDP relaxation solutions, and developing the sufficient conditions for the optimal solutions of UQP and exploring some conditions for UQP which can figure out some polynomially solvable cases of UQP...We will explore the properties of the optimal solutions of UQP via the geometric properties of the objective contour, and construct some perturbed problem to proximate the primal problem. Getting the perturbed multiplier by the semidefinite relaxation of the UQP, we will study the relationships of the optimal solutions of UQP and SDP and attempt to construct the optimal conditions for UQP. Further more, we will construct some polynomially solvable cases for UQP via the study of the duality gap of the SDP relaxation problem and the primal problem. ..We will apply Sedumi to calculate the SDP problem and study our project by numerical computations.

半定规划已经发展成为化理论中的一个重要课题，是优化理论中的重要工具。对研究非线性整数规划有很重要的意义。申请者将以半定规划在无约束0-1二次规划问题中的理论及其应用作为研究内容，希望能够通过理论探索和数值计算相结合的方法，研究以下内容：(1)应用半定规划松弛方法以及目标函数等高线的几何特性，探索无约束0-1二次规划问题的特性，算法，最优解的特征;(2)构造无约束0-1二次规划的最优性条件。(3)研究半定规划松弛解与0-1二次规划最优解的差距，以期以此作为划分0-1二次规划问题求解复杂度的度量，寻找出适用性更为广泛的多项式时间类型的判别条件。..我们将利用半定规划现有算法数据包例如Sedumi等，通过数值实验和数值计算，直接调用半定规划算法程序，配合理论研究和推导，完成半定规划在无约束0-1二次规划问题中理论研究和应用。

无约束0-1二次规划问题在非线性整数规划研究领域中是一个经典的问题。随着近几年半定规划理论和计算的发展，“半定规划在研究无约束0-1二次规划中的应用”成为研究的一大热点问题。其中较为重要的是：利用半定规划求解无约束0-1二次规划的下界；利用半定规划推导该问题的最优性条件，以及利用半定规划确定无约束0-1二次规划的多项式时间类型等问题。我们针对这些问题进行了深入的研究。..首先，我们利用半定规划构造无约束0-1二次规划的扰动因子。求解出半定松弛问题后，在此基础上，在二次型矩阵的对角线上增加一个微小的正数，让矩阵从半定矩阵变化为正定矩阵。这样既可以利用半定规划得到一个好的下界，又可以得到几何性质较好的目标函数等高线。..第二，我们构造出目标函数具有强凸性的原文题的等价问题，利用目标函数等高线，推导出三个最优解的充分条件。这三个最优性条件具有一个广义的形式，即取决于0-1点到某一点的最近的k个点的距离。利用这些最优性条件，我们构造出应用这些最优性条件的算法，来提高分支定界法的效率。同时，应用这些最优性条件，推导出了无约束0-1二次规划的一类多项式时间类型问题。..第三，在研究目标函数等高线的过程中，我们发现了一类带盒子约束的凸二次整数规划的多项式时间类型。即，具有k-degree freedom的凸二次函数的整数规划问题，可以化为最多(mn)k 个凸二次规划的子问题的求解，从而确定了这一类多项式可解类型。这一判别条件对于无约束0-1二次规划也同样适用。