论文部分内容阅读
二阶锥规划(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问题时,双非负锥松弛问题等价于一个新的半定锥松弛问题.同时,对于不同问题得到的不同松弛问题,测试了一些随机例子来比较这些松弛问题各自的计算效果.