数学建模与数学实验 无约束最优化 后勤工程学院数学教硏室
后勤工程学院数学教研室 无约束最优化 数学建模与数学实验
实验目的 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 XE 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 XE 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 从而得到下降方向