游扬1，张圣贵2
（1．福州外语外贸学院，福建 福州 350202；2.福建师范大学 数学与计算机科学学院）
摘要：本文在半定规划中的Gauss-Newton搜索方向的基础上研究一类特殊的二次半定规划(QSDP)求解问题,基于矩阵论和和凸规划理论中原始-对偶算法的NT搜索方向将此类二次半定规划问题转化为求解线性半定规划的最小二乘问题, 为了验证此理论的可行性本文验证了Gauss-Newton搜索方向在最小二乘问题中的存在性和唯一性.
教育期刊网 http://www.jyqkw.com
关键词 ：半定规划；二次半定规划(QSDP)；最小二乘问题；线性最小二乘问题(LQ)；Gauss-Newton方向
中图分类号：O221文献标识码：A文章编号：1673-260X（2015）05-0001-03
1 引言
近年来,半定规划(SDP)是最优化理论领域发展较完善、应用最广泛的规划.伴随着半定规划的发展,原始对偶内点算法已成为解决此类问题最有效的算法中的一员.20世纪90年代末随着线性半定规划的日趋成熟,人们自然而然地开始考虑更为复杂的半定规划——非线性半定规划,其中最为简单的一种规划就是二次半定规划（QSDP）.它在系统论、控制论等诸多领域具有着广泛的应用,而且凭借着矩阵理论和原始对偶算法中NT方向的相关理论可以将二次半定规划转化为线性半定最小二乘问题,使得二次半定规划在证券,金融风险分析,稳健性二次优化等领域中起着非常重要的作用.
在半定规划的原始对偶内点算法中目前为止已经被验证的应用最为广泛的搜索方向主要有如下四种:①AHO方向[1];②K..S..H方向[2];③H..K..M方向[3];④NT方向[4].其中NT方向和H..K..M方向已被人成功地推广到某类二次半定规划上[6,12].到目前为止NT方向被认为是此四个方向中应用最广泛最有效的的搜索方向.在找寻搜索方向时采用牛顿法,借助对称化将互补松弛条件用来求解KKT系统,搜索方向的合理性虽然得到了保障,但求解的过程不仅增加计算的复杂性而且容易导致KKT系统的不稳定.故而此方法还尚待完善.在文献[5]中SergeKruk等学者提出了用于求解线性SDP的新搜索方向即Gauss-Newton方向.若改用此方向可以避免松弛条件的对称化过程,计算的复杂性就得以降低,系统的稳定性也相应的增强.基于此，,本文选取具有特殊算子的一类QSDP，以NT方向为基础将其推广成二次半定规划中的Gauss-Newton方向,并运用优化中的相关理论证明了Gauss-Newton方向的存在唯一性.
为了便于描述,我们做如下规定:（△X,△λ,△Z）表示搜索方向,λ表示拉格朗日乘子,μ表示为障碍参数，Q(X)=
PiXPi为具有半正定性质的自伴随算子.记X·Q(X)=tr(X·Q(X)).
2 QSDP的Gauss-Newton搜索方向的存在唯一性
二次半定规划的一般形式为
min1/2Q(X)+C·X
s.t.Bi·X=ai(i=1,…,k)(1)
X≥0
其中Q是Sn到Sn的具有半正定性质的自伴随线性算子,X≥0规定X为半正定矩阵,Bi是n阶实对称阵(i=1,…,k),且B1,…,Bk是线性无关的,ai为n维列向量.
基于算子的选取不同导致二次半定规划的类型不同.故而,本文选取Q(X)=PiXPi,来探讨此类QSDP问题中的Gauss-Newton方向的存在性及其唯一性.由凸规划中的Wolf对偶理论可得原始规划相应的对偶规划为
再由KKT条件以及类似于文献[6]的处理方法利用松弛条件对上述半定规划(2)进行改写,得到了扰动方程组
上述系统(3)的解被称为中心路径,记为(X(μ),λ(μ),Z(μ)),其中μ为中心路径参数.
若规定原始对偶算法中变量X,Z迭代过程产生的下一步步长分别为△X,△Z，故此步长变量在理想情形下即为如下系统的解[7]
正是因为系统(4)的非线性,zhang等学者在文献[8]中利用互补松弛条件的对称化这一技巧将此系统转化为线性系统.但这一过程却大大增加了系统计算的复杂性,在1998年Kruk于文献[5]中将此非线性系统问题转化为最小二乘问题来考虑,并在文中严谨地证明了求解此类问题的Gauss-Newton方向的存在性和唯一性.基于上述事实，本文将此方法加以推广用以求解下列最小二乘问题(5),并推导出求解系统(3)相应的Gauss-Newton方向,最后论证该搜索方向的存在性和唯一性.
系统(4)可等价地改写为如下最小二乘问题：
由文献[6]中的NT方向,定义如下矩阵
(V+WX)(V+WZ)=μI(6)
WX=WXT≥0
从而系统(6)可等价转化为
由于问题(7)中含有非线性项WX,WZ,直接求解此最小二乘问题很繁琐.文献[5]已经证明忽略问题中出现的非线性项WX,WZ不会改变该问题本身固有属性,并忽略此项后，因为所取范数的类型决定了该最小二乘问题的最优解,故当所给问题的范数类型确定时问题也随之被唯一确定.这里选取由内积导出的范数.内积做如下定义::
〈A,B〉=tr(V-1AV-1B),?坌A=AT,B=BT.
此内积可被看作是由障碍函数f(V)=-lndet(V)的Hessian矩阵诱导出的局部范数.因为f的Hessian矩阵V的值是一个线性的算子?塄2f(V):H→V-1HV-1.所以我们就相应的得到如下最小二乘问题[7]
这里最小二乘问题的范数取F-范数[9].为了方便叙述,
此类最小二乘问题的解被研究者们称为残差,(WX,△λi,WZ)也就是Gauss-Newton搜索方向,下面我们来验证Gauss-Newton方向的存在性及其唯一性
定理1 最小二乘问题（9）中Gauss-Newton方向(WX,△λi,WZ)是唯一的.
证明 不妨设WX和WZ为变量, 故问题(9)是一个限定在多面集上可行的凸二次优化问题,而且它的最优值的下界为0.针对此类问题的最优值存在性的论证可见文献[10]，这里就不在赘述.对于这样的一个问题的最优值的存在性见文献[10]是为大家所熟知的.故,本文只验证此类最小二乘问题解的唯一性.在证明之前先做如下处理:忽略问题(9)中目标函数包含的U,U-1这两项,得到的简化系统我们称其为问题(9)的相似系统,即
如果问题(10)只存在零解,我们便可以推出问题(9)有唯一解.因此下面主要验证问题(10)只存在零解.因为问题(10)
综上所述，WX=WZ=0是问题(10)的唯一解.从而问题(9)的解也是唯一的.即Gauss-Newton方向(WX,△λi,WZ)是唯一的.证毕.
3 问题与总结
本文以线性半定规划的Gauss-Newton方向以及二次半定规划(QSDP)的NT搜索方向的理论为基础,将Gauss- Newton方向从LSDP推广到一类特殊的QSDP,并验证了Gauss-Newton方向的存在性及其唯一性.但本文中只给出了与原始问题等价的线性最小二乘问题,在文献[11]中研究者A.Bjorck提出了用矩阵QR分解简化求解此类问题,若可以将其推广并应用到本文所提的优化问题中,便将进一步完善本文所提理论的系统性.
教育期刊网 http://www.jyqkw.com
参考文献：
〔1〕F.Alizadeh, J.P.A.Haeberly and M.L.Overton. Primal dual methods for semidefinite programming：convergence rates, stability and numerical results[J]. SIAM J. Optim. , 1998,8(3):746-768.
〔2〕R.D.C. Monteiro. Primal dual path following algorithms for semidefinite programming[J]. SIAM J. Optim. , 1997,7:663-678.
〔3〕M. Kojima, S. Shindoh and S.Hara. Interior point methods for the monotone semidefinite complementarity promble in symmtric matrices[J].SIAM J.Optim. , 1997,7:86-125.
〔4〕M.J.Todd, K.C.Toh and R.H.Tutuncu. On the Nesterov-Todd direction in semidefinite programming[J]. SIAM J. Optim. , 1998, 8(3): 769-796.
〔5〕S.Kruk, M.Muramatsu, F.Rendl et al. The Gauss-Newton direction in semidefinite programming[J]. Optimization Methods and Software, 2001, issue 1:1-28.
〔6〕游扬，张圣贵.一类二次半定规划内点算法的K..S..H搜索方向的存在唯一性[J].福建师范大学学报(自然科学版)，2012,28(1):16-20.
〔7〕E.de Klerk, J.Peng, C. Roos,T.Terlaky. A scaled Gauss-Newton Primal-Dual Search Direction for Semidefinite Optimization. http://citeseerx.ist.psu.edu/viewdoc.
〔8〕Y. Zhang. On extending some primal-dual interior point algorithms from linear programming to semidefinite programming. SIAM Journal on Optimization, 1998,8(2):365-386.
〔9〕陈宝林.最优化理论与算法（第2版）[M].北京：清华大学出版社，2005.10.
〔10〕Dimitri P.Bertsekas with Angelia Nedic and Asuman E. Ozdaglar. Convex Analysis and Optimization: 凸分析与优化(第二版)[M].北京：清华大学出版社，2006.2.
〔11〕A. Bjorck. Numerical Methods for Least Squares Problems. SIAM, Philadelphia, 1996.
〔12〕黄静静，王爱文.二次半定规划的原始对偶内点算法的H..K..M搜索方向的存在唯一性[J].数学实践与认识，2008,38(18):233-238.