有约束条件的极值问题.ppt

第五节 有约束条件的极值问题,Min f(x) hi(x)=0 i=1,2,.,m gj(x)0 j=1,2,.,l,对于有约束条件问题采取制约函数法： 可将有约束条件的问题转化为一系列无约束极值问题。 常用的制约函数有两类； 一为惩罚函数，二为障碍函数。 对应于两种函数有外点法和内点法。,外点法 以例来说明外点法基本思路： Min f（x）x12x22 x1x220 该问题的可行域是直线,构造出这样的函数，对可行点不加“惩罚”，对非可行点给以正无穷大的“惩罚”，即 当x1x22时 F(X)x12x22 当x1x22时 F(X),求得无约束条件的F(x) 最优解一定在可行域中。 但对F(x)寻优难以实现，要构造更好的函数。,F(X,)=f(x)+ (h(x)2= x12+x22+(x1+x2-2)2 其中取一很大的正数。 当点x在可行域时, F(X,)= x12+x22 当点x不在可行域时, 即 x1x22时, 使 F(X,)取很大值 (因为很大),而且这个点距可行域越远,F的值就越大。 求解minF(X, ) 问题,迭代点虽然不是可行点,但随着迭代过程进行,迭代点必然向可行域靠近,最后逐步趋向可行域内的最优点。 在迭代过程中令+, 最优点一定在可行域中。 现求无约束问题F(x,)的最优解。,解得： 当很大时, 即令+, 得最优解 x1=1, x2=1。 无约束的极小点接近约束问题的极小点 。 F(x,)称为惩罚函数， 为惩罚因子。,一般地，有约束问题模型为 （1）Min f(x) hi(x)=0 i=1,2,.,m 可用如下形式惩罚函数,（2）Min f(x) gj(x)0 j=1,2,.,l 其惩罚函数可为 F(X,)=f(x)+(x),（3）Min f(x) hi(x)=0 i=1,2,.,m gj(x)0 j=1,2,.,l 其惩罚函数可为 F(X,)=f(x)+(x) 其中,例： 用外点法求,在实际算法中,把取为一个逐步趋向正无穷大的数列k,并对K = 0,1,2,.求解,得极小点数列Xk*。可以证明,如果数列收敛,必收敛于约束问题的极小点X*。惩罚因子(和放大系数)的初始值不能取太大,一般地，取 = 1.0(取10.0)。因越大,无约束目标函数F(X,)的Hesse矩阵越难求,无约束问题的求解越困难,甚至无法求解,所以开始不能太大。,解：令F(X,)=1/3(x1+1)3+x2+(x1-1)2(x1-1)+x22(x2) 则 当xD F(X,)=1/3(x1+1)3 + x2 F(X,)=1/3(x1+1)3 + x2+ (x1-1)2+x22 令：,解得,取1=0.001,=10为初始值,然后289,分别取0.01,0.1,1,10,100,1000,10000,100000得X*=(0.9999,-0.000005)T 本题最优解为X*=(1，0)T,最优目标函数值f(X*)=8/3。,内点法 内点法的迭代点都在可行域内，初始点X(0)必须是可行点。此法对靠近可行域边界的点施加越来越大的惩罚,对边界上的点施加无穷大的惩罚,以阻止迭代点穿越边界,从而将迭代点封在可行域内。内点法仅适用于不等式约束: Min f(x) gj(x)0 j=1,2,.,l 构造函数： F(X,)= f(x)+(x) 其中,(x)叫屏障函数; 0仍叫惩罚函数因子; (x)叫惩罚项。 从D的内点X(0)出发,对Min F(X,)(0)迭代,F(X,)的值逐渐下降,所得的解或近似解只可能是D的内点。 若逐次选取120, k0,求出Min F(X,k)的最优解X(k)也逐步逼近原问题的最优解X*。 1范围可选150,可取0.1或0.01等,初始点X(0)必须为可行点。 例 用内点法求解,解：令