二次半定规划一个原始对偶路径跟踪算法
黎健玲;王培培
【摘 要】A primal-dual path-following algorithm bad on H..K..M direction for quadratic mi-definite programming problems(QSDP)is propod.Firstly,the system of linear equa-tions yielding the H..K..M direction are derived,and the existence and uniqueness of the arch direction are shown;Secondly,the algorithm is described in detail.We show that the it-erates generated by the algorithm can fall into some neighborhood of the central path under some mild conditions.Finally,a preliminary numerical experiment is performed for the algo-rithm by using Matlab (R2011b)mathematical software,and the numerical results show that the propod algorithm is effective.%本文提出求解二次半定规划的一个基于 H..K..M方向的原始对偶路径跟踪算法.文中首先导出确定H..K..M方向的线性方程组，并证明该搜索方向的存在唯一性；然后给出算法的具体步骤，并证明算法产生的迭代点列落在中心路径的某个邻域内.最后采用 Matlab(R2011b)数学软件编程对算法进行数值试验.数值结果表明算法是有效的.
【期刊名称】《广西科学》
【年(卷),期】2016(023)005
【总页数】8页(P396-403)
【关键词】二次半定规划;原始对偶;算法;路径跟踪;中心路径
【作 者】黎健玲;王培培
【作者单位】广西大学数学与信息科学学院，广西南宁 530004;广西大学数学与信息科学学院，广西南宁 530004
【正文语种】中 文
【中图分类】C934
【研究意义】(线性)半定规划(简记SDP)既是定义在半正定矩阵锥上的规划,也是线性规划、凸二次规划、二阶锥规划等的一种推广,在控制论、组合优化等诸多领域有着广泛的应
用.而二次半定规划是半定规划的拓展，它在最优控制、证券、金融风险分析等领域中都有着广泛的应用.【前人研究进展】原始对偶内点算法是求解半定规划的有效方法[1-10].由于确定搜索方向的方法不同,因此导出多种形式的原始对偶内点法.目前常用的搜索方向有以下3种:(i)AHO搜索方向[2];(ii)H..K..M搜索方向[3-5];(iii)Nesterov-Todd搜索方向(简称NT方向)[6-7].基于SDP的原始对偶内点算法,文献[11]提出一个求解二次半定规划的势减少(potential reduction)算法;文献[12]结合Dikin型方向和牛顿中心步提出一个求解二次半定规划的预估校正算法;文献[13]提出一个求解二次半定规划的投影收缩算法;文献[14]将基于NT方向的原始对偶内点算法推广到二次半定规划.【本研究切入点】本文考虑如下二次半定规划问题(简记为QSDP):
s.t. Ai·X =bi,i=1,…,m;
四级估分器XT=X0,
利用凸规划问题的Wolfe对偶理论,可得QSDP(0.1)的对偶规划(简记为DSDP)为
s.t.,
X0,Z0.
FP={X|Ai·X =bi,X0},
易知DSDP(1.1)也是一个凸二次半定规划问题.对于任意的(X,y,Z)∈FD,若X∈FP,则对偶间隙为
f(X)-D(X,y)=svec(X)THTHsvec(X)-aT,
假设：
(A1)设矩阵组{Ai,i=1,…,m}线性无关.
沈阳新东方
(A2)Slater条件成立,即存在X≻0,Z≻0和y∈Rm使得X∈FP,(X,y,Z)∈FD.
由(1.2)式以及文献[13]的定理3.5知,在假设(A2)下,X∈FP是QSDP(0.1)的最优解当且仅当存在y∈Rm,Z∈Sn,使得
XZ=0.
点对(X,Z)如果满足X∈FP,(X,y,Z)∈FD且
XZ=σμI,
Ai·X =bi,i=1,…,m,
XZ=σμI.
Ai·ΔX=0,i=1,…,m,
ΔXZ+XΔZ=σμI-XZ-ΔXΔZ.
ΔXZ+XΔZ=σμI-XZ.
Ai·ΔX=0,i=1,…,m,
GT=(svec(A1),…,svec(Am)),
引理2.1 假设(A1)和(A2)成立,,则矩阵FHTH+E可逆.
证明 已知
rank(FHTH+E)=rank(F-1(FHTH+E))=rank(HTH+F-1E),
引理2.2 假设(A1)和(A2)成立,,
证明 因为
(FHTH+E)-1F=(F-1(FHTH+E))-1=
引理2.3 假设(A1)和(A2)成立,X∈F°P,(X,y,Z)∈F°D,则线性方程组(2.7)有唯一解.
证明 首先证明线性方程组(2.7)的系数矩阵可逆,即证明方程组(2.7)对应的齐次线性方程组
B=
(G(FHTH+E)-1FGT)Δy=0.
将Δy=0代入(2.11)式,即得
svec(ΔX)=(FHTH+E)-1FGTΔy=0,
reicat
svec(ΔZ)=-F-1E svec(ΔX)=0,
引理2.4 假设(A1)和(A2)成立,设X∈F°P,(X,y,Z)∈F°D,(ΔX,Δy,ΔZ)是线性方程组(2.7)对于某个给定的矩阵W(∈Rn×n)的解,则以下结论成立:
①ΔZ·ΔX≥0;
②X·ΔZ+Z·ΔX=Tr(W);
③如果,则
我朋友的辣妈
(X+αΔX)·(Z+αΔZ)=(1-α+α σ)(X·
证明 ①根据(2.5b)式和(2.5a)式,并结合矩阵内积的性质可得
②由(2.5c)式知,则由矩阵迹的性质有
③根据矩阵内积的线性性质以及矩阵迹的性质,再结合结论(2)得到
(X+αΔX)·(Z+αΔZ)=X·Z+α σμn-αTr(XZ)+α2(ΔX·ΔZ)=X·Z+α σμn-
H..K..M搜索方向(ΔX,Δy,ΔZ)可以通过求解线性方程组(2.7)得到,而方程组(2.7)包含m+n(n+
1)个线性方程,通过块高斯消去法将其化简为如下的方程
翻译员
(G(FHTH+E)-1FGT)Δy=-G(FHTH+E)-1rc,
GTΔy-(F-1E+HTH)svec(ΔX)=-F-1rc,
Esvec(ΔX)+Fsvec(ΔZ)=rc,
MΔy=h.
M=G(F-1(FHTH+E))-1GT=G(HTH+F-1E)-1GT=G(HTH+(X-1⊗sZ))-1GT,
于是可利用Cholesky分解求解线性方程组(3.2)得到Δy,进而由(3.1b)式和(3.1c)式可求出
ΔX=smat((FHTH+E)-1(FGTΔy+rc)),
ΔZ=smat(HTHsvec(ΔX)-GTΔy).
这一节我们将给出基于H..K..M方向的短步原始对偶路径跟踪算法.
长辈英文算法的具体步骤如下:
算法A
步骤0(初始步) 选取X0∈F°P,(X0,y0,Z0)∈F°D,参数η>1,令.
当μk>2-ημ0时执行以下步骤:
步骤1 记X=Xk,(y,Z)=(yk,Zk),μ=μk.
步骤2 选择合适参数σ=σk∈[0,1],令.
步骤3 求解线性方程组(2.7)得到H..K..M搜索方向(ΔX,Δy,ΔZ).
步骤4 选择α≥0,使得
步骤5 令,
注:算法A是一个短步路径跟踪算法[5,8],对所有的k≥0,取,其中δ>0是一个常量.
有道翻译算法产生的迭代点列将落在中心路径的如下邻域内:
NF(γ)≡{(X,y,Z)|X∈F°P,(X,y,Z)∈F°D,‖‖F≤γμ}={(X,y,Z)|X∈F°P,(X,y,Z)∈,
引理4.1 假设(A1)和(A2)成立,设X∈F°P,(X,y,Z)∈F°D,(ΔX,ΔZ,Δy)是线性方程组(2.7)的解,其中,对任意的α≥0,令
(X(α),Z(α),y(α))≡(X,Z,y)+α(ΔX,ΔZ,Δy),
μ(α)≡(X(α)· Z(α))/n,检场
证明 假设α≥0是给定的.根据引理2.4(3)有
X(α)·Z(α)=(X+αΔX)·(Z+αΔZ)=(1-α+α σ)(X·Z)+α2(ΔX·ΔZ),
Z(α)X(α)-μ(α)I=(1-α)(ZX-μI)+
接下来的引理给出scaling方向,
‖A+B‖F≤‖A‖F+‖B‖F,‖AB‖F≤‖A‖F‖B‖F,‖AB‖F≤‖A‖F‖B‖.
引理4.2 假设(A1)和(A2)成立,设X∈F°P,(X,y,Z)∈F°D,使得‖‖≤υγ,对任意的γ∈[0,1),υ>0成立.(ΔX,Δy,ΔZ)是线性方程组(2.7)对于某个确定矩阵W的解.记δx=υ‖‖F,δz=υ‖‖F,则下列结论成立:
证明 根据(2.5c)式得
‖W‖F≥‖‖
以下定理说明本文的短步路径跟踪算法产生的迭代点列将落在中心路径邻域NF(γ)内.
定理4.1 假设(A1)和(A2)成立,设常数,并且满足
证明 因为
‖‖‖‖‖‖.
因为‖‖F≤γμ,根据引理4.2取,则有
‖
‖‖F‖.
‖
‖‖F≤‖‖F.
根据(4.10)式,(4.9)式和定理4.1的条件,得
‖,
‖‖,
雀巢咖啡伴侣采用Matlab(R2011b)数学软件编程对算法A进行数值试验,程序运行环境为Windows7(64bite),Intel(R)Core(TM)i3-2330M ***********,RAM:4G.
考虑如下两类测试问题:(1)随机二次半定规划问题;矩阵Ai,Hj,C都是随机生成的对阵矩阵,初始点(X,y,Z)的选取需在FP,FD内.记该类测试问题为RP.(2)最近相关矩阵Nearest correlation matrix(简记为NCM)问题[16-17].
s.t. diag(X)=e,
NCM问题具有广泛的应用,例如在市场营销以及经济学方面.但是遗憾的是,由于缺乏数据等信息，不能得到一个完整的矩阵G,即矩阵G的一些元素是未知的.于是通过求解NCM问题得到一个有效的、且与G最近的相关矩阵.在数值测试中,取G是随机矩阵且G∶=(1-α)B+α E[18],
其中α∈(0,1),E是元素属于[-1,1]的随机对称阵,B是具有指定特征值的测试矩阵,在NCM问题的数值测试中取n=10,20,30.
>animaltube
