解线性不等式约束凸规划问题的势下降内点算法

张 涛,陈 忠,吕一兵

(长江大学信息与数学学院,湖北 荆州 434023)

解线性不等式约束凸规划问题的势下降内点算法

张 涛,陈 忠,吕一兵

(长江大学信息与数学学院,湖北 荆州 434023)

提出了一种解线性不等式约束凸规划问题的势下降算法,并在一定的假设条件下,证明了该算法的收敛性,最后通过数值实验验证了该算法的有效性.

凸规划;不等式约束;势下降内点算法

0 引 言

自1984年Karmarkar[1]提出了解线性规划问题的内点算法以来,一些学者运用线性规划内点算法的思路来求解凸规划问题的Karmarkar内点算法[2-4],但这些方法绝大部分是求解等式约束凸规划问题.为此,基于Karmarkar内点算法,本研究提出了一种求解线性不等式约束凸规划问题的势下降内点算法,并证明了该算法的收敛性,最后通过具体算例验证了该算法的有效性.

1 不等式约束的凸规划模型

其中,A∈Am×n,b∈Rm,f(x)为开凸集D⊂Rn上的凸函数,f(x)二阶连续可微.

根据K-T条件,问题(1)的最优性充要条件可表示为,

注意到,对z∈ Ω0有 g(z)＞0,z*满足条件(2)当且仅当z*∈ Ω0且g(z*)=0,故定义如下势函数,

其中,γ＞n+m是任意给定的常数.由算术—几何平均不等式易知,

在迭代点zk处,取如下方程组的解作为搜索方向,

所有 z∈ Ω0,映射L(z)的Jacobi矩阵为,

其中,X,Y,U和V分别是以向量x,y,u及v的元素为对角元的对角矩阵,▽2f(x)表示f的二阶偏导组成的Hessian矩阵.对所有z∈ Ω0,线性方程组(4)都有唯一解,并可证明该唯一解是势函数φ(z)在点z处的一个下降方向.

2 基本定理

引理1[5]如果C和D是正定对角阵,B是半正定的,则 C+DB是非奇异的.

定理1 对所有的z∈ Ω0,矩阵 ▽L(z)都是非奇异的.

证 对任意 z∈ Ω0,只需证明齐次方程组▽L(z)d=0的解d=(d1,d2)T为零.

由,

由于f(x)为开凸集D⊂Rn上的凸函数且二次连续可导,则 ▽2f(x)半正定,▽2f(x)+ATV-1YA是半正定的,由引理1,U+X(▽2f(x)+ATV-1YA)是非奇异的,故 d1=0,从而d2=0即 d=0,所以矩阵 ▽L(z)是非奇异的.

定理1表明,对所有的z∈ Ω0,方程组(4)都有唯一解.

下面证明,该唯一解还是势函数φ(z)在点z处的一个下降方向.

证 势函数φ(z)在Ω0上是连续可微的,它在点z∈ Ω0处的梯度为,

其中,

且满足,

则,

由算术 —几何平均不等式有,

即(5)式成立.

3 势下降内点算法

3.1 势下降内点算法步骤

势下降内点算法的具体步骤为:

2)求解方程组 ▽L(zk)d+L(zk)=σkβ(zk)en+m,得搜索方向 dk;

3)令mk是满足下面条件的最小非负整数,zk+βρmdk∈ Ω0,φ(zk+βρmdk)- φ(zk) ≤-α βρm(1-σk)(γ-n-m),令 zk+1=zk+βρmdk;

4)检验zk+1是否满足预先给定的终止条件:如果满足,停止迭代;否则取 σk+1∈[0,],令 k=k+1并转2).

3.2 算法收敛性分析

定理3 由势下降内点算法产生的迭代点列{zk}有界,其每个聚点都满足条件(2)且对函数g(z)有

证 易知迭代点列{zk}有界.设z*是{zk}的任一聚点,则z*∈ Ω且存在{zk}的一个子序列,设为{zk:k∈K},使得zk→z*(k∈K),K为所有迭代数列.为证明z*满足条件(2),只需证明g(z*)=0.

采用反证法,假设g(z*)＞0,则存在δ＞0使得对所有充分大的k∈K,均有g(zk)≥δ.因φ(zk)≤φ(z0),集合{L(zk):k∈ K}包含在(分量全大于零的向量集合)的一个紧子集[6]内,所以z*∈Ω0且 L(z*)＞0.由定理 1,▽L(zk)(k ∈ K)及▽L(z*)非奇异,则{▽L(zk)-1:k∈K)}收敛到▽L(z*)-1.因0 ≤σk≤＜1,不失一般性,设{σk:k∈K}收敛于σ*∈[0,1),则{dk:k∈K}收敛于满足 ▽L(z*)d*+L(z*)=σ*β(z*)en+m的向量d*,由定理2及 α∈(0,1)得,

这与(6)矛盾,从而必有,

综上,迭代点列{zk}有界且其任意聚点满足g()=0,则对该迭代点列必有极限成立,则算法是全局收敛的.

定理3表明,g(zk)≤ε可作为算法的终止准则,其中,ε＞0是预先给定的容许误差.

4 算 例

算例2

根据势下降内点算法,利用c#进行编程(计算机配置:CPU,AMD 2.80 GHz;RAM,3.25 GB),算法中的参数设置为,所得数值计算结果如表1所示.

表1 数值算例结果

5 结 语

本研究提出一种求解线性不等式约束凸规划问题的势下降内点算法,并在一定的假设条件下,证明了该算法的全局收敛性,最后,通过数值计算验证了该算法的有效性.

[1] Karmarkar N.A new polynomial-time algorithm for linear programming[C]//STOC'84 Proceedings of the Sixteenth annual ACM Symposium on Theory of Computing.New York:ACM Press,1984:302-311.

[2] Ye Y,Tse E.An extention of Karmarkar's projective algorithm for convex quadratic programming[J].Mathematical Programming,1989,44(1-3):157-179.

[3] Monteiro RDC,Adler I.Interior path following primal-dual algorithms[J].Mathematical Programming,1989,44(1-3):27-66.

[4] Goldfarb D,Liu S.AnPrimal interior point algorithm for convex quadratic programming[J].Mathematical Programming,1991,49(1-3):325-340.

[5] 梁昔明.求解凸二次规划问题的势下降内点算法[J].高等学校计算数学学报,2002,24(1):81-86.

[6] Moteiro RDC.A Globally Convergent Primal-dual Interior Point Algorithm for convex programming[J].Mathematical Programming,1994,64(1-3):123-147.

Potential Reduction Interior-point Algorithm for Linear Convex Programming Problem with Inequality Constraints

ZHANG Tao,CHENGZhong,LVYibing
(School of Information andMathematics,Yangtze University,Jingzhou 434023,China)

In this paper,a potential reduction interior-point algorithm for the linear convex programming problem with inequality constraints is presented and the convergence of the algorithm is proved under some assumptions.Experiments with real data verify the effectiveness of the algorithm.

convex programming;inequality constraints;potential reduction interior-point algorithm

O221

A

1004-5422(2013)01-0036-03

2012-12-17.

国家自然科学基金(11201039,61273179)资助项目.

张 涛(1978—),男,博士研究生,讲师,从事复杂系统建模与智能计算研究.