李 扬，顾世煜

(1.沈阳理工大学 理学院，沈阳 110159； 2.东北中山中学，沈阳110001)

锥规化是一种特殊的凸规化，是线性规划的推广，是在一个仿射空间和一个正则锥的交集上，求线性目标函数的极大或极小值。锥规化问题涵盖了线性规划、凸二次约束规化、半正定规化、二次锥规化。近些年，由于锥规化理论和算法的发展，且在投资组合优化、最小风险套利、协方差矩阵的逼近等方面有广泛的应用，因而锥规化是数学规划领域的一个活跃的研究方向。锥规化问题是NP难问题,这种问题没有一个多项式时间的算法。Bomze等[1]尝试用可行下降法对锥规化求解，然而这种方法无法证明解的收敛性，并且需要额外的工作去找出一个可行的起始点，而找可行起始点的难度不亚于解决原问题。Zilinskas[2]使用一种单纯形划分的方法去解锥规化问题的对偶问题,但模型求解的运行时间过长。Deng等[3]将锥规化问题近似转化为一个二次规化问题，然后利用在椭球域上的非负二次函数定义的对偶锥，解一个线性锥规化序列，得到原问题的近似解。以上研究得到的近似解要么计算繁琐，要么得到解的近似程度不高。

本文引入建立在集合FSOC上的一种非负二次形式锥，利用一系列的非负二次形式锥近似计算一种有用的NP难锥规化问题，是利用对一种标准单形的划分去逼近对偶锥的方法，根据半正定规化的解法，得出NP难锥规化问题一个比较好的下界，进而得到原问题的一种近似解。……