一种求解半定规划的邻近外梯度算法

于冬梅，高雷阜，赵世杰，杨培

（辽宁工程技术大学优化与决策研究所，辽宁阜新123000）

一种求解半定规划的邻近外梯度算法

于冬梅，高雷阜，赵世杰，杨培

（辽宁工程技术大学优化与决策研究所，辽宁阜新123000）

本文提出了一种求解半定规划的邻近外梯度算法.通过转化半定规划的最优性条件为变分不等式，在变分不等式满足单调性和Lipschitz连续的前提下，构造包含原投影区域的半空间，产生邻近点序列来逼近变分不等式的解，简化了投影的求解过程.将该算法应用到教育测评问题中，数值实验结果表明，该方法是解大规模半定规划问题的一种可行方法.

半定规划；变分不等式；次梯度半空间；外梯度算法

1　引言

半定规划（Semidefinite Programming，SDP）是线性规划（Linear Programming，LP）的一种拓广.与线性规划的约束条件不同，半定规划是在满足约束条件“对称矩阵的仿射组合半正定”的条件下，求目标函数极大（极小）化的问题.在半定规划模型下，线性规划、凸二次规划（Convex Quadratic Programming，CQP）、二阶锥规划（Second-order Cone Programming，SOCP）等规划问题均可看作其特殊形式［1］.于此同时，半定规划在特征值优化、控制论、组合优化以及工业工程设计等许多领域都具有广泛的应用.目前，半定规划的研究主要集中在求解方法上，线性规划内点法的巨大成功，启发人们将线性规划的内点法推广到半定规划上.在理论上，内点算法已经非常成熟，被证明是求解半定规划问题的有效方法之一［2］，但是内点法的运行通常需要一对严格的原始一对偶初始可行解，而选择合适的严格原始一对偶初始可行解非常困难，更为重要的是内点算法的每步迭代涉及到大量矩阵运算，这在很大程度上限制了其在大规模问题中的应用.

变分不等式问题（Variational Inequalities，VIP）不仅是数学规划领域的一个重要的组成部分，而且它还与其它数学规划问题有着紧密的联系.线性规划、非线性规划及互补问题都是变分不等式的特殊情形［3］.对于变分不等式问题的求解算法研究在近十几年中取得了很多优秀的研究成果.Pang和Chan在文献［4］中全面地介绍了变分不等式问题的解法及其收敛性，主要包括线性化求解方法，非线性化求解方法（如非线性Jacobi方法）等.20世纪90年代，何炳生教授提出了投影收缩算法［5］，韩乔明基于投影收缩算法的思想提出了解半定规划的二次摄动方法［6］，关秀翠证明了二次半定规划的最优性条件与线性对称变分不等式的等价性，并利用投影收缩算法求解［7］，徐凤敏等转化半定规划的最优性条件，提出了一种新的投影算法［8］.本文把半定规划问题转化为等价的变分不等式，在变分不等式满足单调性和Lipschitz连续的前提下，提出了一种邻近外梯度算法求解半定规划问题，通过数值实验验证本文的邻近外梯度算法对于半定规划问题的求解是可行的.

2　问题的提出

考虑如式（2.1）所示的标准形式的半定规划问题和如式（2.2）所示的其对偶问题.

其中矩阵C，Ai∈Rn×n，X∈Sn×n表示对称矩阵，表示X为半正定矩阵，“·”表示Frobenius内积，CX=Tr（CX）=表示矩阵CX的迹，

为给定的m维向量.

半定规划原问题（2.1）和其对偶问题（2.2）的最优性充分条件如下：

转化最优性条件（2.3）为变分不等式，利用邻近外梯度算法对SDP问题进行求解.

2.1变分不等式

定义2.1［9］设C为有限维欧氏空间中的非空闭凸子集，映射F：C→Rn，若对任意的x∈C，寻求x∗∈C使得下式恒成立

称式（2.5）为变分不等式问题，记为VIP（Ω，F）.

