一個求解不等式約束優(yōu)化問題的非內(nèi)點(diǎn)型可行QP-free算法

陳 玉,陳內(nèi)萍,段 玉

(湖南商學(xué)院信息學(xué)院,中國 長沙 410205)

本文考慮求解如下不等式約束優(yōu)化問題

且假定f:Rn→R,gi:Rn→Rn都是連續(xù)可微的.為表述方便，記F={x∈Rn:gi(x)≤0,i∈I}.

對上述問題(P)的求解，目前存在很多方法，如SQP、可行方向法、罰函數(shù)法、內(nèi)點(diǎn)法等，其中QP-free方法是求解上述問題的有效方法之一[2-12].該算法的思想最早見于文獻(xiàn)[1],而由Panier,Tits和Herskovits[4]首次提出．在Panier-Tits-Herskovits算法的每一個迭代，僅需求解2個不同的線性方程組和一個線性最小二乘問題．Gao,He和Wu[5]也提出一個求解問題(P)的可行QP-free 算法，不同于Panier,Tits和Herskovits算法，在不要求穩(wěn)定點(diǎn)數(shù)目有限的條件下，他們的算法產(chǎn)生的點(diǎn)列的聚點(diǎn)都是問題(P)的KKT點(diǎn).但是，在收斂性的證明中，他們必須假定乘子序列有界.Qi基于互補(bǔ)函數(shù)和KKT條件，提出了一個求解問題(P)的可行QP-free 算法[8]，他們在無嚴(yán)格互補(bǔ)條件下證明了迭代矩陣的一致非奇異性和近似乘子序列的有界性.Yang, Li和Qi[9]通過引進(jìn)一個工作集的概念，提出了一個新的求解問題(P) 的可行QP-free 算法,該算法僅考慮工作集內(nèi)的約束，這使得計算量大大減少；在該算法的每一個迭代，僅需求解4個系數(shù)相同的線性方程組.但是，對于上述幾種可行QP-free 算法，迭代點(diǎn)必須是F的內(nèi)點(diǎn).

本文在文獻(xiàn)[9]的基礎(chǔ)上提出了一個求解問題(P)的非內(nèi)點(diǎn)型修正可行QP-free算法，該算法不要求迭代點(diǎn)必須是F的內(nèi)點(diǎn)；在算法的每一個迭代，只需求解4個系數(shù)相同的線性方程組；在合適的條件下，該算法具有全局收斂性和局部一步超線性收斂速度.

1 算法描述

我們首先給出該算法的有關(guān)記號，然后給出該算法.為此，我們給出如下假設(shè)：

(H1) 集合F是有界的.

(H2) 對任意x∈F，向量組{▽gi(x),i∈I0(x)}是線性無關(guān)的，這里I0(x)={i|gi(x)=0}.

性質(zhì)1[6](i)對每個x∈F，關(guān)于λ的二次函數(shù)‖▽xL(x,λ)‖2+‖G(x)λ‖2存在唯一的極小者λ(x)=-M-1▽g(x)T▽f(x)，這里

L(x,λ)=f(x)+λTg(x)G(x)=diag(gi(x)),M(x)=▽g(x)T▽g(x)+G(x)2.

(ii)乘子函數(shù)λ(x)在F上是連續(xù)可微的.

(iii)如果(x*,λ*)∈Rn×Rm是(P)的KKT點(diǎn)對，那么λ(x*)=λ*.

非內(nèi)點(diǎn)型可行QP-free算法步驟：

參數(shù)及有關(guān)初始值：β∈(0,1),μ∈(0,0.5),ν>2,τ∈(2,3),?∈(0,1),M0>0,σ∈(0,1),σ1>1,x′∈F，H1是一個對稱正定矩陣，ε0>0,k=1.

步驟1. 令ε=εk-1和M=Mk-1.

步驟2. 令A(yù)k(ε)=A(xk,ε)和Vk(ε)=V(xk,Hk;Ak(ε)).如果▽gAk(ε)(xk)非滿秩或‖Vk(ε)-1‖>M，那么令ε=σε和M=σM，進(jìn)入步2.

步驟3. 令εk=ε和Mk=M,Ak=Ak(εk),Vk=V(xk,Hk;Ak).

步驟4. 搜索方向的計算：

步驟6. 線搜索：

計算序列{1，β，β2，…，}中滿足如下不等式組的第1個數(shù)tk：

注從H2和Hk的對稱正定性易知，V(xk,Hk,Ak)是非奇異的.

從算法中，不難得到如下關(guān)系:

(1)

引理1(i)如果dk1=0，那么xk是問題P的KKT點(diǎn).

(ii)如果dk1≠0,那么▽f(xk)Tdk<0,▽gi(xk)Tdk<0,?i∈I0(xk).

(ii)該結(jié)論的證明類似于文獻(xiàn)[9]中引理2.2的證明.

2 全局收斂性分析

在本節(jié)，我們將分析該算法的全局收斂性.首先假設(shè)：

(H3)對所有的k和d∈Rn，存在正常數(shù)C1和C2滿足C1‖d‖2≤dTHkd≤C2‖d‖2.

引理2[9]序列{(dk0,zk0)},(dk1,zk1),(dk2,zk2)都是有界的.

