一类二次半定规划Gauss-Newton方向的存在唯一性

游 扬，张圣贵

（1．福州外语外贸学院，福建 福州 350202；2.福建师范大学 数学与计算机科学学院）

一类二次半定规划Gauss-Newton方向的存在唯一性

游 扬1，张圣贵2

（1．福州外语外贸学院，福建 福州 350202；2.福建师范大学 数学与计算机科学学院）

本文在半定规划中的Gauss-Newton搜索方向的基础上研究一类特殊的二次半定规划（QSDP）求解问题，基于矩阵论和和凸规划理论中原始-对偶算法的NT搜索方向将此类二次半定规划问题转化为求解线性半定规划的最小二乘问题，为了验证此理论的可行性本文验证了Gauss-Newton搜索方向在最小二乘问题中的存在性和唯一性.

半定规划；二次半定规划（QSDP）；最小二乘问题；线性最小二乘问题（LQ）；Gauss-Newton方向

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方向的存在唯一性.

2 QSDP的Gauss-Newton搜索方向的存在唯一性

二次半定规划的一般形式为

其中Q是Sn到Sn的具有半正定性质的自伴随线性算子，X≥0规定X为半正定矩阵，Bi是n阶实对称阵（i=1，…，k），且B1，…，Bk是线性无关的，ai为n维列向量.

再由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方向，定义如下矩阵

从而系统（6）可等价转化为

由于问题（7）中含有非线性项WX，WZ，直接求解此最小二乘问题很繁琐.文献［5］已经证明忽略问题中出现的非线性项WX，WZ不会改变该问题本身固有属性，并忽略此项后，因为所取范数的类型决定了该最小二乘问题的最优解，故当所给问题的范数类型确定时问题也随之被唯一确定.这里选取由内积导出的范数.内积做如下定义：：此内积可被看作是由障碍函数f（V）=-lndet（V）的Hessian矩阵诱导出的局部范数.因为f的Hessian矩阵V的值是一个线性的算子▽2f（V）：H→V-1HV-1.所以我们就相应的得到如下最小二乘问题［7］

这里最小二乘问题的范数取F-范数［9］.为了方便叙述，

如果问题（10）只存在零解，我们便可以推出问题（9）有唯一解.因此下面主要验证问题（10）只存在零解.因为问题（10）

3 问题与总结

本文以线性半定规划的Gauss-Newton方向以及二次半定规划 （QSDP）的NT搜索方向的理论为基础，将Gauss-Newton方向从LSDP推广到一类特殊的QSDP，并验证了Gauss-Newton方向的存在性及其唯一性.但本文中只给出了与原始问题等价的线性最小二乘问题，在文献［11］中研究者A.Bjorck提出了用矩阵QR分解简化求解此类问题，若可以将其推广并应用到本文所提的优化问题中，便将进一步完善本文所提理论的系统性.

〔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.Interiorpoint 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.Rendletal.TheGauss-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.deKlerk，J.Peng，C.Roos， T.Terlaky.A scaled Gauss-Newton Primal-DualSearch Direction for Semidefinite Optimization.http：//citeseerx.ist.psu. edu/ viewdoc.

〔8〕Y.Zhang.On extending some primal-dualinterior 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.NumericalMethods for Least Squares Problems.SIAM，Philadelphia，1996.

〔12〕黄静静，王爱文.二次半定规划的原始对偶内点算法的H..K..M搜索方向的存在唯一性 ［J］.数学实践与认识，2008，38（18）：233-238.

O221

A

1673-260X（2015）05-0001-03

福建省教育厅B类项目（JB13364S）资助