后勤工程学院：《数学建模与数学实验》课程教学资源（PPT课件讲稿）第5讲 无约束优化

数学建模与数学实验 无约束最优化 后勤工程学院数学教硏室

后勤工程学院数学教研室 无约束最优化 数学建模与数学实验

实验目的 1、了解无约束最优化基本算法。 2、掌握用数学软件包求解无约束最优化问题 实验内容 1、无约柬优化基本思想及基本算法。 2、 MATLAB优化工具箱简介 3、用 MATLAB求解无约束优化问题。 4、实验作业

实验目的 实验内容 2、掌握用数学软件包求解无约束最优化问题。 1、了解无约束最优化基本算法。 1、无约束优化基本思想及基本算法。 4、实验作业。 3、用MATLAB求解无约束优化问题。 2、MATLAB优化工具箱简介

无约束最优化问题 求解无约束最优化问题的的基本思想 无约束最优化回题的基本算法 返回

无约束最优化问题 求解无约束最优化问题的的基本思想 *无约束最优化问题的基本算法 返回

求解无约束最优化问题的基本思想 标准形式: min f(r) X∈E 其中f:E"→E max f(r)= min[-f(r) X∈En X∈E 求解的基本思想(以二元函数为例) f(x, x2) x2f(X0)>f(X1)>f(x2) 连续可微 XI

f (X ) n XE min 其中 1 f : E E n → 标准形式： 求解无约束最优化问题的基本思想 求解的基本思想 ( 以二元函数为例 ) 1 x 2 x ( ) 1 2 f x x 0 1 x 2 x 0 5 3 1 X0 X1 X2 ( ) X0 f ( ) X1  f ( ) X2  f 连 续 可 微 f (X ) n XE max = min [ f (X )] n X E − 

f(x1x)=一x-x2 f(x1x)=x+2 f(x1x2)=x2-x2

唯一极小 全局极小) f(xx2)=2x2-2xx2+x2-3x1+x2 O f=0.298 0.298 多局部极小 了(x1x2)=2 1.05x4+ x

多局部极小 f = 0.298 f = 0 f = 0.298 唯一极小 (全局极小) 1 2 2 1 2 2 2 1 2 1 f (x x ) = 2x − 2x x + x −3x + x

最优点(11) 搜索过程mnf(xx2)=10(x2-x)2+(1-x)初始点(-11) 1400 100 0.790583.39 0.530.23260 0.180.00150 0.09-0.030.98 0.370 11 1 0.47 0.590.330.20 0.800.630.05 0.950.900.003 0990 99 lE-4 0.99909981E-5 0.99970.99981E-8 返回

搜索过程 2 1 2 2 1 2 2 1 min f ( x x ) =100 ( x − x ) + (1− x ) 最优点 (1 1) 初始点 ( -1 1) 1 x 2 x f -1 1 4.00 -0.79 0.58 3.39 -0.53 0.23 2.60 -0.18 0.00 1.50 0.09 -0.03 0.98 0.37 0.11 0.47 0.59 0.33 0.20 0.80 0.63 0.05 0.95 0.90 0.003 0.99 0.99 1E - 4 0.999 0.998 1E - 5 0.9997 0.9998 1E - 8 返回

无约束优化问题的基本算法 1.最速下降法(共轭梯度法)算法步骤: (1)给定初始点X∈En,允许误差E>0,令k=0 2)计算v(x) (3)检验是否满足收敛性的判别准则: v(x)≤, 若满足,则停止迭代,得点X≈X,否则进行(4) (4)令 ,从ⅹ出发,沿进行一维搜索, 即求使得:mk+S)=八(x4+k) (5)令Xk=Xk+Sk,k=k+1返回(2) 最速下降法是一种最基本的算法,它在最优化方法中占有重要地位.最 速下降法的优点是工作量小,存储变量较少,初始点要求不高;缺点是收敛 慢,最速下降法适用于寻优过程的前期迭代或作为间插步骤,当接近极值 点时,宜选用别种收敛快的算法

⑴ 给定初始点 n X  E 0 ，允许误差  0 ,令 k=0； ⑵ 计算 ( ) k f X ； ⑶ 检验是否满足收敛性的判别准则：  ( )   k f X ， 若满足，则停止迭代，得点 k X  X * ，否则进行⑷； ⑷ 令 ( ) k k S = −f X ，从 k X 出发，沿 k S 进行一维搜索， 即求k 使得： ( ) ( ) k k k k k f X S f X  S  + = + 0 min ； ⑸ 令 k k k k X = X +  S +1 ，k=k+1 返回⑵. 无约束优化问题的基本算法 最速下降法是一种最基本的算法，它在最优化方法中占有重要地位.最 速下降法的优点是工作量小，存储变量较少,初始点要求不高；缺点是收敛 慢，最速下降法适用于寻优过程的前期迭代或作为间插步骤，当接近极值 点时，宜选用别种收敛快的算法. 1．最速下降法（共轭梯度法）算法步骤：

2.牛顿法算法步骤 (1)选定初始点X∈En,给定允许误差E>0,令k=0 )求v(x)(/(x),检验:若|(x)<,则 停止迭代,X≈Ⅹ.否则,转向(3); (3)令Sk=2/(x)V/(x)(牛顿方向) (4)XA=Xk+Sk,k=k+1,转回(2) 如果f是对称正定矩阵A的二次函数,则用牛顿法经过一次迭代 就可达到最优点,如不是二次函数,则牛顿法不能一步达到极值点, 但由于这种函数在极值点附近和二次函数很近似,因此牛顿法的收 敛速度还是很快的. 牛顿法的收敛速度虽然较快,但要求 Hessian矩阵要可逆 要计算二阶导数和逆矩阵,就加大了计算机计算量和存储量

2．牛顿法算法步骤： (1) 选定初始点 n X  E 0 ，给定允许误差  0 ，令 k=0； (2) 求 ( ) k f X ,( ( )) 1 2 −  k f X ,检验：若  ( )   k f X ,则 停止迭代, k X  X * .否则, 转向(3)； (3) 令 ( ) ( ) k k k S = −  f X f X 2 −1 [ ] （牛顿方向）； (4) k k k X = X + S +1 , k = k +1 ,转回(2). 如果f是对称正定矩阵A的二次函数，则用牛顿法经过一次迭代 就可达到最优点,如不是二次函数，则牛顿法不能一步达到极值点， 但由于这种函数在极值点附近和二次函数很近似,因此牛顿法的收 敛速度还是很快的. 牛顿法的收敛速度虽然较快，但要求Hessian矩阵要可逆， 要计算二阶导数和逆矩阵，就加大了计算机计算量和存储量

3.拟牛顿法 为克服牛顿法的缺点,同时保持较快收敛速度的优点,利用第k步 和第k+1步得到的X,X+,Vf(X),Vf(Xk),构造一个正定 矩阵Gk近似代替V2f(Xk),或用Hk近似代替(V2f(Xk),将 牛顿方向改为: Gk+l sk+l=-Vf(X k+1 k+1 hk+l vf( kt) 从而得到下降方向

3．拟牛顿法 为克服牛顿法的缺点，同时保持较快收敛速度的优点，利用第 k 步 和第 k+1 步得到的 k X ， k+1 X ， ( ) k f X ， ( ) +1  k f X ，构造一个正定 矩阵 k +1 G 近似代替 ( ) 2 k  f X ,或用 k+1 H 近似代替 2 1 ( ( ) ) −  k f X ，将 牛顿方向改为： k +1 G k+1 S =- ( ) +1  k f X ， k+1 S =- k+1 H ( ) +1  k f X 从而得到下降方向