Noor在文献［10］中把上述变分不等式的经典定义推广到实Hilbert空间，给出如下定义.

定义2.2［10］设H为实Hilbert空间，其内积记为〈·，·〉，范数记为‖·‖，Ω⊂H为一非空闭凸集，映射F：H→H，对任意的v∈Ω，求u∈Ω，使下式恒成立

定义2.3设H为实Hilbert空间，F：H→H为一映射，

（1）若对任意的u，v∈Ω，都有〈F（u）-F（v），v-u〉≥0成立，则称F在Ω上是单调的.

（2）若对任意的u，v∈Ω，存在τ＞0，使得

成立，则称F在Ω上强单调，其中τ被称为映射F的强单调常数.

（3）若对任意的u，v∈Ω，存在L＞0，使得

则称F在Ω上Lipschitz连续，其中L为常数，称其为映射F的Lipschitz常数.

定义2.4设Ω为实Hilbert空间H上一非空闭凸集，记为Ω⊂H，给定其中一点u⊂H，如果存在z⊂Ω，使得

则称z是u在Ω上的投影，记为z=PΩ［u］.

2.2半定规划问题的转化

考虑半定规划原问题（2.l）的对偶问题（2.2），去掉其松弛矩阵S可写为

从而（2.3）式的最优性条件可表示为

定义有限维欧式空间Rn×n×Rn上的内积和范数，若令u=（X，y）T，则对任意的，定义内积为〈u1，u2〉=，则由此内积诱导出的范数为‖u‖=，用vec（X）表示矩阵X的列依次按列的顺序尾首连接成的n2维向量.

由矩阵论［11］理论易知，任一个对称矩阵A可以写成A=WTDW的形式，其中W为正交矩阵，D为对角阵.定义，而且分别为对角阵D+，D-的对角元素，则

并且P1［A］=WTD+W表示对称矩阵A在上的正交投影，P2［A］=WTD-W表示对称矩阵A在上的正交投影［12］.在凸紧集上的投影具有一个重要的性质［13］：对于任意的v∈Rn×n×Rm和w∈Ω，有

下面给出的引理和定理建立了互补松弛条件和投影方程之间的等价关系.

引理2.1 A∈Sn，B∈，如果〈A，B〉=0当且仅当AB=0.

定理2.1［14］X0∈，S0∈，若X0S0=0当且仅当

证必要性：令X=X0-S0，对于∀XT=X，则在如下的不等式

得到

由引理2.1可知

通过不等式（2.9）和（2.10），得到E（X0）=0.

充分性：由E（X0）=0，得到X0=.由

成立，从而得到

记

于是由引理2.1得到X0S0=0.

定理2.2设u=（X，y）T∈Ω，那么最优性条件（2.7）与如下的投影方程等价

证最优性条件（2.3）等价于

于是SDP的最优性条件等价于式（2.15）的变分不等式问题.所以求解半定规划最优解的问题，可以通过求解变分不等式（2.15）实现，能够解决该变分不等式的方法，都可能同时获得SDP的最优解.而在本文中提出邻近外梯度算法解决该问题.

3　半定规划的邻近外梯度算法

有许多求解变分不等式的算法和研究成果，如投影法［15］、Wiener-Hopf方程法、逐点逼近法等［16-18［19］，通过每次迭代中增加一个投影来克服一般投影算法限制太强的缺点.并且，何炳生教授在2004年提出了一种近似邻近外梯度类型算法［20］.本文针对迭代步骤中不规则闭凸区域上投影计算难的问题，结合近似邻近点算法，外梯度算法以及次梯度半空间投影算法，提出邻近外梯度算法求解半定规划问题，在每次迭代步中定义误差限ε，保证算法具有很好的收敛性.

3.1半定规划的邻近外梯度算法的实现

通过最优性条件（2.15），SDP问题可等价转化为一个定义在有限维欧氏空间中，并在闭凸集Ω=×Rm上的变分不等式问题

