应用改进的内点法求二阶锥规划的最优解.doc

应用改进的内点法求二阶锥规划的最优解
王璐1 , 高雷阜1
（1辽宁工程技术大学数学与系统科学研究所,辽宁 阜新 123000)
摘要：本文针对二阶锥规划的优化问题提出了一种改进的非精确内点算法。本算法允许搜索方向有相对较大的误差，且不要求迭代点的可行性，在相对不精确的假设下，利用该算法可找到二阶锥规划的近似解。从实验的结果可以看出,改进算法的性能得到了显著的提高。
关键词：二阶锥规划；非精确搜索方向；内点算法
中图分类号：O232 文献标识码：A
An Application of Improved interior point algorithm
on second-order cone programming
Wang Lu1, Gao Lei –fu1
(1.Mathematics and Systems Science Institute of Liaoning Technology University
Liaoning Fuxin 123000)
Abstract: A inexact interior point algorithm is presented for solving the second-order cone programming(SOCP) problem. The search direction of this algorithm allows a relatively larger error and dose not require interation points to be within the sets of strictly feasible solutions, under mild assumptions on the inexactness, we can find an approximate solution of the SOCP by using this algorithm. Numerical results suggest the effectiveness of our proposed algorithm .
Key words: second-order cone programming; inexact search direction; interior point algorithm
0引言
二阶锥规划问题是一族凸优化问题，而非线性规划，它是半定规划的特例。人们对二阶锥规划的研究已经有很长的历史了，如经典的Fermat-Weber问题可追溯到几个世纪以前,由于把二阶锥规划转化成半定规划求解，其效果并不很理想，因此人们开始对二阶锥规划进行深入研究。
对二阶锥规划的研究主要是建立在欧几里得约当代数基础上的，Faruat和Konary详细论述了这一理论。随后Nesetorv和Nemiorvski提出了用内点法求解凸规划的理论。上世纪九十年代，人们开始用内点法求解二阶锥规划及其特例(凸二约束下的二次规划)，自Nesteorv和Todd第一次用多项式时间原-对偶路径跟踪法以来，求解二阶锥规划的原-对偶内点算法才得以长足发展。
目前，对于二阶锥规划算法与性质的研究以及其在各领域的广泛应用都有了较大的进展，本文将对二阶锥规划的内点算法做进一步的研究。基于文献[3]中半定规划的算法，提出了一种新的改进的非精确内点算法。
1相关概念
定义1 二阶锥及其规划
二阶锥定义为：，为二阶锥的维数.
其原规划为：
对偶规划为：，其中。
定义2 欧几里得约当代数
二阶锥规划的算法是基于约当代数发展起来的，与二阶锥相伴的欧几里得约当代数定义为：，其中。
令，则有，其中
定义3 向量的谱分解
, 从而被写成，
其中，，，
将分成块处理, 其中,则，, , ,
定义4 约当块的标准化
定义标准约当块,其中标准特征向量，
将约当块转化为约当块，通过下面式子：
，详见文献[4]。
因此,
2非精确内点算法
2.1 主要思想
内点算法是一类求解二阶锥规划的非常有效的方法,在内点算法的每一步迭代中主要工作是通过求解一个非线性方程组来找一个搜索方向，但是由于计算机的精度原因，由以前的方法直接求解不仅花费了大量计算时间，而且得不到真正精确的搜索方向.事实上，非精确内点算法的基本思想是在中心路径的邻域内围绕中心路经前进，最终趋向最优点，但在计算过程中约当矩阵会出现奇异的现象,导致算法不稳定。本文提出的算法是将约当块通过函数进行标准化处理，再利用非精确内点算法求解二阶锥规划的最优解，这样既可保证算法的稳定性，又可以保证算法的全局收敛性，节约了大量的计算时间，使算法变得更为有效.
互补松弛定理：如果是二阶锥原规划的最优解，是其对偶规划的最优解，那么。
基于互补松弛定理，谱分解定义及约当块的标准化的相关理论, 二阶锥规划可转化为:

2.2 中心路径及其邻域

探索步：，，，
牛顿线性方程组：

2.3 非精确内点算法的实现
假设：（1）是二阶锥规划的原-对偶可行解，是特征值。
（2），其中
选择，初始点，选择，这样使得。
步1：选择
步2：计算牛顿线性方程组，从而解出搜索方向。
步3：选择探索步：，，，

步4：。
若或者，则停止。
如果，则；如果，则
3 实验结果
为了测试上述算法，我们用MATLAB8.0编写程序，测试了随机产生的1000个问题。设定步长为，，，其中，. 这些设定均符合传统的算法。
选择初始点，，。置，，矩阵，向量和在之间随机产生。
图3.1算法收敛性说明图 图3.2 收敛精度比较
测试结果表明，该算法具有以下两方面优点：
（1）精确度和稳定性。当原-对偶矩阵非退化，且具有严格互补条件，则牛顿系统具有非奇异性，且该算法具有二次收敛性，如图3.1.
（2）该算法具有较强的鲁棒性，如图3.2。
4结语
本文针对二阶锥规划问题提出的改进的非精确内点算法允许搜索方向有相对较大的误差，且不要求迭代点的可行性，在相对不精确的假设下，利用该算法可找到二阶锥规划的近似解。该改进算法与传统算法相比较，其性能得到了显著的提高。

本文作者创新点：通过将特征向量做标准化处理以及在算法实现过程中对系统进行分块处理，用向量代替，将半定规划的方法引进到了求解二阶锥规划中。
参考文献：
[1] Alizadeh F, Goldfarb D. Second-order cone programming. Mathematical Programming 2003;95(1, Ser. B):3–51.
[2] Alizadeh F, Haeberly JP, Overton ML. A new primal–dual interior point method for semidefinite programming. Proceedings of the fifth SIAM conference on applications of linear algebra. Snowbird, Utah, 1994.
[3] Xia Y, Alizadeh F. The Q Method for Symmetric Cone Programming. Manuscript, 2005.
[4] Goldfarb D, Scheinberg K. Product-form Cholesky factorization in interior point methods for second-order cone programming. Mathematical Programming 2005;103(1, Ser. A):153–79.
[5] Alizadeh F, Schmieta SH. Optimization with semidefinite, quadratic and linear constraints. Technical Report RRR 23-97, RUTCOR, Rutgers Univeristy, 1997.
[6] Xue G, Ye Y. An efficient algorithm for minimizing a sum of Euclidean norms with applications. SIAM Journal on Optimization 1997;7(4):1017–36.
[7]王凯，基于多项式光滑的支持向量回归机［J］．微计算机信息，2007，3-3：232-233。

作者简介：王璐，女，1983年生，硕士研究生，主要研究方向为最优化理论与方法。
高雷阜，男，1963年生，博士生导师，主要研究方向最优化理论与方法，混沌理论。
Biography: Wang Lu (1983-), female, master, major in Optimization Theory and Methods,.
Gao Leifu (1963-), male, Professor, major in Optimization Theory and Methods and Task Force Theory.
联系方式：
地址：辽宁省阜新市中华路辽宁工程技术大学资环研07-3班 123信箱 王璐
邮编：123000
邮箱：myhoneylu@