【作者】 郭传好；

【导师】 白延琴；

【作者基本信息】 上海大学 ， 运筹学与控制论， 2013， 博士

【摘要】 二阶锥规划(second-order cone programming)、协正锥规划(eopositive cone pro-gramming)以及双非负锥规划(doubly nonnegativp cone programming)是三类重要的最优化问题,其中，二阶锥规划属于对称锥规划，协正锥规划和双非负锥规划属于非对称锥规划.这些锥规划的特殊结构特点,决定了它们在实际中的应用非常广泛,在人工智能、物联网、数据挖掘、投资组合以及动力系统与控制等领域中都有所应用.此外,协正锥规划还包含了组合优化中许多重要的具有挑战性的NP-难问题.如图的稳定数、二次选址、最大团等问题.因此,研究这三类特殊锥规划的算法理论和实际应用具有重要的理论意义和实际应用价值.本学位论文旨在较全面了解二阶锥规划、协正锥规划以及双非负锥规划的研究背景及其研究进展的基础上,对这三类锥规划问题的算法理论和应用进行相关研究.取得主要研究成果如下：(?)第二章研究了一类带有二阶锥约束的非凸二次规划问题.首先,基于二阶锥约束的结构特点,原问题被等价转化为一个二次约束二次规划问题.借助于向量的提升技术和线性锥规划的对偶理论,该二次约束二次规划问题被转化为一个线性锥规划问题,其中约束锥可以被一个半定锥和一个特殊锥的和有效的近似.其次.根据该线性锥规划问题的最优解和二次约束二次规划问题的KKT解的关系,我们给出了一个关于原问题的全局最优性条件.依据此条件,设计了一个求解原问题的算法.该算法在理论上能够保证所得到的最优解是原问题的全局最优解,或者得到的是原问题的一个下界.最后,我们对算法进行了初步的数值实验,数值结果表明该算法能够有效求得原问题的全局最优解,或得到一个较紧的下界.(?)第三章考虑了一类协正锥规划问题,即在一个特殊协正锥约束空间上求一个连续函数的极小值.首先,根据协正矩阵的定义,给出了协正矩阵另外一种等价的表达形式.基于该新的表达形式,原问题可以被等价转化为一个半无限规划问题.其次,根据离散化方法求解半无限规划问题的思想,给出了一个新的离散化算法来求解原问题.最后,在适当的假设条件下,证明了本章所给出的算法能够有限步收敛到原问题的可行近似最优解.(?)第四章讨论了一类带有线性与非负约束的多目标二次规划问题.该问题通常不存在使得所有目标函数同时达到最优的最优解.因此寻求Pareto有效解就成为求解原问题的关键.首先,利用线性加权和法,原问题被转化为一个单目标二次规划问题,其在通常情况下是非凸且NP-难的.借助于双非负锥松弛技术,这一单目标二次规划问题被松弛为一可计算的凸规划问题.在一定的假设条件下,该凸规划问题的最优解是原问题的Pareto有效(弱有效)解.最后,对一些随机的例子和实际投资组合例子进行了数值实验,实验结果表明我们所给出的方法是有效的.(?)第五章研究了一类0-1二次规划问题,其在通常情况下是非凸且NP-难的.为了求解该问题,给出了两种凸松弛方法：一种是半定锥松弛,一种是双非负锥松弛.而且,在一定的假设条件下,证明了这两种松弛方法所得到的问题是等价的.当原问题退化为Max-Cut问题时,双非负锥松弛问题等价于标准的半定锥松弛问题.当原问题退化为Densest k-Subgraph问题时,双非负锥松弛问题等价于一个新的半定锥松弛问题.同时,对于不同问题得到的不同松弛问题,测试了一些随机例子来比较这些松弛问题各自的计算效果.更多还原

【Abstract】 Second-order cone programming, copositive cone programming and doubly nonneg-ative cone programming are three important classes of optimization problems, among which second-order cone programming belongs to symmetric conic programming, eopos-itive cone programming and doubly nonnegative cone programming are both asymmetric conic programming. Since the special characteristics of these conic programming, they have widely applications in the real world. For example, artificial intelligence, inter-net of things, data mining, portfolio selection, dynamical systems and control, and so on. Moreover, copositive cone programming includes many important and challenging NP-hard problems in the areas of combinatorial optimization, such as stability number of a graph, quadratic-assignment, maximum clique, etc. Therefore, the studies on al-gorithms and practical applications for these three kinds of special conic programming have important theoretical significance and practical value.Based on the comprehensive understanding of the research progress for second-order cone programming and copositive cone programming as well as doubly nonnegative cone programming, this thesis aims to investigate the algorithms and applications for these three types of conic programming. The main contributions of the thesis are as follows:◣In Chapter2, we study a class of nonconvex quadratic programming problems with second-order cone constraint. First, according to the characteristics of the second-order cone constraint, the original problem is equivalently reformulated as a quadratically constrained quadratic programming problem. By using the lifting technique and the linear conic duality theory, the latter problem is converted into an equivalent linear conic programming problem, where the constraint cone can be inner approximated by a summation of positive seniideh’nite cone and the cone of special one. Then, a suf-ficient global optimization condition is developed for the original problem in terms of the relationship between the optima] solution of linear conic programming problem and the KKT solution of quadratically constrained quadratic; programming problem. Based on this condition, an algorithm for solving the original problem is presented. Theo-retically, the proposed algorithm which provides either a global optimal solution or a lower bound for the original problem. Finally, we test some elementary examples. The numerical results show that the proposed algorithm can effectively obtain the global optimal solutions or the tighter bounds for the test examples.? Chapter3is devoted to studying a type of copositive cone programming prob-lems. Based on the definition of copositive matrices, another equivalent expression for copositive matrices is presented. Using this new expression for copositive matrices, the original problem is equivalently transformed into a semi-infinite programming problem. Employing the idea of discretization method for solving semi-infinite programming, a new discretization algorithm for solving the latter semi-infinite programming problem is proposed. Moreover, under some mild assumptions, this new algorithm posses the finite-step convergence.? In Chapter4, we discuss a kind of multiple objective quadratic programming prob-lems with linear and nonnegative constraints, which does not have a single solution that simultaneously minimizes each objective function in general. So seeking Pareto efficient solutions is the key to solve the original problem. Exploiting the technique of the linear weighted sum method, the original multiple objective quadratic programming problem is transformed into a single objective one. Such a problem is nonconvex and NP-hard in general. By using the techniques of lifting and doubly nonnegative cone relaxation, respectively, this single objective quadratic programming problem is relaxed to a com-putable convex doubly nonnegative cone programming problem. The optimal solutions of this computable convex problem are Pareto (weekly) efficient solutions for the origi-nal problem under some mild conditions. Moreover, the proposed method is tested with some random examples and practical portfolio selection example. The numerical results show that the proposed method is effective and promising.? Chapter5focuses on the relationship between the semidifinite cone relaxation and the doubly nonnegative cone relaxation for binary quadratic programming problem. Under some suitable assumptions, we prove that the doubly nonnegative relaxation for the original problem is equivalent to a new semidifinite cone relaxation with tighter bound. If the original problem reduces to the Max-Cut problem, the doubly nonnegative cone relaxation for it is equivalent to the standard semidifinite cone relaxation. If the original problem reduces to the Densest k-Subgraph problem, the doubly nonnegative cone relaxation is equivalent to a tighter semidifinite cone relaxation. Furthermore, some comparative numerical results are reported to show the efficiency of these relaxation problems, respectively.更多还原