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

《有约束条件的极值问题.ppt》由会员分享，可在线阅读，更多相关《有约束条件的极值问题.ppt（13页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第五节 有约束条件的极值问题 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)寻优难以实现，要构造

2、更好的函数。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,)称为惩罚函数，为惩罚因子。一般地，有约束问

3、题模型为（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,)的H

4、esse矩阵越难求,无约束问题的求解越困难,甚至无法求解,所以开始不能太大。解：令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

5、)必须是可行点。此法对靠近可行域边界的点施加越来越大的惩罚,对边界上的点施加无穷大的惩罚,以阻止迭代点穿越边界,从而将迭代点封在可行域内。内点法仅适用于不等式约束: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)必须为可行点。例 用内点法求解解：令 并令 所求最优解为 习题v1.用最速下降法解2.用变尺度法求二次函数 的极小值点,其中v3.用单纯型法求 的极小值设初始点为v4.用外点法解5.用内点法解题4