其中

由F（u）的定义可知F（u）单调且Lipschitz连续［21，22］.本文结合外梯度算法，构造包含原投影区域的半空间，将投影建立在半空间上，简化投影的求解过程，并对新的邻近点序列作相应限制.下面给出邻近外梯度算法具体的实现过程.

步骤1给定β0=1，ε≥0，0＜u＜v＜1，0＜ρ＜1，0＜γ＜2，u0∈Ω，k=0.

步骤2计算预测点

停，否则转步骤3.

步骤3令rk=，若rk≤v，计算

步骤4构造半空间Hk，

计算在半空间上Hk投影

计算下一个迭代点

步骤5若e（F（uk），βk）=0，计算

否则k=k+1，转步骤1.

3.2数值试验

教学测试稳定性的统计研究中有一类重要问题即教育测试问题（ETP）.为了验证算法的可行性，在Matlab2012中执行该算法，在Intel（R），Pentium（R），Core（TM）i7-3520M CPU，2.9GHz，4.00GB内存，Windows 7操作系统上进行数值实验.在实施算法时，为了与外梯度算法和半定规划软件包SDP packuser内点算法的计算结果进行比较［23-24］，实验参数的设置相同.教育测试问题模型如下.

给定一个对称正定矩阵C，求

其中Diag（y）表示由向量y为对角元素得到的对角矩阵，e表示元素全为1的列向量.Iter表示求解问题过程中算法得到最终结果所需要的迭代次数，CPU-time表示完成计算所需要的时间，单位s，问题规模从n=4到n=180，ε=10-4为停止准则.下表给出了求解SDP问题的迭代次数和CPU计算时间的结果.

表1：数值实验结果比较

表2：数值实验结果比较

表1和2分别给出了求解半定规划问题一次计算的迭代次数和CPU计算时间，与解半定规划的内点法相比，本文算法编程容易，单步计算量小，能充分利用原始数据的稀疏性，占用内存小.可以看出，在精度要求相同的情况下，本文提出的邻近外梯度算法在求解半定规划问题时运行速度比内点算法快得多，迭代次数明显减少，算法运行时间短.与外梯度算法相比，本文算法的迭代次数和运行时间更优.从数值实验结果可以看出，提出的算法对于半定规划问题的求解是可行的.

4　结论

本文通过把求解半定规划问题有效的转化为求解变分不等式问题，把变分不等式的数值解法从欧式空间推广到有限维空间，给出了一个求解半定规划问题的邻近外梯度算法.并在算法中考虑不规则闭凸区域上投影计算难的问题来构造半空间上的投影，在算法中引入特殊的迭代步长因子，增加了迭代点的灵活性，通过数值实验说明该算法是求解半定规划问题的一种可行方法.半定规划与许多优化问题有着紧密的联系，将半定规划和互补问题结合是今后的研究重点.

［1］Henry Wolkowicz，Romesh Saigal，Lieven Vandenbrghe.Handbook of semidefinite programming［M］. Boston：Kluwer Academic Publishers，2000：1-27.

［2］Chen X，Tseng P.Non-interior continuation methods for solving semidefinite complementarity problems［J］.Math.Prog.，2003（9）：624-645.

［3］Harker P T，Pang J S.Finite-dimensional variational inequality and nonlinear complementarity problems：a survey of theory，algorithms and applications［J］.Math.Prog.，1990，48：161-220.

［4］Pang J S，Chan D.Iterative methods for variational and complementarity problems［J］.Math.Prog.，1982，24：284-313.

［5］He B S.A class of projection and contraction methods for monotone varational inequalities［J］.Appl. Math.Opti.，1997，35：69-76.

［6］韩乔明.解半定规划的二次摄动方法［J］.应用数学学报，1999，1：84-90.

［7］关秀翠，刁在筠.二次半定规划问题及其投影收缩算法［J］.高等学校计算数学学报，2002，2：97-108.

