一個求解不等式約束優化問題的非內點型可行QP-free算法

陳 玉,陳內萍,段 玉

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

本文考慮求解如下不等式約束優化問題

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

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

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

1 算法描述

我們首先給出該算法的有關記號，然后給出該算法.為此，我們給出如下假設：

(H1) 集合F是有界的.

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

性質1[6](i)對每個x∈F，關于λ的二次函數‖▽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)乘子函數λ(x)在F上是連續可微的.

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

非內點型可行QP-free算法步驟：

參數及有關初始值：β∈(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. 令Ak(ε)=A(xk,ε)和Vk(ε)=V(xk,Hk;Ak(ε)).如果▽gAk(ε)(xk)非滿秩或‖Vk(ε)-1‖>M，那么令ε=σε和M=σM，進入步2.

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

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

步驟6. 線搜索：

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

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

從算法中，不難得到如下關系:

(1)

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

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

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

2 全局收斂性分析

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

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

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

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

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

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

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

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

3 收斂速度分析

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

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

(ii)在(x*,λ*)處嚴格互補條件成立，即λ*-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.

下面的引理見文獻[13]中的定理2.3和2.7.

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

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

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

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

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

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

該引理的證明見文獻[9]中引理4.3,4.4.

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

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

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

參考文獻：

[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.