汪 燕 张明望
(三峡大学理学院,湖北宜昌 443002)
本文根据原始-对偶内点算法的思想,基于Zhang M W 提出的一个新核函数[1],对凸二次规划设计了新的大步校正原始-对偶内点算法.考虑下面的凸二次规划及其对偶问题:
其中,x,c,s∈Rn,b,y∈Rm,Q∈Sn+,A∈Rm×n且rank(A)=m.
如果(x,y,s)是(P)和(D)的可行解,由对偶理论知,(x,y,s)是(P)和(D)的最优解的充要条件是
其中,xs=(x1s1,x2s2,…,xnsn)T,第3 个方程称为(P)和(D)的互补性条件.
根据原始-对偶内点算法的基本思想,用参数方程xs=μe(μ>0)代替方程组(1)中的第3个方程,即得如下方程组:
不失一般性,假设问题(P)和(D)满足内点条件(IPC),即存在内点(x0,y0,s0),满足
这时,对任意的μ>0,方程组(2)都有唯一解,记为(x(μ),y(μ),s(μ)).集合{(x(μ),y(μ),s(μ))}形成了一个同伦路径,称之为(P)和(D)的中心路径.若μ→0,则中心路径的极限值存在,且满足互补性条件,故此极限值即为(P)和(D)的最优解.
将牛顿法运用到方程组(2),得方程组
则方程组(4)的解(Δx,Δy,Δz)取作算法的迭代方向.
为了便于算法的分析,对任意的(x,s)>0,μ>0,定义:
因此,方程组(4)等价于方程组
本文考虑的障碍函数Ψ(v)是开区间(0,+∞)上光滑的严格凸函数,且当v=e时取得最小值0,因此
现在用-▽Ψ(v)替换(6)中的第3个方程的右半部分,得方程组
由于A 的秩为m 且满足(IPC),所以对任意μ>0,方程组(10)都有唯一解(dx,Δy,ds).再由(5),从而得到算法新的迭代方向(Δx,Δy,Δs).
若(x,y,s)≠(x(μ),y(μ),s(μ)),则(Δx,Δy,Δs)≠(0,0,0).迭代点(x,y,s)沿牛顿方向取步长α,有
又因为Q 是半正定对称矩阵,所以有
这与线性规划中(dx)Tds=(ds)Tdx=0不同,这正是本文新算法与线性规划相应算法及其分析的主要不同之处.
现在具体描述凸二次规划的原始-对偶内点算法:
Step1:输入参数τ>0,精度参数ε>0,以及一个固定的障碍校正参数θ(0<θ<1),选一组严格初始可行解(x0,y0,s0),使得Ψ(x0,s0,μ0)≤τ(这里μ0=(x)0Ts0/n),令x:=x0,y:=y0,s:=s0,μ:=μ0.
Step2:如果nμ<ε,停止.此时的(x,y,s)便是ε-最优解,否则修改μ=(1-θ)μ,转Step3.
Step3:Ψ(v)≤τ,返回Step2,否则进入Step4.
本文引用文献[1]中的核函数
以下关于核函数的性质证明均类似于文献[1].
设在内迭代过程中,当前点(x,s)经过一次内迭代之后,得到新的迭代点(x+,s+),其中
根据引理2.1,显然有f(α)≤f1(α),f(0)=f1(0)=0.
对f1(α)关于α求导可得
定义f(α):=Ψ(v+)-Ψ(v)和
于是
对f1(α)关于α求二阶导数可得
为方便讨论,记δ:=δ(v),vmin:=min{vi},i=1,…,n.
证明 根据δ(v)的定义,可得‖dx+ds‖=2δ,所以有‖dx‖≤2δ和‖ds‖≤2δ,由此可得
由于φ″(t)在(0,+∞)上单调递减,可得
所以
同理
根据式(15),可得
证毕.
引理3.1.2 如果α满足不等式
引理3.1.5(文献[3]中引理12) 若h(t)是一个二阶可微函数且满足h(0)=0,h′(0)<0,如果h(t)在t*>0处取得最小值,且h″(t)在[0,t*]上单调递增,则h″(t)≤h′(0)t/2,t∈[0,t*].
为讨论方便,记s=ρ(2δ),由ρ的定义,则有-φ′(s)=4δ.由核函数的一阶导数和二阶导数可得
所以
注意到0≤s≤1,则有
于是,有
从引理3.1.6,可得
由于式(20)的右边不等式关于δ是单调递减的,利用引理2.3,可得
其中,这里的第二个不等式用到Ψ0≥Ψ≥τ≥1.
3.2 迭代复杂性分析
为了估计大步校正内点算法总的迭代复杂性,需要定量计算出算法在μ 修正以后,需要迭代多少步满足Ψ(v)≤τ.记μ 修正后Ψ(v)的值为Ψ0,此后的序列值记为Ψk,k=1,2,…,K.K 表示在一次外迭代中内迭代的总数目,则有
引理3.2.1(文献[3]中的引理14) 设t0,t1,…,tk是一列正实数,满足
引理3.2.2 设K 表示在一次外迭代之后内迭代的总数目,则有
证明 根据式(21),可得
证毕.
[1] Zhang M W.A Large-update Interior-point Algorithm for Convex Quadratic Semi-definite Optimization Based on a New Kernel Function[J].Acta Mathematica Sinica,English Series,2012,28(11):2313-2328.
[2] Bai Y Q,El Ghami M,Roos C.A Comparative Study of Kernel Functions for Primal-dual Interior-point Algorithms in Linear Optimization[J].SIAM Journal on Optimization,2004,15(1):101-128.
[3] Peng J,Roos C,Terlaky T.Self-regular Functions and New Search Directions for Linear and Semidefinite Optimization[J].Mathematical Programming,2002,93:129-171.