【作者】 路程；

【导师】 邢文训；

【作者基本信息】 清华大学 ， 数学， 2011， 博士

【摘要】 非负二次函数锥，即在给定的区域上全体非负的二次函数构成的锥，是经典的半正定锥及共正锥的扩展。由于任意二次规划问题均可转化为与其等价的非负二次函数锥规划问题。因此，对非负二次函数锥规划问题进行深入研究，可以进一步促进二次规划的发展。在二次规划领域的传统研究方法中，拉格朗日对偶方法及半正定松弛方法是两类重要理论工具。然而这两类方法具有一定局限性。特别对于非凸情形，上述方法通常引入非零对偶间隙或松弛间隙。为了克服传统方法的局限性，本文将利用非负二次函数锥规划的理论与方法对二次规划进行研究。通过建立非负二次函数锥规划问题与二次规划问题拉格朗日乘子之间的理论联系，可以从线性锥规划的视角对二次规划问题的全局最优性条件，松弛算法，可解子类进行深入研究。基于这样的研究视角，本文提出了二次约束二次规划问题及0-1二次规划问题的新的全局最优性条件，该条件比以往文献中的半正定性条件更具一般性。同时，基于该条件，得到了一类可多项式时间求解的二次规划子类问题，从而扩大了问题的可解情形。在算法方面，为了有效求解非负二次函数锥规划问题，本文设计了自适应逼近策略。该策略可以根据问题数值特性自动地提高逼近效果。相关算法收敛性得到了证明，同时数值算例表明了其有效性。本文的主要创新点包括：通过建立非负二次函数锥规划与二次规划拉格朗日乘子之间的理论联系，提出了二次规划问题的新的全局最优性条件，该条件比以往文献中提到的半正定性条件更具一般性。基于锥规划的方法，给出了二次规划问题的新的可多项式时间求解的子类问题，从而进一步扩展了二次规划问题的可多项式时间求解情形。为了有效求解非负二次函数锥规划问题，设计了非负二次函数锥的可计算逼近策略。该策略对问题具有自适应性，即根据问题本身的数值特性，可自动地改进逼近效果。更多还原

【Abstract】 Cone of nonnegative quadratic functions is the cone of all quadratic functionsbeing nonnegative over a given feasible set. It is an extension of the well-known posi-tive semidefinite cone and copositive cone. Any quadratic programming problem canbe transformed to a conic programming problem over cones of nonnegative quadraticfunctions. Hence, it can further improves the development in quadratic programmingby study the conic programming over cones of nonnegative quadratic functions.In the literature, Lagrangian dual method and semidefinite relaxation method aretwo of the most important tools for studying quadratic programming. However, thesetwo methods have some limitations, especially for non-convex cases, they usually in-troduce a nonzero duality gap or slack gap. In order to overcome the limitations oftraditional methods, this thesis will use the theory of cones of nonnegative quadraticfunctions to study quadratic programming. In this thesis, we establish the theoreti-cal connections between programming problems over cones of nonnegative quadraticfunctions and quadratic programming problems, and then study the global optimal-ity conditions, solvable subclasses and relaxation methods of quadratic programmingfrom the view point of linear conic programming. Based on this research direction,we propose new global optimality conditions for quadratically constrained quadraticprogramming and0-1quadratic programming. These new conditions are more generalthan the positive semidefiniteness condition in the literature. We also propose a newpolynomial time solvable subclass of quadratic programming problems, which expandspreviously known solvable cases. To solve conic programming problems over cones ofnonnegative quadratic functions, we design an adaptive approximation scheme, whichcan automatically improve the approximation efectiveness based on the properties ofgiven problem instances. The convergence property of this scheme is proved. Somenumerical examples are shown to demonstrate the efectiveness of this scheme.The main contributions of the thesis are: By constructing the theoretical connections between conic programming prob-lems over cones of nonnegative quadratic functions and the Lagrangian multi-plier of quadratic programming problems, we propose a new global optimalitycondition, which is more general than the positive semidefiniteness condition inthe literature, for quadratic programming.Based on the algorithms for conic programming, we propose a new algorithm tosolve a subclass of quadratic programming problems. This result extends previ-ously known solvable class to more general cases.To solve the conic programming problems over cones of nonnegative quadraticfunctions, we design an adaptive approximation scheme, which can automati-cally improve the approximation efectiveness for given instances.更多还原