基于非负二次函数锥规划的有效不等式生成方法与应用研究

Valid inequality is an important tool for designing convex relaxations of quadratically constrained quadratic programming. However, most methods in the literature of generating valid inequalities are based on the special structure of the original problem or particular skills. Very few theoretical results are proposed on the sufficient and necessary conditions of whether valid inequalities improve the lower bound obtained by the convex relaxation problem. This proposal will study systematically on the generating methods of valid inequalities from the view of conic programming over the cone of nonnegative quadratic functions:.1.Based on the equivalence of quadratically constrained quadratic programming and conic programming over the cone of nonnegative quadratic functions, we mainly discuss the sufficient and necessary conditions of valid inequalities to determine whether a given valid inequality will improve the lower bound obtained by the relaxation problem. Then we will study how to generate valid inequalities dynamically and adaptively..2.When the global optimal solution of the original problem is known, we focus on the properties of the optimal solution of the corresponding conic program. We will use the known optimal solution to generate valid inequalities such that there is no gap between the relaxation problem and the original problem, to obtain new polynomial-time solvable subclasses..3.We will analyze the sensitivity of different valid inequalities on non-smooth optimal solutions of the conic programming, to propose a systematic method to generate the best valid inequalities..The accomplishment of this project will provide more general methods and theoretical tools to design high-quality convex relaxations of quadratically constrained quadratic programming.

有效不等式是设计二次规划凸松弛方法的重要工具。文献中现有的大多数方法通过挖掘问题结构特征生成特殊的有效不等式，需要很强技巧性。目前尚没有统一的理论探讨有效不等式何时能降低松弛间隙的充分必要条件。本项目拟从非负二次函数锥规划的视角对非凸二次规划有效不等式的生成方法进行系统研究：.1.利用二次规划与非负二次函数锥规划的等价性，从锥规划的视角对有效不等式进行理论分析，提出有效不等式改进松弛问题下界的充分必要条件及动态生成方法；.2.在非凸二次规划全局最优解已知的情况下，对非负二次函数锥规划最优解处的几何特征进行变分分析，得到有效不等式应满足的变分不等式，从而设计凸松弛方法使其与原问题最优解一致，进一步发现新的多项式时间可解子类；.3.对锥规划非光滑最优解处各类有效不等式的灵敏度进行分析，挖掘最佳有效不等式的生成方法。.本项目的顺利完成将为二次规划设计高质量的松弛方法提供更多的理论工具和求解手段。

有效不等式是设计二次规划凸松弛方法的重要工具，现有文献大多通过挖掘问题特征生成特殊的有效不等式。本项目从非负二次函数锥规划的视角对非凸二次规划有效不等式的生成方法进行了系统研究。本项目证明了非负二次函数锥规划与原问题的等价性，从锥规划的视角首次提出了有效不等式改进松弛问题下界的一般性充分必要条件。从理论上给出了有效不等式对偶变量最优解具有的性质和求解方法，对偶变量与松弛锥的对偶锥之间的关系，最稳定的支撑平面的存在性及生成方式。利用目标函数和约束函数负特征值的特征向量生成的有效不等式设计分支定界算法，降低了计算复杂性。根据松弛问题最优解设计了有效不等式的动态生成方法。上述工作为电力市场定价等实际问题提供了有效求解方案，为二次规划设计高质量的松弛方法提供了更多的理论工具和求解手段。