云南师范大学：《数学建模与数学实验》课程PPT教学讲义_第4讲 非线性规划（费培之）

(数学模型 第四节 非线性规划模型的解 二次插值法 最速下降法 罚函数法

第四节 非线性规划模型的解 • 二次插值法 • 最速下降法 • 罚函数法

(数学模型 非线性规划模型的一般形式: 、无约束模型:min{f(X)X∈R" 二、有约束模型: min f(X) stg;(X)≥0,讠=1,2,,m h,(X)=0,j=1,2,…,p 「若X∈S∩N(X") f(x)≤f(x则X称为局部最优解,或局部解 若X∈ 则X'称为整体最优解,或最优解或解

非线性规划模型的一般形式： 一、无约束模型: min{ ( )| } n f X X  R 二、有约束模型： min f (X) s.t gi (X)  0,i = 1,2,  ,m hj (X) = 0, j = 1,2,  , p f (X )  f (X)  ( ),  若 X  S  N X 若 X  S, 则 称为局部最优解，  X 或局部解； 则 称为整体最优解，  X 或最优解或解

(数学模型 无约束模型的解 沿某直线方向求目标函数的极小值点,称为一维搜索。 高维问题可通过一系列的一维搜索,求出其近似最优解。 讨论顺序: min{f(x)x∈R}一维搜索 沿某些方向作一维搜索 min{f(X)|X∈R"} 为无约束问题 min f(X) stg1(X)≥0,讠=1,2,…,m h(X)=0,=1,2,…,P

一、无约束模型的解 min{ ( )| } n f X X  R 沿某直线方向求目标函数的极小值点，称为一维搜索。 高维问题可通过一系列的一维搜索，求出其近似最优解。 min{ f (x)| x  R} 一维搜索 沿某些方向作一维搜索 min f (X) s.t gi (X)  0,i = 1,2,  ,m hj (X) = 0, j = 1,2,  , p 化为无约束问题 讨论顺序：

(数学模型 1.一维搜索(二次插值法) 单峰函数f(x),x∈[u,b g lf(r) 设x1∫(x2)S∫(x3) 过三点作抛物线:g(x)=+x+ 或f(x1)≥∫(x2)0 即抛物线的开口向上

1. 一维搜索 （二次插值法） 单峰函数 f (x), x [a,b] 设 x1  x2  x3 , 满足 ( ) ( ) ( ) 1 2 x3 f x  f x  f 或 ( ) ( ) ( ) 1 2 x3 f x  f x  f 1 x 2 x 3 x f (x) g(x) x 过三点作抛物线： 2 0 1 2 g(x) = a + a x + a x 有 ( ) ( ) 1 2 g x1 = a0 + a1 x1 + a2 x1 = f x ( ) ( ) 2 2 g x2 = a0 + a1 x2 + a2 x2 = f x ( ) ( ) 3 2 g x3 = a0 + a1 x3 + a2 x3 = f x ,  xi  xj 0 1 1 1 2 3 3 2 2 2 2 1 1   x x x x x x 故方程组有唯一解，且 a2  0 即抛物线的开口向上

(数学模型 令 g(x)=a1+2a2x=0 得极小值点 2a2 再从x1,X2,x3,x中选出满足前面不等式的三点, 重复前面的过程,直到满足终止条件: f(x)-g(x)61,|x3-x1KE2 ≈X 注:迭代时,若出现退化情形x=x2 可取x 2 继续迭代 #

令 g (x) = a1 + 2a2 x = 0 得极小值点 2 1 2a a x = − 再从 x1 , x2 , x3 , x 中选出满足前面不等式的三点 ， 重复前面的过程，直到满足终止条件： 1 3 1 2 | f (x) − g(x)|  , | x − x |  则 x  x  注：迭代时，若出现退化情形 x = x2 , 2 x1 x2 x + 可取 = 继续迭代。 #

(数学模型 2.最速下降法 设f(X)可微,给定初始点X1,e>0 Vf(X 每次沿使f下降得最快的负梯度 方向D=-Vf(X)搜索,直到满足 终止条件为止。 D=-VS(X 第k次迭代 第1步求新点设已得Xk 令Dk=-V(Xk)求λ1使 f(Xx+n D)=min f(Xk+AD) ≥0 得新点 k+1 X+2D kk 注意:不是步长(因D不是单位向量), 且非负(否则,不是下降得最快的方向)

2. 最速下降法 • X f (X) D= －f (X) 第1步 求新点 设f(X) 可微，给定初始点X1 ,>0, 每次沿使f 下降得最快的负梯度 方向 D=－f (X)搜索，直到满足 终止条件为止。 第k次迭代 令 ( ) k Xk D = −f 求 k 使 ( ) min ( ) 0 k k k Xk Dk f X  D f   + = +  注意： k不是步长（因Dk不是单位向量）， 且非负（否则，不是下降得最快的方向）。 得新点 Xk+1 = Xk + kDk 设已得Xk

(数学模型 第2步验证终止条件 若Vf(X+)<E,则X"=Xk+m 否则,将X+1作为新的出发点,Dk+=-Vf(xXk 作为新的迭代方向,进行下一次迭代 Vf(X)是∫(X)在X处的最大变化率。 有结论: )k⊥D k+1 因为_df(X+D)df(X+AD)D d (xk+ NDu) 了(Xxk+)·Dk=-D,D k+1 可见,搜索路线呈之字形

第2步 验证终止条件 ( ) , , 1 +1   Xk+  X = Xk 若 f  则 f (Xk+1 ) 是 f (X)在 Xk+1 处的最大变化率。 否则，将Xk+1作为新的出发点， 作为新的迭代方向，进行下一次迭代。 ( ) k+1 = − Xk+1 D f 有结论： Dk ⊥ Dk+1 因为 k d d f Xk Dk   ( +  ) Xk Dk = f  + ( )1 Dk Dk = −  +1 k k k k k k D d X D d f X D     + + = ( ) ( ) 0 = 可见，搜索路线呈之字形

(数学模型 ●X 该法的优点是:不论维数多高,每次迭代只沿 个方向搜索。 缺点是:收敛速度“前快后慢” 当目标函数等值线 “较圆”时,则收敛得较快; “较扁”时,则收敛得较慢 实际中,前面阶段可用最速下降法, 后面阶段用旋转方向法

该法的优点是：不论维数多高，每次迭代只沿 一个方向搜索。 “较圆”时，则收敛得较快； “较扁”时，则收敛得较慢。 当目标函数等值线  • X • 实际中，前面阶段可用最速下降法， 后面阶段用旋转方向法。 缺点是：收敛速度“前快后慢

(数学模型 例求解minf(X)=x2+2x2-2x1x2-2x2 解V(X)=(2x1-2x2,4x2-2x-2) E=0.3,初始点X1=(0,0) 第1步 因 V(X1)=(0,2),Vf(X1)=2E 所以令D1=-Vf(X1)=(0,2) 则有 X1+AD1=(0,24) f(X1+D1)=f(0,24)=8x2-4 现求使mnf(X1+D)=mn{872-44}的41 20 九20 由=16-4=0,得λ 得新点:X2=X1+41D12=(00+1(02y=0,3y

例 求解 1 2 2 22 2 min f (X) = x1 + 2x − 2x x − 2x 解 T f (X) (2x 2x , 4x 2x 2)  = 1 − 2 2 − 1 − 0.3 (0,0) , 1 T ＝ ， 初始点 X = 因 ( ) (0, 2) , 1 T f X = − f (X1 ) = 2 <  所以令 ( ) (0,2) , 1 1 T D = −f X = T X D (0, 2 ) 则有 1 +  1 =  ( ) (0, 2 ) f X1 + D1 = f  8 4 2 = − 1 2 0 1 1 0 min (  ) min{8 4}    现求使 + = − 的   f X D 由 f  = 16 − 4 = 0, 41 得 1＝ 得新点： X2 = X1 + 1 D1 T) 21 = ( 0 , T T (0,2) 41 = (0,0) + 第 1 步

(数学模型 第2步 因V(X2)=(-1,0),Vf(X2)=1+6 迭代: D2=-Vf(X2)=(1,0 沿D2方向搜索,得2= 2 37 经5次迭代后得解点X641<E vf(X6)=(-,0),Vf(X6)= 故得近似最优解:X 37 48 搜索过程见P32表1l。 而本题的精确最优解是:(1,1)

第2步 因 ( ) ( 1,0) , 2 T f X = − f (X2 ) = 1 <  令 T D f (X ) (1,0) 2 = − 2 = 沿 D2 方向搜索，得 2 1 2 = 迭代： 经5次迭代后得解点 ) , 8 7 , 4 3 ( 6 T X = ,0) , 4 1 ( ) ( 6 T f X = − 4 1 ( ) f X6 =   T X ) 8 7 , 4 3 = ( 故得近似最优解：  而本题的精确最优解是： T (1, 1) 搜索过程见P.32表1.11