一類光滑罰算法的全局收斂性

梁卓華(山東理工大學 數學與統計學院，山東 淄博 255049)

1 光滑罰函數

考慮約束優化問題

s.t.fi(x)≤0,0≤i≤m,

其中，fi:Rn→R(0≤i≤m)是連續可微函數， Ω0={x∈Rn|fi(x)≤0,1≤i≤m}≠φ．

不失一般性，假設

(1)

否則，可用ef0(x)來代替f0(x)．

非線性規劃問題在科學管理，工程和經濟管理等方面有廣泛的應用．罰函數方法是解決非線性規劃問題的重要方法，其主要思想是對目標函數增加懲罰項，將原問題轉化為無約束優化問題．對于罰函數的研究已有很多文章[1-5]．

問題(CP)的l1精確罰函數為

(2)

文獻[6]中給出的光滑罰算法是基于如下形式

(3)

式中：r是一個參數；θ(·)是一類光滑凸函數．隨后Wang等[8]將式(3) 中的參數β進行了改進，給出了如下光滑罰函數

(4)

本文將式(4)進行推廣，給出如下形式的光滑函數

(5)

這里的f(x)=(f1(x),f2(x),…,fm(x))，σ函數是滿足第2節中,A1,A2,A3的函數，然后由罰函數(5)給出了一類光滑罰算法，并證明了一個攝動定理，由此攝動定理推出了罰算法的全局收斂性．

2 罰算法及全局收斂性

設函數σ∶Rm→R滿足如下假設：

(A1) 對?ε>0，?ηε>0，使得

(A2) 對ck→+(k→)，存在εk→0+(k→)，有

(A3) 存在常數σ0使得

σ(u)≥σ0,?u∈Rm．

容易驗證函數σ(u)=||u+||α(α≥1)及σ(u)=||u+||2-||u+||均滿足假設(A1)～(A3)．

命題1若假設(A2)成立，則存在σ1，對?u≤0，都有σ(u)≤σ1．

證明由假設(A2)知，一定存在δ>0與k0使得

證畢．

對于問題(CP)給出新的罰函數

其中f(x)=(f1(x),f2(x),…,fm(x))．進一步給出基于L(x,β,r)給出一種罰算法并證明了一個攝動定理，由此攝動定理得到該算法的全局收斂性．

算法1

step0β0=1,r0=1,ω0=1，令k:=0．

step1 判定

(6)

否則，求非精確解xk滿足

(7)

注 由(1)與假設(A3)，對?β>0及r>0有

因此不論式(6)是否成立，滿足式(7)式的全局非精確解總是存在的，即算法總是可行的，文獻[8]給出的算法，在某些情況下是不可行的，這體現了本文結果的運用具有更加廣泛性．

下面研究算法的收斂性．

對于ε≥0，定義問題(CP)的松弛可行集

Ωε={x∈Rn|fi(x)≤ε,1≤i≤m}．

定義問題(CP)的攝動函數為

則問題(CP)的最優值為

設

Fε={x∈Rn|f0(x)≤θf0(ε)+ε}．

引理1算法產生的序列{rk}收斂于0．

=

(8)

對于任意充分大的k≥k0，由假設(A1)有

≥

引理2?ε>0，存在K，當k>K時都有Sk(ε)?Ωε．

證明用反證法．否則?ε0>0及無窮子列K?N={1,2,…}使得?k∈K，存在zk∈Sk(ε0)，zk?Ωε0因此存在無窮子列K0?K，使得?k∈K0與指標i0∈{1,2,…,m}，有

fi0(zk)>ε0

(9)

則由引理1及式(9)知，對充分大的k，||f+(xk)||>ε0≥rk．

由式(9)與假設(A1)，當k充分大時，有

(10)

又由step2知βk→+(k→)，因此(10)式右端趨向于正無窮．

(11)

(11)式左端是有界的，這樣(10)式與(11)式矛盾．證畢．

定理1(攝動定理) 設{xk}是由算法所產生的點列，則有

(12)

再取δk>0且δk→0(k→)．根據下確界的定義，對每個k，存在使得

(13)

同時由于

因此得

(14)

另一方面，對?ε>0，由引理2的證明過程知，對所有充分大的k，有

xk∈Ωε

(15)

從而，對?ε>0，由假設及(13)-(14)，有

θf0(ε)≤f0(xk)≤

令k→，于上式兩端取極限，由式(12)即得．證畢．

由此定理可以得到下面推論．

推論1設{xk}是由算法所產生的點列，則它的每一個聚點都是問題(CP)的最優解．

證明由引理2，對充分大的k有

xk∈Ωε

(16)

設x*是序列{xk}的一個聚點，由fi(0≤i≤m)的連續性及式(16)即知x*∈Ωε．再據ε>0的任意性知，x*∈Ω0．

由攝動定理，有

證畢．

3 結束語

罰函數與精確罰函數在多個領域應用很廣泛，并且起著非常重要的作用，多年來，很多學者對罰函數進行了深入研究．本文給出了一種光滑罰算法并證明了其全局收斂性．這為求解約束規劃問題，提供了一個新的方法．

[1]LIU J, TEO K L, WANG X. An exact penalty function-based differential search algorithm for constrained global optimization[J]. Soft computing, 2016, 20(4): 1 305-1 313.

[2] ZHOU J, LOVE P E D, TEO K L. An exact penalty function method for optimising QAP for mulation in facility layout problem[J]. International Journal of Production Research, 2016: 55(10):2 913-2 929.

[3]GONZAGA C C,CASTILLO R A. A nonlinear programming algorithm based on non-coercive penalty functions[J].Mathematical Programming, 2003, 96(1):87-101．

[4] BOLAND N L, EBERHARD A C. On the augmented lagrangian dual for integer programming[J] . Mathematical Programming , 2015,150(2):491-509．

[5] BURACHIK R S, IUSEM A N, MELO J G. The exact penalty map for nonsmooth and nonconvex optimization[J]．Optimization,2015,64(4), 717-738．

[6] WANG C Y. Global convergence and finite termination of a class of smooth penalty function algorithms[J]. Optimization Methods & Software, 2013, 28(1):1-25．

[7] WU Z Y, BAI F S, LEE H W J. Quadratic smoothing approximation to exact penalty function in global optimazation [J]. Journal of Industrial & Management Optimization, 2005, 1(4):533-547．

[8] WANG C, MA C, ZHOU J. A new class of exact penalty functions and penalty algorithms[J]. Journal of Global Optimization, 2014, 58(1):51-73．

[9] WU Z Y, BAI F S,YANG X Q. An exact lower order penalty function and its smoothing in nonlinear programming[J]. Optimization, 2004, 53(1):51-68．

[10] BEN-TAL A, TEBOULLE M. A smoothing technique for nondifferentiable optimization problems[M]. Optimization Springer Berlin Heidelberg, 1989:1-11．

[11] HUANG X X, YANG X Q. A unified augmented lagrangian approach to duality and exact penalization[J]. Mathematics of Operations Research, 2003, 28(3):533-552．