《最优化设计》PPT课件.ppt

最优化设计 无约束优化方法 1 第四章无约束优化方法 4 1概述4 2最速下降法4 3牛顿型方法4 4共轭方向及共轭方向法4 5共轭梯度法4 6变尺度法4 7坐标轮换法4 8鲍威尔法4 9单形替换法 最优化设计 无约束优化方法 2 4 1概述 无约束优化方法只考虑搜索的适行性 结合罚函数法 也可解约束优化问题 目前 成熟可靠的优化算法中 无约束优化方法占多数 总体上无约束优化方法的有效性及实用性都优于约束优化方法 无约束优化方法可分为两大类 1 不求导数的直接法 主要有随机方法和直接搜索方法 2 求导数的间接法 按所求导数的最高阶数又可分为一阶方法和二阶方法 二阶方法很少采用 图4 1为无约束极小化算法的粗框图 在 1 4中已给出了优化算法的一般搜索迭代公式xk 1 xk xk 1 15 xk 1 xk kdk 1 16 注意 在搜索迭代中 由于一维搜索需增加大量计算 因此 并不是所有优化方法都采用一维搜索 最优化设计 无约束优化方法 3 4 2最速下降法 1 最速下降法以负梯度方向作为搜索方向并作一维搜索 因此又称为 梯度法 属于求导数的间接法 它的基本思想早在1847年就已提出 尽管它本身不再被认为是一种有效的方法 但它是许多优化方法尤其是二次收敛方法的基础 各点的梯度一般各不相同 因此 最速下降方向 仅对某一点附近而言 它具有局部性质 如图4 2所示 当作一维搜索时 搜索方向是与目标函数等值线相切的 而切点的梯度方向是与等值线正交的 因此 相邻两次搜索方向相互垂直 搜索路径呈严重的 之 字形 特别是目标函数接近二次型时更为明显 可以利用梯度矢量在极值点为零这一重要性质设立收敛准则 f x 最优化设计 无约束优化方法 4 4 2最速下降法 2 或 数值微分数值微分在优化中是一个非常重要的问题 对优化结果影响较大 具体作法是用代替 其中 f f f0式中 f0 f x0 是计算偏导数那点x0处的目标函数值 f f x f x1 x2 xi xi xn 是其它变量保持不变 xi变化为xi xi时的目标函数值 xi 0 001 ui li ui和li分别为变量xi的估计上限和下限 最优化设计 无约束优化方法 5 4 2最速下降法 3 例4 1 图4 3 求f x1 x2 x12 25x22的极小点 取初始点x0 22 T 则f x0 104 f x0 4100 T沿负梯度即 4 100 T方向进行一维搜索 有x1 x0 0 f x0 22 T 0 4100 T 2 4 02 100 0 T在x1点f x1 x2 2 4 0 2 25 2 100 0 2 0 令 0 0 有2 2 4 0 4 50 2 100 0 100 16 32 0 10000 500000 0 500032 0 10016 0 0 0 020030718得到第一次迭代的结果 x1 2 4 02 100 0 T 1 919877 3 0718034 2 Tf x1 3 686164经过十次迭代 得到最优解 x 00 Tf x 0 最优化设计 无约束优化方法 6 4 2最速下降法 4 图4 3表示例4 1的搜索路径 目标函数等值线为椭圆 若进行代换y1 x1y2 5x2则f x1 x2 变为 y1 y2 等值线为一族同心圆 因为圆上任一点的负梯度方向都指向圆心 因此沿负梯度方向经过一次一维搜索即可找到最优点 图4 5为最速下降法的程序框图 最优化设计 无约束优化方法 7 4 3牛顿型方法 1 牛顿法是用目标函数二阶偏导数的间接方法 因类似于解非线性方程的牛顿法而得名 又叫 二阶导数法 拟线性法 将目标函数泰勒展开 保留到二次项 原目标函数就转变为下列二次型函数 f xk 2f xk x xk 0对于二次型函数 从理论上来说 牛顿法从任选初始点一步就能收敛到最优点 但对于目标函数不是二次型 或计算机截断误差的影响 往往需要多次迭代才能得到最优点 牛顿法的迭代公式为 xk 1 xk 2f xk 1 f xk k 0 1 2 2f xk 为f x 在xk点处的海赛矩阵 最优化设计 无约束优化方法 8 4 3牛顿型方法 2 为防止牛顿法收敛到极大点而不是极小点 可在迭代过程中作一维搜索 形成改进的牛顿法 阻尼牛顿法 其程序框图见图4 6 牛顿法的最大缺点是需要计算海赛矩阵 并求其逆矩阵 计算量很大 例4 2用牛顿法求f x1 x2 x12 25x22的极小点 取x0 22 T f x0 2x1050 x20 T 4100 T 最优化设计 无约束优化方法 9 4 3牛顿型方法 3 例4 2 续 因为f x1 x2 是二次型函数 用牛顿迭代公式 一步就可达到最优点 对照梯度法和牛顿法迭代公式 可以看出只相差一项海赛矩阵的逆矩阵 因此 牛顿法是对梯度法的进一步修正 事实上 梯度法是对目标函数f x 在点xk的一阶 线性 近似 而牛顿法是对f x 在点xk的二阶 二次 近似 最优化设计 无约束优化方法 10 4 4共轭方向及共轭方向法 1 共轭方向的概念二次正定函数的一般形式为 式中 G为n n阶对称正定矩阵 b b1 b2 bn T为常矢量 c为常数 对于矩阵G 若存在两个n维非零矢量d0和d1 使 d0 TGd1 0成立 则称d0和d1是G共轭方向 或G共轭矢量 特别地 当G为单位矩阵时 d0 Td1 0 则称d0和d1是正交的 矢量正交是矢量共轭的特例 最优化设计 无约束优化方法 11 4 4共轭方向及共轭方向法 2 共轭方向的性质二次收敛性 如n 2 二次函数的等值线为一同心椭圆族 它的极小点就是椭圆中心 该椭圆族有一重要性质 即两平行线与椭圆的两个切点的连线必过椭圆族的中心 且连线与平行线的方向是共轭的 见下图 最优化设计 无约束优化方法 12 4 4共轭方向及共轭方向法 3 因此 从任一点出发 沿任意方向作一维搜索找到的极小点就是椭圆的切点 再沿共轭方向作一维搜索找到的极小点就是椭圆中心也就是目标函数的极小点 这说明 对二维二次正定目标函数只要沿共轭方向作两次一维搜索就可得到其极小点 推广到n维 若采用共轭方向作为搜索方向 任何一个具有极小值的n维二次正定目标函数 理论上最多只要n步就能达到极小点且与所用搜索方向的次序无关 这种性质称为 二次收敛性 利用这种性质的优化方法称为二次收敛方法 最优化设计 无约束优化方法 13 4 4共轭方向及共轭方向法 4 共轭方向法共轭方向是一大类方法 包括共轭梯度法 Powell法等 总的框图见图4 8 其中一种产生共轭方向的方法为格拉姆 斯密特 Gram Schmidt 法 比较有效的共轭方向法都尽量避免计算海赛矩阵 例4 3选三个坐标轴上的单位向量作为一组线性无关向量系 最优化设计 无约束优化方法 14 4 4共轭方向及共轭方向法 5 例4 3 续1 最优化设计 无约束优化方法 15 4 4共轭方向及共轭方向法 6 例4 3 续2 说明d0 d1 d2对G共轭 最优化设计 无约束优化方法 16 4 5共轭梯度法 1 gk Gxk b前面已给出优化算法的搜索迭代公式 xk 1 xk kdk若进行一维搜索 k则为最优步长因子 xk和xk 1两点负梯度方向的差为gk 1 gk G xk 1 xk G xk kdk xk kGdk若dk 1和dk是G共轭方向 则 dk 1 TGdk 0用 dk 1 T前乘 gk 1 gk 有 dk 1 T gk 1 gk k dk 1 TGdk 0即dk 1与 gk 1 gk 正交 共轭梯度法的共轭方向 最优化设计 无约束优化方法 17 4 5共轭梯度法 2 上式表明 从xk开始沿dk方向进行一维搜索 其终点xk 1与始点xk两点的梯度之差gk 1 gk与dk的共轭方向dk 1正交 因此 利用这个性质 不必计算矩阵G即可求出共轭梯度法的共轭方向 共轭梯度法的几何说明 最优化设计 无约束优化方法 18 4 5共轭梯度法 3 共轭梯度法的迭代公式设从xk出发 沿dk gk方向作一维搜索到xk 1点 并算出xk 1点的梯度方向gk 1 由于gk 1是沿等直面在该点的法线方向 而dk是沿等直面在该点的切线方向 故 dk Tgk 1 0 即gk 1Tgk 0 gk 1与gk正交 为了在gk 1和gk构成的正交系中确定共轭方向dk 1 令dk 1 gk 1 kdk即把共轭方向dk 1看成 gk 1与dk的线性组合 k为待定系数 要使dk 1与dk共轭 就应使 dk 1 TGdk 0而 dk 1 TGdk gk 1 kdk TGdk gk 1 kgk TG gk gk 1TGgk kgkTGgk 0 最优化设计 无约束优化方法 19 4 5共轭梯度法 4 因此 前面已推导出gk 1 gk kGdk 即gk 1 gk kGgk或 代入上式得 最优化设计 无约束优化方法 20 4 5共轭梯度法 5 因此 下一个搜索方向确定为 同样 可以证明按上述公式确定的dk 2与dk 1为共轭方向 依此类推而确定的n个dk k 0 1 2 n 1 方向为一组关于G的共轭向量系 上述结论也可由数学归纳法证明 最后 我们得到共轭梯度法的迭代公式为xk 1 xk kdk式中dk gk k 1dk 1 在迭代中第一次搜索方向d0取x0的负梯度方向 g0 最优化设计 无约束优化方法 21 4 5共轭梯度法 6 与梯度法相比 由于修正项 kdk改进了收敛性 使搜索方向共轭 故能以较少的迭代次数收敛到最优点 由于计算梯度时很可能出现误差 使搜索方向不能完全保持共轭 同时目标函数也可能不是正定的二次函数 因此n次迭代后一般都不会达到精确的极小点 可在每n次迭代后令d0 dn gn作为下一轮迭代的第一次搜索方向 重新开始新一轮迭代 上述共轭梯度法又称Fletcher Reeves共轭梯度法 而PRP Polak Ribiere Poiyak 共轭梯度法按下式计算 k 1 最优化设计 无约束优化方法 22 4 5共轭梯度法 7 共轭梯度法 Fletcher Reeves 的算法1 给定变量个数n 选取收敛精度 和初始点x0 计算x0点的梯度g0 取第一次搜索方向d0 g0 令k 0 2 沿dk方向作一维搜索 得到xk 1点 xk 1 xk kdk k k 1 转2 继续进行迭代 最优化设计 无约束优化方法 23 4 5共轭梯度法 8 例4 4用共轭梯度法求f x1 x2 x12 2x22 4x1 2x1x2的极小点 取x0 11 Td0 g0 2x1 2x2 44x2 2x1 x0 4 2 T沿d0进行一维搜索x1 x0 0d0 11 T 0 4 2 T 1 4 01 2 0 T在x1点f x1 x2 1 4 0 2 2 1 2 0 2 4 1 4 0 2 1 4 0 1 2 0 令df d 0 0 有8 1 4 0 8 1 2 0 16 2 2 16 0 8 32 0 8 16 0 16 4 32 0 80 0 20 0 0 0 25 x1 20 5 Tg1 2x1 2x2 44x2 2x1 x1 1 2 T 最优化设计 无约束优化方法 24 4 5共轭梯度法 9 例4 4 续 d1 g1 0d0 21 5 T沿d1进行一维搜索x2 x1 1d1 20 5 T 1 21 5 T 2 2 10 5 1 5 1 T在x2点f x1 x2 2 2 1 2 2 0 5 1 5 1 2 4 2 2 1 2 2 2 1 0 5 1 5 1 令df d 1 0 有4 2 2 1 6 0 5 1 5 1 8 2 4 6 1 8 8 1 3 9 1 8 8 12 1 5 1 5 0 1 1 x2 42 T因为g2 00 T 且在x2点处海赛矩阵正定 故x2为极小点 x x2 42 Tf x 8 最优化设计 无约束优化方法 25 4 6变尺度法 1 变尺度法又被称为 拟牛顿法 大步梯度法 共轭方向法 其中最有名的是DFP算法 变尺度法是在牛顿法的基础上演变发展的 但它是一阶方法 不求二阶偏导数 而是用一个矩阵近似表示海赛矩阵的逆矩阵 然后在搜索迭代过程中不断修正这个矩阵 使它逐步逼近海赛矩阵的逆矩阵 一 尺度矩阵的概念通过尺度变换可改进收敛性 对于一般二次函数 进行尺度变换x Qx 则二次项 若G正定 则总存在矩阵Q使QTGQ II为单位矩阵 最优化设计 无约束优化方法 26 4 6变尺度法 2 用Q 1左乘等式两边 再用Q左乘等式两边 得到QQTG I即QQT G 1令H QQTH称为尺度矩阵 要求H正定 则牛顿法迭代公式变为xk 1 xk kH f xk k 0 1 2 二 变尺度矩阵的建立用尺度矩阵逼近海赛矩阵的逆矩阵G 1 则构成一个尺度矩阵序列 Hk 因此 尺度在不断变化 迭代公式为xk 1 xk kHkgk k 0 1 2 gk f xk 最优化设计 无约束优化方法 27 4 6变尺度法 3 对Hk的要求 1 Hk应对称正定 2 Hk之间的迭代应具有下列简单的形式 Hk 1 Hk EkEk为n n阶矩阵 称为校正矩阵 3 Hk必须满足拟牛顿条件Hk 1yk skyk gk 1 gksk xk 1 xk三 变尺度法的一般步骤图4 11为变尺度法的程序框图 最优化设计 无约束优化方法 28 4 6变尺度法 4 四 DFP算法根据校正公式中Ek选取的不同 形成不同的变尺度法 其中最著名的为DFP算法 DFP算法中Ek取下列形式 Ek kukukT kvkvkT式中 k k为待定常数 uk vk是n维待定向量 ukukT和vkvkT都是对称 秩为1的n n阶矩阵 取 k k uk vk 使它们满足 kukukTyk sk kvkvkTyk Hkyk注意到uyk和vyk均为1 1阶矩阵即常量 可取uk skvk Hkyk定出 最优化设计 无约束优化方法 29 4 6变尺度法 5 因此 DFP算法校正公式为 例4 5用DFP法求f x1 x2 x12 2x22 4x1 2x1x2的最优解 1 取x0 11 Tk 0g0 42 TH0 Id0 H0g0 4 2 T沿d0进行一维搜索x1 x0 0d0 1 4 01 2 0 T令df d 0 0 得到 0 0 25 x1 20 5 T2 k 1g1 1 2 Ty0 g1 g0 3 4 Ts0 x1 x0 1 0 5 T 最优化设计 无约束优化方法 30 4 6变尺度法 6 d1 H1g1 0 84 0 760 38 0 82 T 1 61 2 Tx2 x1 1d1 2 1 6 10 5 1 2 1 T令df d 1 0 得到 1 1 25 x2 42 T3 g2 00 T 例4 5 续 x2 T 2f x2 x2 40 42 T 16 0 2f x2 正定 x x2 42 Tf x 8 最优化设计 无约束优化方法 31 4 7坐标轮换法 1 坐标轮换法属于不求导数的直接搜索法 它的基本思想是取x的n个坐标方向作为搜索方向 即从x0出发 第一次搜索沿x1坐标方向 第二次搜索沿x2坐标方向 第n次搜索沿xn坐标方向 第n 1次搜索沿x1坐标方向 依次类推 搜索不断沿坐标方向轮换进行 直到收敛条件被满足 坐标轮换法一般不作一维搜索 坐标轮换法的算法如下 1 选取初始点x0 x0又称为初始基点 初始步长 xi 收敛精度 i 一般初始步长可取为变量估计变动范围 ui li 的1 100 收敛精度 i可取为初始步长 xi的1 100 令k 0 2 k k 1 进行一轮依次沿坐标方向的探查搜索 先给x1一个增量 x1 其它变量保持不变 得到一个试验点 最优化设计 无约束优化方法 32 4 7坐标轮换法 2 检验xs的适行性 若f xs f xk 1 则xs就作为下一个坐标方向搜索的起点 否则 从xk 1点沿反方向搜索 若两个方向的搜索都失败了 则停在原来的点不动 接着 以步长 x2沿x2坐标方向搜索 直到xn为止 此轮探查搜索的终点称为基点xBk 3 作模式移动 PatternMove 到点xMk 模式移动的方向是从前一个基点xBk 1到当前基点xBk 移动量是两基点之间的距离 即 检验模式移动的适行性 若f xMk f xBk 则xMk就作为下一轮搜索的起点 否则 取消此次模式移动 xBk作为下一轮搜索的起点 最优化设计 无约束优化方法 33 4 7坐标轮换法 3 4 重复2 3 的搜索 模式移动的循环 直到各个坐标方向探查搜索都失败 仍停留在原基点不动为止 检验收敛准则 xi I是否满足 若不满足 则将各变量步长 xi i 1 2 n 都减少一半 重新开始新一轮探查搜索 若满足 则输出最优点x xBk 例用坐标轮换法解f x x12 x22 6 x1 x2 x3 min 求经过一轮探查搜索和模式移动后的终点xM 1 1 选取变量估计下限xl 000 T 变量估计上限xu 101010 T 初始点x0 xB 0 555 T 初始步长 x1 x2 x3 0 1 收敛精度 1 2 3 0 001 求出f0 f x0 52 进行探查搜索 x1方向 向正向搜索 xs 5 155 T f xs 4 59 不适行 向反向搜索 xs 4 955 T f xs 5 39 适行 最优化设计 无约束优化方法 34 4 7坐标轮换法 4 x2方向 向正向搜索 xs 4 95 15 T f xs 4 98 不适行 向反向搜索 xs 4 94 95 T f xs 5 78 适行 x3方向 向正向搜索 xs 4 94 95 1 T f xs 5 68 不适行 向反向搜索 xs 4 94 94 9 T f xs 5 88 适行 因此 xB 1 4 94 94 9 T f xB 1 5 88 3 作模式移动xM 1 xB 1 xB 1 xB 0 4 94 94 9 T 4 94 94 9 T 555 T 4 94 94 9 T 0 1 0 1 0 1 T 4 84 84 8 T由于f xM 1 6 72 f xB 1 因此模式移动满足适行性 点 4 84 84 8 T作为下一轮探查搜索的起点 最优化设计 无约束优化方法 35 4 7坐标轮换法 5 坐标轮换法被认为是目前最成功的优化算法之一 至今仍被广泛应用着 国外有些专家曾以工程实际中实际提出的优化设计问题作为考题 对各种优化方法进行专门研究对比 坐标轮换法是名列前茅的算法之一 坐标轮换法的缺点是有时收敛较慢 由于其搜索方向是固定的 如果恰好遇到某些约束曲面的走向对它的搜索特别不利时 往往会在接近最优点之前 粘 在约束边界上中止收敛而得到一个假最优点 针对这个缺点 已提出了一些改进措施 如 多选几个初始点进行多次运行 选择较为 温和 的罚函数 搜索中止后 对最后一个点的邻近区域进行随机 扫靶 搜索 如能发现一个新的好点 则以此点作为起点开始一轮新的搜索 设法使搜索在遇到约束边界后改变固定的搜索方向 沿约束边界 爬行 等 最优化设计 无约束优化方法 36 4 8鲍威尔法 1 鲍威尔 Powell 法的搜索方向是共轭的 但不需要计算目标函数的导数 这是它的一大优点 一 共轭方向的生成 gk Gxk bgk 1 Gxk 1 bgk 1 gk G xk 1 xk Gdk设xk xk 1为沿同一方向dj进行一维搜索得到的两个极小点 因此dj和梯度方向正交 图4 15 有 dj Tgk 0 dj Tgk 1 0根据共轭方向的定义 式4 11 有 dj T gk 1 gk dj TGdk 0因此 dj和dk是G共轭方向 最优化设计 无约束优化方法 37 4 8鲍威尔法 2 二 基本算法图4 17为Powell法搜索过程 1 任选一初始点x0 确定收敛精度 选择坐标轴方向ei i 1 2 n 为第一轮搜索方向 令k 0 xB 0 x0 2 k k 1 从xB k 1 出发 分别沿ei i 1 2 n 作一维搜索 此轮搜索的终点为xB k 3 作模式移动 沿dk xB k xB k 1 作一维搜索 得到xk 作为下一轮搜索的起点 4 检验收敛准则 如满足则输出当前点xk作为最优点 5 若未收敛 则重复2 3 的一维搜索和模式移动 但每一轮一维搜索中都用上一轮模式移动方向代替原有的一个坐标轴方向 如第二轮搜索方向为e2 e3 en d1 依次类推 最优化设计 无约束优化方法 38 4 8鲍威尔法 3 三 改进的算法框图见图4 18 在每一轮搜索后 模式移动与坐标轮换法的相同而不作一维搜索 另外增加了Powell判别条件 若满足判别式 则用模式移动方向替换目标函数值下降量最大的一个方向 以保证下一轮搜索方向组线性无关 例4 6用Powell法求f x1 x2 10 x1 x2 5 2 x1 x2 2的极小值 选取x0 0 00 T F0 f0 250 第一轮搜索 1 沿e1 10 T方向作一维搜索 得到x1 0 4 54550 T f1 22 727 1 f0 f1 227 273 2 沿e2 01 T方向作一维搜索 得到x2 0 4 54550 8264 T F2 f2 15 214 2 f1 f2 7 513 m 1 227 273 3 模式移动 x3 0 2x2 0 x0 0 9 0911 6528 TF3 f x3 0 385 24 最优化设计 无约束优化方法 39 4 8鲍威尔法 4 4 检验Powell判别条件 因为F3 F0 因此下一轮搜索方向仍用e1 e2方向 因为F2 F3 因此x2 0 作为下一轮搜索的起点 第二轮搜索 起点x0 1 x2 0 4 54550 8264 T F0 f0 15 214 1 沿e1 10 T方向作一维搜索 得到x1 1 3 86930 8264 T F1 f1 10 185 1 f0 f1 5 029 2 沿e2 01 T方向作一维搜索 得到x2 1 3 86931 3797 T F2 f2 6 818 2 f1 f2 3 367 m 1 5 029 3 模式移动 x3 1 2x2 1 x0 1 3 19311 9330 TF3 f x3 1 1 7474 检验Powell判别条件 因为F3 F0且 F0 2F2 F3 F0 F2 m 2 0 5 m F0 F3 2 故用模式移动方向d3 1 x2 1 x0 1 0 67620 5533 T代替e1 沿d3 1 方向作一维搜索 得到下一轮搜索的起点 x0 2 2 499952 5091 TF0 f0 0 0008若不满足收敛准则 则再进行第三轮搜索 最优化设计 无约束优化方法 40 4 9单形替换法 1 单形替换法又称单纯形 Simplex 法 属于直接搜索方法 一 基本原理单纯形就是在n维空间中由n 1个顶点构成的形体 在优化搜索过程中要满足适行性 就要对目标函数的变化趋势有大概的估计 避免盲目选择搜索方向 可以根据若干点的目标函数值大小的变化推测这种趋势 这些点可取为单纯形的顶点 单纯形的基本思想是利用单纯形的顶点构造有利的搜索方向和步长 用新的较好点取代原来较差的点 构成新的单纯形 不断向最优点逼近 假定在一个二维问题中 已求得不在一条直线上的三个点H S L 及它们的目标函数值fH fS fL 且fH fS fL 这三点构成一个单纯形 三角形 如有更好点 则在最差点H的反对称方向可能性最大 最优化设计 无约束优化方法 41 4 9单形替换法 2 因此 取S和L两点的中点M 从H出发沿H和M的连线作模式移动到A点 然后舍弃H点 剩下的S L和A又构成一个单纯形 推广到n维的情况 仍在单纯形的n 1个顶点中取三个点 H为最