張 濤,陳 忠,呂一兵

(長江大學(xué)信息與數(shù)學(xué)學(xué)院,湖北 荊州 434023)

解線性不等式約束凸規(guī)劃問題的勢下降內(nèi)點(diǎn)算法

張 濤,陳 忠,呂一兵

(長江大學(xué)信息與數(shù)學(xué)學(xué)院,湖北 荊州 434023)

提出了一種解線性不等式約束凸規(guī)劃問題的勢下降算法,并在一定的假設(shè)條件下,證明了該算法的收斂性,最后通過數(shù)值實(shí)驗(yàn)驗(yàn)證了該算法的有效性.

凸規(guī)劃;不等式約束;勢下降內(nèi)點(diǎn)算法

0 引 言

自1984年Karmarkar[1]提出了解線性規(guī)劃問題的內(nèi)點(diǎn)算法以來,一些學(xué)者運(yùn)用線性規(guī)劃內(nèi)點(diǎn)算法的思路來求解凸規(guī)劃問題的Karmarkar內(nèi)點(diǎn)算法[2-4],但這些方法絕大部分是求解等式約束凸規(guī)劃問題.為此,基于Karmarkar內(nèi)點(diǎn)算法,本研究提出了一種求解線性不等式約束凸規(guī)劃問題的勢下降內(nèi)點(diǎn)算法,并證明了該算法的收斂性,最后通過具體算例驗(yàn)證了該算法的有效性.

1 不等式約束的凸規(guī)劃模型

其中,A∈Am×n,b∈Rm,f(x)為開凸集D?Rn上的凸函數(shù),f(x)二階連續(xù)可微.

根據(jù)K-T條件,問題(1)的最優(yōu)性充要條件可表示為,

注意到,對(duì)z∈ Ω0有 g(z)＞0,z*滿足條件(2)當(dāng)且僅當(dāng)z*∈ Ω0且g(z*)=0,故定義如下勢函數(shù),

其中,γ＞n+m是任意給定的常數(shù).由算術(shù)—幾何平均不等式易知,

在迭代點(diǎn)zk處,取如下方程組的解作為搜索方向,

所有 z∈ Ω0,映射L(z)的Jacobi矩陣為,

其中,X,Y,U和V分別是以向量x,y,u及v的元素為對(duì)角元的對(duì)角矩陣,▽2f(x)表示f的二階偏導(dǎo)組成的Hessian矩陣.對(duì)所有z∈ Ω0,線性方程組(4)都有唯一解,并可證明該唯一解是勢函數(shù)φ(z)在點(diǎn)z處的一個(gè)下降方向.

2 基本定理

引理1[5]如果C和D是正定對(duì)角陣,B是半正定的,則 C+DB是非奇異的.

定理1 對(duì)所有的z∈ Ω0,矩陣 ▽L(z)都是非奇異的.

證 對(duì)任意 z∈ Ω0,只需證明齊次方程組▽L(z)d=0的解d=(d1,d2)T為零.

由,

由于f(x)為開凸集D?Rn上的凸函數(shù)且二次連續(xù)可導(dǎo),則 ▽2f(x)半正定,▽2f(x)+ATV-1YA是半正定的,由引理1,U+X(▽2f(x)+ATV-1YA)是非奇異的,故 d1=0,從而d2=0即 d=0,所以矩陣 ▽L(z)是非奇異的.

定理1表明,對(duì)所有的z∈ Ω0,方程組(4)都有唯一解.

下面證明,該唯一解還是勢函數(shù)φ(z)在點(diǎn)z處的一個(gè)下降方向.

證 勢函數(shù)φ(z)在Ω0上是連續(xù)可微的,它在點(diǎn)z∈ Ω0處的梯度為,

其中,

且滿足,

則,

由算術(shù) —幾何平均不等式有,

即(5)式成立.

3 勢下降內(nèi)點(diǎn)算法

3.1 勢下降內(nèi)點(diǎn)算法步驟

勢下降內(nèi)點(diǎn)算法的具體步驟為:

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

3)令mk是滿足下面條件的最小非負(fù)整數(shù),zk+βρmdk∈ Ω0,φ(zk+βρmdk)- φ(zk) ≤-α βρm(1-σk)(γ-n-m),令 zk+1=zk+βρmdk;

4)檢驗(yàn)zk+1是否滿足預(yù)先給定的終止條件:如果滿足,停止迭代;否則取 σk+1∈[0,],令 k=k+1并轉(zhuǎn)2).

3.2 算法收斂性分析

定理3 由勢下降內(nèi)點(diǎn)算法產(chǎn)生的迭代點(diǎn)列{zk}有界,其每個(gè)聚點(diǎn)都滿足條件(2)且對(duì)函數(shù)g(z)有

證 易知迭代點(diǎn)列{zk}有界.設(shè)z*是{zk}的任一聚點(diǎn),則z*∈ Ω且存在{zk}的一個(gè)子序列,設(shè)為{zk:k∈K},使得zk→z*(k∈K),K為所有迭代數(shù)列.為證明z*滿足條件(2),只需證明g(z*)=0.

采用反證法,假設(shè)g(z*)＞0,則存在δ＞0使得對(duì)所有充分大的k∈K,均有g(shù)(zk)≥δ.因φ(zk)≤φ(z0),集合{L(zk):k∈ K}包含在(分量全大于零的向量集合)的一個(gè)緊子集[6]內(nèi),所以z*∈Ω0且 L(z*)＞0.由定理 1,▽L(zk)(k ∈ K)及▽L(z*)非奇異,則{▽L(zk)-1:k∈K)}收斂到▽L(z*)-1.因0 ≤σk≤＜1,不失一般性,設(shè){σk:k∈K}收斂于σ*∈[0,1),則{dk:k∈K}收斂于滿足 ▽L(z*)d*+L(z*)=σ*β(z*)en+m的向量d*,由定理2及 α∈(0,1)得,

這與(6)矛盾,從而必有,

綜上,迭代點(diǎn)列{zk}有界且其任意聚點(diǎn)滿足g()=0,則對(duì)該迭代點(diǎn)列必有極限成立,則算法是全局收斂的.

定理3表明,g(zk)≤ε可作為算法的終止準(zhǔn)則,其中,ε＞0是預(yù)先給定的容許誤差.

4 算 例

算例2

根據(jù)勢下降內(nèi)點(diǎn)算法,利用c#進(jìn)行編程(計(jì)算機(jī)配置:CPU,AMD 2.80 GHz;RAM,3.25 GB),算法中的參數(shù)設(shè)置為,所得數(shù)值計(jì)算結(jié)果如表1所示.

表1 數(shù)值算例結(jié)果

5 結(jié) 語

本研究提出一種求解線性不等式約束凸規(guī)劃問題的勢下降內(nèi)點(diǎn)算法,并在一定的假設(shè)條件下,證明了該算法的全局收斂性,最后,通過數(shù)值計(jì)算驗(yàn)證了該算法的有效性.

[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] 梁昔明.求解凸二次規(guī)劃問題的勢下降內(nèi)點(diǎn)算法[J].高等學(xué)校計(jì)算數(shù)學(xué)學(xué)報(bào),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.

國家自然科學(xué)基金(11201039,61273179)資助項(xiàng)目.

張 濤(1978—),男,博士研究生,講師,從事復(fù)雜系統(tǒng)建模與智能計(jì)算研究.