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

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

项目编号： No.11201281

项目类型： 青年科学基金项目

立项/批准年度： 2013

项目学科： 数理科学和化学

项目作者： 刘春丽

作者单位： 上海财经大学

项目金额： 21万元

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

中文关键词： 无约束；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.

英文关键词： Unconstrained；quadratic binary programming；optimality conditions；polynomial solvable case；semi-definite programming