［8］徐凤敏，刘三阳.半定规划的一种新算法［J］.西安电子科技大学学报，2000，6：773-777.

［9］韩继业，修乃华，戚厚铎.非线性互补理论与算法［M］.上海：上海科学技术出版社，2006.

［10］Noor M A.Extragradient methods for pseudomonotone variational inequalities［J］.J.Opti.The. Appli.，2003，117（3），475-488.

［11］Bhatia R.Matrix analysis［M］.Germany：Springer，1985.

［12］杨国平，刘三阳.半定规划问题的一种新的预测校正算法［J］.应用数学，2005，18：5-9.

［13］Luenberger D G.Introduction to linear and nonlinear programming［M］.USA：Addison-Wesley，1973.

［14］Han Qiaoming.Projection and contraction methods for semidefinite programming［J］.Appl.Math. Comput.，1998，95：275-289.

［15］郑莲.解拟变分不等式的超平面投影算法［J］.系统科学与数学，2013，5：579-584.

［16］张丽丽，李兴斯.箱式约束变分不等式的一类新光滑gap函数［J］.应用数学和力学，2013，1：27-37.

［17］刘英.Banach空间中关于变分不等式组与严格伪压缩映射的粘滞逼近法［J］.应用数学学报，2013，2：324-336.

［18］乌力吉，陈国庆.箱约束变分不等式的一个简单光滑价值函数和阻尼牛顿法［J］.应用数学和力学，2005，26（8）：988-996.

［19］He B S，Liao L Z.Improvements of some projection methods for monotone nonlinear variational inequalities［J］.Optim.Theory Appl.，2002，112（1），111-128.

［20］He B S，Yang Z H，Yuan X M.An approximate proximal-extragradient type method for monotone variational inequalities［J］.J.Math.Anal.Appl.，2004，300：362-374.

［21］Censor Y，Gibali A，Reich S.The subgradient extra-gradient method for solving variational inequalities in hilbert space［J］.J.Optim.Theory Appl.，2011，148：318-335.

［22］Abdellah Bnouhachem，Muhammad Aslam Noor.Mohalfaoui and Sheng zhaohan.An approximate proximal point algorithm for nonlinear complementtarity problems［J］.Hacettepe J.Math.Stat.，2012，41（1），103-117.

［23］Toh K C，Todd M J，T¨ut¨unc¨u R H.SDPT3-a Matlab software package for semidefinite programming，version 2.1［J］.Opti.Meth.Soft.，1999，11（2）：1-30.

［24］李蕊.半定规划的外梯度法研究［D］.西安：西安电子科技大学硕士学位论文，2010.

A PROXIMAL EXTRAGRADIENT ALGORITHM FOR SEMIDEFINITE PROGRAMMING

YU Dong-mei，GAO Lei-fu，ZHAO Shi-jie，YANG Pei
（Research Institute of Optim.and Decision，Liaoning Technical University，Fuxin 123000，China）

In this paper，we present a proximal extragradient algorithm for solving semidefinite programming probem.The optimality conditions for semidefinite programming are transformed into variational inequality problem.Under the premise of variational inequality monotone and Lipschitz continuous，half-space contains the original projection area is constructed，generated points sequence is approaching the solution of variational inequalities，such that the projection of the solution process is simplified.The algorithm is applied to educational evaluation questions，and numerical results show that the proposed method is feasible for solving large-scale semidefinite programming problem.

semidefinite programming（SDP）；variational inequalities；subgradient half space；extragradient algorithm

MR（2010）主题分类号：90C22O221.2

A

0255-7797（2016）05-1047-09

2014-04-02接收日期：2014-07-02

教育部高校博士学科科研基金联合资助项目（20132121110009）；国家自然科学基金天元基金（11326224）；辽宁省教育厅基金资助项目（L2012105）.

于冬梅（1986-），女，满族，辽宁岫岩，博士，主要研究方向：半定规划理论与应用，锥规划.

2010 MR Subject Classification：90C22