《一五有约束条件的极值问题》由会员分享，可在线阅读，更多相关《一五有约束条件的极值问题（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) 最优解一定在可行域中。
2、 但对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。 无约
3、束的极小点接近约束问题的极小点 。 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*。 可以证明,如果数列收敛,必收敛于约束问题的
4、极小点 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.0
5、00005)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) 必须为可行点。 例 用内点法求解 解：令 并令 所求最优解为 习题 v1.用最速下降法解 2.用变尺度法求二次函数 的极小值点, 其中 v3.用单纯型法求 的极小值设初始点为 v4.用外点法解 5.用内点法解题4
