精确罚函数若干性质及算法

李 璞,尚有林

(河南科技大学数学与统计学院,河南洛阳 471003)

0 前言

罚函数法是将有约束的优化问题转化成无约束的优化问题来求解的方法。经典的罚函数理论,是通过添加罚函数项后,研究一系列无约束优化问题,并使惩罚参数趋于无限大来获得原规划的最优解。而精确罚函数理论是通过求解单个无约束优化问题来求原规划的最优解。如文献[1]所述,罚函数法的主要缺点是目标函数的病态性质,这种病态性质是由罚因子的无限增大或减小而引起的[2-3],为了改进罚函数法而提出的各类方法中,精确罚函数方法是一类重要的算法。一般精确罚函数并不光滑[4-5],可以将非光滑的精确罚函数光滑化[6],但罚函数的形式会变的更加复杂,在实际计算中,由于不知道罚参数具体有多大,需要不断的增大,这样就影响了常用的一些有效的算法,如 Newton算法。因此,精确性和可微性是罚函数的关键性问题。文献[8-9]给出了最小精确罚参数的估计。文献[7]也提出了同时具有光滑性和精确性的一类罚函数形式。本文在一种精确罚函数形式下[10],讨论了相关的一些性质定理,根据此罚函数的形式设计了相应的算法,并通过编程给予实现。

1 精确罚函数

解集: X={x∈Rnhi=0,i∈Igj(x)≤0,j∈J},文献[10]提出了如下的罚函数形式: P(x,M)=φ(f(x)-M)+F(x)。其中φ(t)=max2(0,t),F(x)=[hi(x)]2+φ(gj(x)),显然F(x)≥0,所以P(x,M)≥0,F(x)=0的充要条件是hi(x)=0,i∈Igj(x)≤0,j∈J。

于是问题(I)的解x*满足F(x*)=0,并且对于任意的满足F(x)=0的点x都有f(x)≥f(x*)。

考虑新的无约束优化问题:(Ⅱ)minP(x,M),s.t x∈Rn。

2 精确罚函数的若干性质

针对上述精确罚函数的形式,文献[7]与文献[10]分别介绍了若干性质定理如下:

性质1【7】如果x*是问题(I)的最优解且M=f*=f(x*),则x*是罚问题(Ⅱ)的最优解且P(x*,f*)=0。

性质2【7】设x*是问题(I)的最优解,对某个M,是罚问题(Ⅱ)的最优解和问题(I)的可行解,并且P(x*,M)≠0。如果M≤f(x*),那么是问题(I)的最优解。

性质3【10】设X是连通紧集,f(x)是X上的连续函数,令α=f(x),β=f(x),对某个M,是罚问题(Ⅱ)的最优解,则:

上述 3个性质虽然指出了给定的精确罚函数的若干性质,但是并未涉及到罚参数和最优值之间的具体联系,本文在已有文献基础上,给出两个有关罚函数的罚参数与原问题最优解以及罚问题最优解之间关系的性质定理,具体如下:

该定理说明了当罚参数取值大于原问题最优值的时候,罚问题最优解x*M满足P(x*M,M)=0,并且当P(,M)=0时,罚参数的取值一定是大于原问题最优值的。

3 算法

已有文献在给出精确罚函数的形式之后,选择适当的罚参数,将各个变量直接代入罚函数形式中进行计算,验证这样的精确罚函数是确实存在的,但并没有提出有效算法。根据精确罚函数性质以及P(x,M)连续性,若知道f*的近似值,则能通过求解问题(II)得到约束问题(I)的最优解,基于这个思想,本文在已有罚函数形式基础上,设计了相关算法,并通过编程给予实现,在计算上减少直接代入的不便性,提高了效率。具体算法如下:

(1)输入f*的下界初值α0≤f*(α0可根据目标函数与可行域适当选取),取得问题(I)的可行点x0,显然F(x0)=0。令β0=f(x0)为f*的上界初值,即f*≤β0(x0也可以通过求解min F(x)得到)。

(2)令Mk=(1-θ)αk+θβk(θ为参数,取值范围 0＜θ＜0.5,程序中取了θ=0.4),求解min P(x,M)=P(,Mk)=

(4)重复(2)、(3)直到βk-αk≤ε,这时令最优解为x*=k。

定理 1和定理 2给出 f*确定的取值范围,并且 f*下界不宜选取过小,这就可避免产生溢出而导致算法失败。

收敛性定理 上述精确罚函数的算法是收敛的。

由上述算法产生的 αk,βk满足αk≤f*≤βk,并且由于βk-αk→0,所以,上面给出的算法是收敛的。

4 程序说明与计算实例

根据上面给出的算法,用MATLAB编写程序,列出部分主程序如下:

以上程序中涉及到的无约束问题的求解采用的是拟牛顿法。

对上述程序给出算例(以两个变量为例)如下:

其中初始点选取(s,t)=(2,3)。

解 在MATLAB的命令窗口中输入:syms s t。

f=s^2-s*t+t-s+1;g=[——t^2-s^2+6;-s;-t];h=[2*s+3*t-9];[x,minf]=minLP(f, [2 3],g,h,0,0.4,[s t])。

运行结果为:x=1.384 6; 2.076 9。

min f=0.733 7。

可见,用精确罚函数法求得最优点为(s,t)=(1.384 6,2.076 9)。

例2 m in f(s,t)=0.5t2+0.25s2,s.t t+s=1。

这是仅有等式约束的优化问题,初始点取(s,t)=(0,0),运行结果为(s,t)=(0.500 0,0.500 0), min f=0.187 5。因此,也可以用精确罚函数法求解仅含有等式约束的优化问题。

5 结论

在文献[10]的基础上讨论了罚函数的罚参数与原问题最优解以及罚问题最优解之间具体关系,指出精确罚函数P(x,M)的精确性以及f(x*)的取值范围,并且给出了具体罚函数形式下相应的算法,最后通过计算机编写程序给予实现。

[1] 胡毓达.非线性规划[M].北京:高等教育出版社,1990.

[2] 《运筹学》教材编写组.运筹学[M].3版.北京:清华大学出版社,2005.

[3] 陈宝林.最优化理论与算法[M].2版.北京:清华大学出版社,2005.

[4] Han S P,Mngasarian O L.Exact Penalty Functions in Nonlinear Programm ing[J].Math Programming,1979,17:251-269.

[5] ZangwillW I.Non linear Programm ing Via Penalty Function[J].Management Science,1967,13:344-358.

[6] Zenio S A.A Smooth Penalty Function Algorithm for Network Structured Prob lems[J].European Journal of Operational Research,1993,64:258.

[7] 汪寿阳.一种新的罚函数的精确罚定理[J].自然科学进展,2003,13(3):328-329.

[8] Wu Z Y,Bai F S,Yang X Q.An Exact Lowei Order Penalty Function and Its Smoothing in Nonlinear Programming[J].Optim ization,2004,53(1):51-68.

[9] Rubinov A M,Yang X Q.Langrange-type Functions in Corrstrained Non-Convex Optimization[M].Boston,London:Kluwer Academ ic Publishers,2003.

[10] 江维琼.一种新的精确罚函数[J].云南师范大学学报,2006,26(2):9-20.