第二部分：03第三章 一维搜索方法.pdf

2013 9 24 1 昆明理工大学机电工程学院 2013年9月22日星期日8时42分35秒 1 第三章第三章 一维搜索方法一维搜索方法 主要内容 主要内容 一维搜索的基本思想一维搜索的基本思想 0 618法 黄金分割法 法 黄金分割法 二次插值法二次插值法 实例分析实例分析 第第2 2部分部分 优化设计 优化设计 昆明理工大学机电工程学院 2013年9月22日星期日8时42分35秒 2 第三章第三章 一维搜索方法一维搜索方法 一 一维搜索的基本思想一 一维搜索的基本思想 第第2 2部分部分 优化设计 优化设计 在多维优化问题的迭代过程中 每次迭代寻优下一在多维优化问题的迭代过程中 每次迭代寻优下一 点 新点 点 新点 xk 1时 根据基本迭代公式可知 需在已经时 根据基本迭代公式可知 需在已经 确定的搜索方向确定的搜索方向Sk上求一个步长因子 并使这新点的目上求一个步长因子 并使这新点的目 标函数值下降最多 即标函数值下降最多 即f xk 1 f xk 这样的步长因子这样的步长因子 k就是一维搜索的最优化步长因子 就是一维搜索的最优化步长因子 求求 k值的方法叫做值的方法叫做一维搜索最优化方法一维搜索最优化方法 求解最优步长因子实质上是求单变量求解最优步长因子实质上是求单变量 k的极值问题 的极值问题 也就是寻求一个最优步长因子也就是寻求一个最优步长因子 k使使f xk kSk 沿给定方向沿给定方向 Sk为极小 这个过程叫做为极小 这个过程叫做一维最优化搜索一维最优化搜索 min kkkkk ffSxSx 昆明理工大学机电工程学院 2013年9月22日星期日8时42分35秒 3 第三章第三章 一维搜索方法一维搜索方法 一 一维搜索的基本思想一 一维搜索的基本思想 第第2 2部分部分 优化设计 优化设计 根据优化设计的根据优化设计的思想思想 迭代优化的关键问题是 如何确定每次迭代的方向迭代优化的关键问题是 如何确定每次迭代的方向 Sk与步长因子与步长因子 k 由于每次迭代都需要进行一次一维搜索 因此 一由于每次迭代都需要进行一次一维搜索 因此 一 维搜索贯穿于整个迭代过程 它是优化方法中最简单 维搜索贯穿于整个迭代过程 它是优化方法中最简单 最基础的方法 当然 也可用来解决一维优化问题 最基础的方法 当然 也可用来解决一维优化问题 如目标函数如目标函数可微可微 最优步长因子可以用 最优步长因子可以用解析法解析法求得 求得 一般采用一般采用搜索迭代搜索迭代的方法来求得的方法来求得 k 常用的方法有 常用的方法有黄黄 金分割法金分割法 也叫也叫0 618法法 牛顿法 牛顿法 二次插值法二次插值法和三次插和三次插 值法等 值法等 昆明理工大学机电工程学院 2013年9月22日星期日8时42分35秒 4 第三章第三章 一维搜索方法一维搜索方法 一 一维搜索的基本思想一 一维搜索的基本思想 第第2 2部分部分 优化设计 优化设计 确定一个最小值所在的区间 确定一个最小值所在的区间 求出该区间内的最优步长因子求出该区间内的最优步长因子 k值 值 一维最优化搜索是要在单峰区间求单峰函数的极小一维最优化搜索是要在单峰区间求单峰函数的极小 点 通常分两步进行 点 通常分两步进行 确定搜索区间的确定搜索区间的外推法外推法 在一维搜索时 假设函数在一维搜索时 假设函数f 具有单谷性 即在所考具有单谷性 即在所考 虑的区间内部 函数虑的区间内部 函数f 有唯一得极小点有唯一得极小点 为了确定 为了确定 极小点极小点 所在得区间所在得区间 a b 应使函数 应使函数f 在在 a b 区间形区间形 成 高 低 高 趋势 成 高 低 高 趋势 f 0 ab 对于一般情况 分正向对于一般情况 分正向 搜索和反向搜索的外推法 搜索和反向搜索的外推法 昆明理工大学机电工程学院 2013年9月22日星期日8时42分35秒 5 第三章第三章 一维搜索方法一维搜索方法 一 一维搜索的基本思想一 一维搜索的基本思想 第第2 2部分部分 优化设计 优化设计 在进行一维搜索时 从在进行一维搜索时 从 0 或任意一初始点或任意一初始点 开始 开始 以初始步长以初始步长h0向前试探 如果函数值下降 则保持原方向前试探 如果函数值下降 则保持原方 向不变 将向不变 将步长加倍步长加倍 如果函数值上升 则 如果函数值上升 则步长变号步长变号 即改变搜索方向 区间的始点 中间点依次沿搜索方向即改变搜索方向 区间的始点 中间点依次沿搜索方向 前进一步 前进一步 f 0 ab 最后得到的三点即为搜最后得到的三点即为搜 索区间的始点 中间点和索区间的始点 中间点和 终点 形成函数值的 高终点 形成函数值的 高 低 高 趋势 低 高 趋势 f 0 b a 此过程一直进行到函数值此过程一直进行到函数值再次上升再次上升时为止 即可找到时为止 即可找到 搜索区间的终点 搜索区间的终点 昆明理工大学机电工程学院 2013年9月22日星期日8时42分35秒 6 第三章第三章 一维搜索方法一维搜索方法 一 一维搜索的基本思想一 一维搜索的基本思想 第第2 2部分部分 优化设计 优化设计 正向搜索正向搜索 每走一步都将区间的始点 中间点沿搜索方向移动一每走一步都将区间的始点 中间点沿搜索方向移动一 步步 进行换名进行换名 经过三步最后确定搜索区间 经过三步最后确定搜索区间 1 2 并且 并且 得到区间始点 中间点和终点得到区间始点 中间点和终点 1 2y2y2 则极小点 则极小点 必在必在 1右方 作右方 作正向正向搜索寻求第三点 搜索寻求第三点 y1 y2 则极小点 则极小点 必在必在 1 h0左方 作左方 作反向反向搜索寻第三点 搜索寻第三点 y1 y2 则极小点 则极小点 必在必在 1和和 1 h0之间 则为 高之间 则为 高 低低 高 高 形态 找到初始单峰区间为形态 找到初始单峰区间为 1 1 h0 2013 9 24 2 昆明理工大学机电工程学院 2013年9月22日星期日8时42分35秒 7 第三章第三章 一维搜索方法一维搜索方法 一 一维搜索的基本思想一 一维搜索的基本思想 第第2 2部分部分 优化设计 优化设计 若若y1y2 则再作正向搜索 则再作正向搜索 步长再加倍 下一计算点为步长再加倍 下一计算点为 1 7h0 若若y1 y2 则初始单峰区间为 则初始单峰区间为 1 h0 1 3h0 1 y 1 2 y 2 12 yy 12 0 h 0 h 3 3 y23 yy 23 昆明理工大学机电工程学院 2013年9月22日星期日8时42分36秒 8 第三章第三章 一维搜索方法一维搜索方法 一 一维搜索的基本思想一 一维搜索的基本思想 第第2 2部分部分 优化设计 优化设计 开始沿开始沿 的正方向搜索 由函数值的上升而改变搜的正方向搜索 由函数值的上升而改变搜 索方向 最后得到始点 中间点和终点索方向 最后得到始点 中间点和终点 1 2 3 及 及 它们的对应函数值它们的对应函数值y1 y2 y3 从而形成单谷区间 从而形成单谷区间 3 1 为一维搜索区间 为一维搜索区间 因为 因为 y1y3 继续沿反向搜 继续沿反向搜 索 并加倍步长索 并加倍步长4h0 寻求下 寻求下 一点一点 3 h0 4h0 5h0 并计算并计算f 3 令令 y1 y2 y2 y3 此时此时y2 y3 反向搜索反向搜索 y O 1 y 1 2 y 2 0 h 0 h 3 3 y 21 12 21 yy 12 yy 相邻三点的函数值构成 高相邻三点的函数值构成 高 低低 高 形态 得到单峰区间高 形态 得到单峰区间 3 1 即 即 5h0 0 0 4h 32 21 yy 32 yy 3 3 y 21 昆明理工大学机电工程学院 2013年9月22日星期日8时42分37秒 10 第三章第三章 一维搜索方法一维搜索方法 一 一维搜索的基本思想一 一维搜索的基本思想 第第2 2部分部分 优化设计 优化设计 在搜索区间内取两点在搜索区间内取两点a1 bl a1 bl 计算 计算f a1 f bl 有三种可能情形 有三种可能情形 缩短搜索区间的缩短搜索区间的消去法消去法 搜索区间搜索区间 a b 确定后 需要进一步缩短搜索区间 确定后 需要进一步缩短搜索区间 一般采用一般采用区间消去法区间消去法逐步缩短搜索区间 从而找到极逐步缩短搜索区间 从而找到极 小点的数值近似解 小点的数值近似解 要想把区间要想把区间 a1 b1 进一步缩进一步缩 短 需在其内部取两个点短 需在其内部取两个点 而不是一个点 计算出相 而不是一个点 计算出相 应的函数值再加以比较 应的函数值再加以比较 可把第三种情形合并到前面可把第三种情形合并到前面 两种情形中去 两种情形中去 f a1 f 2 f 3 二次插值函数的二次插值函数的构造构造及其及其极值点极值点 以这三点构造二次多项式以这三点构造二次多项式P 求该多项式的极值点求该多项式的极值点 p 2 210 aaaP 02 21 ppp aaP 2 1 2a a p 昆明理工大学机电工程学院 2013年9月23日星期一2时12分42秒 28 第三章第三章 一维搜索方法一维搜索方法 三 二次插值法三 二次插值法 第第2 2部分部分 优化设计 优化设计 将上述三点及其相应函数值代入多项式有 将上述三点及其相应函数值代入多项式有 二次插值函数的二次插值函数的构造构造及其及其极值点极值点 则 则 解得 解得 2 210 aaaP 11 2 121101 fyaaaP 22 2 222102 fyaaaP 33 2 323103 fyaaaP 133221 3 2 2 2 12 2 1 2 31 2 3 2 2 1 yyy a 133221 321213132 2 yyy a 321213132 3 2 2 2 12 2 1 2 31 2 3 2 2 2 1 2 1 2yyy yyy a a p 这就是这就是f 极小点极小点 的的 近似解近似解 p 昆明理工大学机电工程学院 2013年9月23日星期一2时43分28秒 29 第三章第三章 一维搜索方法一维搜索方法 三 二次插值法三 二次插值法 第第2 2部分部分 优化设计 优化设计 如果区间如果区间 1 3 足够小 则近似极小点足够小 则近似极小点 p 得到该得到该二次插值多项式的二次插值多项式的极小点极小点后 结合给定的三点后 结合给定的三点 1 2 3 利用区间消去原理逐步缩小搜索区间 利用区间消去原理逐步缩小搜索区间 当当f 2 f p 2 f 2 p f p 取取 1 p 如果如果 3 1 f 0 1 3 p 2 f 1 f 2 f 3 f p f 当当f 2 f p 取取 2 3 然后在新的区间内再次利用二次插值法插入新的极然后在新的区间内再次利用二次插值法插入新的极 小点近似值 并进行下一步迭代搜索小点近似值 并进行下一步迭代搜索到满足精度要求 到满足精度要求 昆明理工大学机电工程学院 2013年9月23日星期一2时46分5秒 30 第三章第三章 一维搜索方法一维搜索方法 三 二次插值法三 二次插值法 第第2 2部分部分 优化设计 优化设计 二次插值法在推导插值方程求极小点时 只要求二次插值法在推导插值方程求极小点时 只要求f x 连连 续 不要求续 不要求f x 一阶可微 一阶可微 二次插值法的特点 二次插值法的特点 检验方法为 当检验方法为 当 1 2 f 2 f 2 f 3 3 b 1 5 y3 f 3 0 318 2 0 5 a b 0 5 y2 f 2 3 018 计算计算 p 1 作第一次迭代作第一次迭代 y2 3 018 f p 1 2 983 445 0 2 1 321213132 3 2 2 2 12 2 1 2 31 2 3 2 2 1 yyy yyy p 1 3 2 0 5 1 50 5 p 0 445 昆明理工大学机电工程学院 2013年9月23日星期一2时52分44秒 32 第三章第三章 一维搜索方法一维搜索方法 三 二次插值法三 二次插值法 第第2 2部分部分 优化设计 优化设计 y2 3 018 f p 1 2 983 例例 minf x ex 1 5 x 1 已知初始区间 已知初始区间 a b 0 5 1 5 相邻两点绝对精度相邻两点绝对精度 1 0 13 3 1 5 y3 f 3 0 318 新的三点为 新的三点为 1 p 1 0 445 y1 f p 1 2 983 计算计算 p 2 得 得 p 2 0 569 检验收敛精度 检验收敛精度 p 2 p 1 0 12367 1 0 13 1 3 2 0 5 1 50 5 p 0 445 2 0 5 y2 f 2 3 018 近似极小点为 近似极小点为 p 2 0 569 精确解为 精确解为 0 609 昆明理工大学机电工程学院 2013年9月23日星期一2时54分30秒 33 第三章第三章 一维搜索方法一维搜索方法 四 实例分析四 实例分析 第第2 2部分部分 优化设计 优化设计 例例 解方程 解方程 一元四次方程 有四个实解一元四次方程 有四个实解 其中之一为其中之一为 3 2 6 x1 6 6 x2 6 用用MATLAB程序求解 程序求解 x1 Roots 1 0 22 1 114 x2 11 x1 2 常规代数解法 常规代数解法 7 11 2 21 2 2 1 xx xx 2 12 11xx 7 11 22 11 xx 011422 1 2 1 4 1 xxx 昆明理工大学机电工程学院 2013年9月23日星期一2时59分6秒 34 第三章第三章 一维搜索方法一维搜索方法 四 实例分析四 实例分析 第第2 2部分部分 优化设计 优化设计 例例 解方程 解方程 x1 3 5844 3 0000 3 7793 2 8051 6 x1 6 6 x2 6 x2 1 8481 2 0000 3 2832 3 1313 即四点 即四点 3 5844 1 8481 3 0000 2 0000 3 7793 3 2832 2 8051 3 1313 解为 解为 7 11 2 21 2 2 1 xx xx 6 6 3 2 6 6 6 6x1 x2 昆明理工大学机电工程学院 2013年9月23日星期一2时59分8秒 35 第三章第三章 一维搜索方法一维搜索方法 四 实例分析四 实例分析 第第2 2部分部分 优化设计 优化设计 例例 解方程 解方程 假设假设有有m个个方程 方程 都是都是代数方程代数方程 6 x1 6 6 x2 6 minf x 首先介绍用优化设计进行求解的思想 首先介绍用优化设计进行求解的思想 7 11 2 21 2 2 1 xx xx 0 0 0 2 1 xp xp xp m n x x x x 2 1 0 0 0 2 2 2 1 2 xp xp xp m m i i xp 1 2 0 m i i xpxf 1 2 昆明理工大学机电工程学院 2013年9月23日星期一3时0分43秒 36 第三章第三章 一维搜索方法一维搜索方法 四 实例分析四 实例分析 第第2 2部分部分 优化设计 优化设计 例例 解方程 解方程 6 x1 6 6 x2 6 基于上述思想 对方程做变换 基于上述思想 对方程做变换 7 11 2 21 2 2 1 xx xx 7 11 2 212 2 2 11 xxxf xxxf 0 0 2 1 xf xf 构造目标函数 构造目标函数 22 21 2 2 2 1 2 2 2 1 7 11 xxxxxfxfxf 2013 9 24 7 昆明理工大学机电工程学院 2013年9月23日星期一3时1分20秒 37 第三章第三章 一维搜索方法一维搜索方法 四 实例分析四 实例分析 第第2 2部分部分 优化设计 优化设计 例例 解方程 解方程 进一步可以求进一步可以求H x 矩阵 矩阵 6 x1 6 6 x2 6 对目标函数求偏导数或梯度 对目标函数求偏导数或梯度 构造目标函数 构造目标函数 7 11 2 21 2 2 1 xx xx 22 21 2 2 2 1 2 2 2 1 7 11 xxxxxfxfxf 2 2 212 2 1 2 2112 2 1 7 4 11 2 7 2 11 4 xxxxx xxxxx xf 昆明理工大学机电工程学院 2013年9月23日星期一3时2分32秒 38 第三章第三章 一维搜索方法一维搜索方法 四 实例分析四 实例分析 第第2 2部分部分 优化设计 优化设计 例例 解方程 解方程 function f f himm x x1 x 1 x2 x 2 f x1 2 x2 11 2 x1 x2 2 7 2 6 x1 6 6 x2 6 编写目标函数的编写目标函数的MATLAB程序 程序 7 11 2 21 2 2 1 xx xx 22 21 2 2 2 1 2 2 2 1 7 11 xxxxxfxfxf 昆明理工大学机电工程学院 2013年9月23日星期一3时4分29秒 39 第三章第三章 一维搜索方法一维搜索方法 四 实例分析四 实例分析 第第2 2部分部分 优化设计 优化设计 例例 解方程 解方程 function g g himm x x1 x 1 x2 x 2 w1 x1 2 x2 11 w2 x1 x2 2 7 g1 4 w1 x1 2 w2 g2 2 w1 4 w2 x2 g g1 g2 6 x1 6 6 x2 6 编写梯度的编写梯度的MATLAB程序 程序 7 11 2 21 2 2 1 xx xx 2 2 212 2 1 2 2112 2 1 7 4 11 2 7 2 11 4 xxxxx xxxxx xf 昆明理工大学机电工程学院 2013年9月23日星期一3时4分50秒 40 第三章第三章 一维搜索方法一维搜索方法 四 实例分析四 实例分析 第第2 2部分部分 优化设计 优化设计 例例 解方程 解方程 6 x1 6 6 x2 6 求梯度 还有一种数值的方法 可以避免复杂的推求梯度 还有一种数值的方法 可以避免复杂的推 算 算 因为求导数就是求极限值因为求导数就是求极限值 因此 因此 7 11 2 21 2 2 1 xx xx 2121 0 1 lim nn xxxfxxxf x f 数值法求梯度的相应数值法求梯度的相应MATLAB程序为 程序为 昆明理工大学机电工程学院 2013年9月23日星期一3时5分49秒 41 第三章第三章 一维搜索方法一维搜索方法 四 实例分析四 实例分析 第第2 2部分部分 优化设计 优化设计 例例 解方程 解方程 6 x1 6 6 x2 6 function g g himm num x n length x dt 1e 8 I eye n f0 f himm x for i 1 n g i f himm x dt I i f0 dt end g g 7 11 2 21 2 2 1 xx xx 0 0 1 2 1 2 1 nn x x x x x x x 昆明理工大学机电工程学院 2013年9月23日星期一3时5分59秒 42 第三章第三章 一维搜索方法一维搜索方法 四 实例分析四 实例分析 第第2 2部分部分 优化设计 优化设计 例例 解方程 解方程 6 x1 6 6 x2 6 初始点 初始点 7 11 2 21 2 2 1 xx xx 6 6 3 2 6 6 6 6x1 x2 6 6 x 1 1 d搜索方向 搜索方向 用用inexact line searchs a inex lsearch x d f himm g himm a 3 4585 x new x a d 到点到点 2 5415 2 5415 2013 9 24 8 昆明理工大学机电工程学院 2013年9月23日星期一3时9分40秒 43 第三章第三章 一维搜索方法一维搜索方法 四 实例分析四 实例分析 第第2 2部分部分 优化设计 优化设计 例例 解方程 解方程 6 x1 6 6 x2 6 若改变搜索方向点 若改变搜索方向点 6 6 3 2 6 6 6 6x1 x2 则则 a 4 2865 到点到点 2 5729 1 7135 则向第二相限的点则向第二相限的点 2 8051 3 1313 靠近靠近 确定方向 求步长 即一维搜索 确定方向 求步长 即一维搜索 7 11 2 21 2 2 1 xx xx 1 2 d 昆明理工大学机电工程学院 2