正则对偶方法在二次规划问题中的理论与应用

项目名称： 正则对偶方法在二次规划问题中的理论与应用

项目编号： No.10801087

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

立项/批准年度： 2009

项目学科： 石油、天然气工业

项目作者： 王振波

作者单位： 清华大学

项目金额： 17万元

中文摘要： 对偶方法是研究优化问题的一种重要手段。对于非凸优化来说，经典的对偶方法会造成原始与对偶问题的对偶间隙。正则对偶方法通过正则变换建立对偶问题，在一定条件下，对偶问题与原问题没有对偶间隙。正则对偶方法的提出对求解困难的非光滑，非凸优化问题提供了一个有力的工具。根据研究计划，本项目研究了以下几个问题，并得到相应的研究结果。1.建立标准的正则对偶问题，并对正则对偶原理给出严格的数学证明；2.给出二次规划问题可用正则对偶方法求解的必要条件，并设计有效算法来求解对偶问题；3.把研究范围扩展到非负二次函数锥，得到了更好可解性条件及解的近似。4. 基于锥优化理论，提出并设计了二次函数锥的内逼近方法。

中文关键词： 全局最优化；二次规划；对偶理论；非负二次函谁锥；组合优化

英文摘要： Dual approach is an important method in the study of optimization problems. Classical dual approaches may suffer from having a potential duality gap. The canonical duality approach constructs the dual problem by the canonical transformation, and it is proved that there is no duality gap under certain condition. The canonical duality theory is originally developed for handling general nonconvex and nonsmooth systems. The canonical duality theory has shown its potential for some global optimization and nonconvex analysis. According to the project proposal, we study the following key problems. 1. Present the standard canonical dual problem, and give the mathematical proofs for the canonical duality theory. 2. Find the necessary conditions that a quadratic program can be solved by canonical duality approach. 3. Extend the scopes to cones of nonnegative quadratic functions, and obtain better results on optimality conditions and approximation solutions. 4. Base on the theory of conic program, we present an inner approximation approach to quadratic program.

英文关键词： quadratic program; duality theory; cones of nonnegative quadratic functions; combinatorial optimization