引理3[9]對所有的k,存在正常數(shù)κ滿足‖dk-dk1‖≤κ‖dk1‖ν.

引理4假設(shè)x*是該算法所生成序列xk的一個聚點(diǎn)，{xk}K0→x*，如果{▽f(xk)Tdk1}K0→0，那么x*是問題P的KKT點(diǎn)且{zk0}K0存在一子列收斂到對應(yīng)于x*的唯一乘子向量λ*.

又g(x*)≤0，因此x*是問題P的KKT點(diǎn).由乘子向量的唯一性知：{zk0}K1收斂到對應(yīng)于x*.的唯一乘子向量λ*.

類似于文獻(xiàn)[9]中的定理3.1的證明，我們可得如下全局收斂性定理.

定理1如果(x*,λ*)是該算法所生成序列(xk,zk0)的一個聚點(diǎn)，那么(x*,λ*)是問題P的KKT點(diǎn).

3 收斂速度分析

本節(jié)我們將分析該算法的收斂速度.假定(x*,λ*)是該算法所生成序列(xk,zk0)的一個聚點(diǎn)，那么從全局收斂性定理知，(x*,λ*)是問題P的KKT點(diǎn).為討論方便，我們記I0=I0(x*).為此，我們需做如下假設(shè)：

(H4)(i)函數(shù)f(x),gi(x)都是二次連續(xù)可微的.

(ii)在(x*,λ*)處嚴(yán)格互補(bǔ)條件成立，即λ*-g(x*)>0.

引理5假定(H1),(H3)，(H4)，(H5)成立，則整個序列{xk}收斂到x*，即xk→x*,k→∞.

證從(2.1)和引理2.1可知

f(xk+1)≤f(xk)+μtk▽f(xk)Tdk≤f(xk)-μ?tkdk1THkdk1.

考慮到(H1)和(H3)，可得到tk‖dk1‖→0.因此利用引理3可得，tk‖dk‖→0.

下面的引理見文獻(xiàn)[13]中的定理2.3和2.7.

類似于文獻(xiàn)[9]中的推論4.1,我們可得如下引理.

引理7假定(H1),(H2),(H3)，(H5)成立，則對充分大的k,有Ak=I0成立.而且有如下關(guān)系成立：

(i)dk0→0,dk1→0,dk→0(k→∞)

(ii)zk0→λ*,zk1→λ*,zk→λ*(k→∞)

(iii)如果還有(H4)成立，則對充分大的k，有φk=-gI0(xk).

為得到該算法的超線性收斂性，一個關(guān)鍵性要求是在解的附近單位步長能達(dá)到.為此，下面的假設(shè)是必要的.

該引理的證明見文獻(xiàn)[9]中引理4.3,4.4.

類似于文獻(xiàn)[9]中引理3.5的證明，我們可得到如下引理.

引理9假定(H1)～(H5)成立，則當(dāng)k充分大時，步長tk≡1.

基于上述一系列引理，我們可得如下定理

參考文獻(xiàn)：

[1] HERSKOVITS J. A two-stage feasible direction algorithm for nonlinear constrained optimization[J].Math Prog, 1986,36(1):19-38.

[2] PANIER E R, TITS A L. A supperlinearly convergent feasible method for the solution of inequaality constrained optimization problems[J].SIAM Contr Opti, 1987,25(7):934-950.

[3] WIEST E J, POLAK E. A generalized quadratic programming based phase I-phase II method for inequality constrained optimization[J].Appl Math Opti, 1992,26(2):223-252.

[4] PANIER E R, TITS A L, HERSKOVITS J N. A QP-free globally convergent,locally superlinearly convergent algorithm for inequality constrained optimization[J]. SIAM J Contr Opti, 1988,26(5):788-811.

[5] GAO Z Y, HE G P, WU F. Sequential syestems of linear equations with general constrains[J].J Opti Theo Appl, 1997,27(1):24-33.

[6] LUCIDI S. New results on a continuously differentiable penalty function [J]. SIAM J Opti, 1992,2(4):558-574.

[7] Q L Q, YANG Y F. Globaally and supearliearly QP-free algorithm for nonlinear constrained optimization[J].J Opti Theo Appl, 2002,113(2):297-323.

[8] QI H D, QI Q L. Anew QP-free,globallyconvergent, locally superlinearly convergent algorithm for inequality constrained optimization[J].SIAM J Opti, 2000,11(2):113-132.

[9] YANG Y F, LI D H, QI L. A feasible sequential linear equation method for inequality constrained optimization [J].SIAM J Opti, 2002,13(6):1222-1224.

[10] FACCHINEI F, LAZZARI C. Local feasible QP-free algorithms for the constrained minimization of SC1 functions[J]. J Opti Theo Appl, 2003,119(3):281-316.

[11] FACCHINEI F, LUCIDI S. Quadratically and superlinearly convergent algorithms for the solution of inequality constrained minimization problems[J].J Opti Theo Appl, 1995,85(3):256-289.

[12] ZHU ZH B. An interior point type QP-free algorithms with superlinearly convergent for inequality constrained. optimization[J].Appl Math Mod, 2007,31(6):1201-1212.

[13] FACCHINEI F, FISCHER A, KANZOW C. On the accurate identification of active constraints[J]. SIAM J Opti, 1999,9(1):14-32.