资源描述
4 一 维 优 化 方 法4.1 概 述4.2 初 始 搜 索 区 间 的 确 定4.3 黄 金 分 割 法 1、 消 去 法 : 不 断 的 消 去 部 分 搜 索 区 间 , 逐 步 缩 小 最 优 点 所在 的 范 围 , 最 终 找 到 最 优 点 ( 如 : 黄 金 分 割 法 、 Fibonacci法 )2、 近 似 法 : 用 一 个 多 项 式 来 代 替 目 标 函 数 , 并 用 多 项 式 的极 小 点 作 为 目 标 函 数 的 近 似 最 优 点 ( 如 : 二 次 插 值 法 ) 31 322 1 21 初 始 区 间 : , 31 312111 11 1f 1 3122f111f12 2f 131 , 新 区 间 131 , 新 区 间 ll l)1( 内 分 点 的 取 点 原 则 为 : )(618.0)( )(382.0)(1( )1(1)1(3)1(1)1(1)1(3)1(112 )1(1)1(3)1(1)1(1)1(3)1(111 3)1(31)1(1 ; 第 一 次 缩 短 时 的 原 区 间 :区 间 缩 短 的 终 止 条 件 :设 : K区 间 缩 短 次 数 , 迭 代 精 度 , 按 点 距 准 则 : )(618.0)( 1313)(1)(3 kkkk 4 一 维 优 化 方 法4.4 二 次 插 值 法 (近 似 抛 物 线 法 ) 一 维 优 化 方 法 例 题 分 析 1、 进 一 步 体 会 一 维 优 化 方 法 的 基 本 思 想2、 明 确 黄 金 分 割 法 和 二 次 插 值 法 之 间 的 区 别3、 熟 悉 二 次 插 值 法 的 基 本 思 想 及 应 用 条 件 4.4 二 次 插 值 法 (近 似 抛 物 线 法 ) 多项式逼近原理 利 用 目 标 函 数 在 一 些 点 的 函 数 值 等 信 息 来构 造 一 个 低 次 插 值 多 项 式 , 以 此 多 项 式 的 最 优点 作 为 原 函 数 的 最 优 点 的 近 似 解 1、 取 点 且 计 算 相 应 函 数 值 (构 造 插 值 节 点 ) , )( 31 初 始 区 间 :一 元 函 数 : f 321 _ ttt点 :试 )(21 31223311 ttt )()()( 332211 ffffff 相 应 函 数 值 : ),(),(;)( 333222111 fPfPfP ,插 值 节 点 : 2、 过 “ - - ” 点 构 造 一 个 二 次 曲线 2P )(f 逼 近)(p 1P 3P2)( cbap “逼 近 函 数 ”)(p式 中 : a、 b、 c待 定 系 数 根据插值原理: )( 1)( )( )( 32333 22222 12111 fcbap fcbap fcbap )(f O )(f)(p )( 111 fP , )( 222 fP , )( 333 fP , p* 3 3f11f 2 2f )()( )()()( 133221 321122313113223 fffa )()( )()()( 133221 321213132 fffc )()( )()()( 133221 322212212312322 fffb解 方 程 组 ( 1) 得 : 2)( cbap 3、 求 插 值 函 数 的 极 小 点 :)(p p 321213132 322212212312322 )()()( )()()(21 fff fffp 02)( cbp cbp 2 )( )()( )()( 32 112122 13131 cffc ffc令 : 2)( cbap )( 213121 ccp 然 后 , 原 区 间 再 缩 短 , 进 行 多 次 的 插 值 计算 , 使 的 点 列 不 断 逼 近 原函 数 的 极 小 点 * * 2*1 pp ,p )()( 44 ffff pp pf 与 两 点 函 数 值 的 大 小 。 两 者 较 小 者 相 应 的 点 为 新 的 点 ( 与 均 有 可 能 )。 以 此 新 点 左 右 两 邻 点 为 新 的 和 点 , 缩 短 后 的 新 区 间 2 12 3 31 , 2 p p 步 骤 2比 较 与 的 大 小 , 按 照 相对 于 的 位 置 , 区 间 缩 短 分 下 面 4种 情 况 : p2 2f pf 不 变, 3221 ; p 13142 )(. , fffb p:)(1 24 p) )(, 4321 p不 变 , 13142 )(. , fffa p p)(f O )(f)(p 3 3f11f 2 2f pf )(f O )(f p 3 3f11f 2 2f pf13 2 )(f O )(f 3 3f11f 2 2fp pf13124 )(. , fffc p 13124 )(. , fffd p 不 变, 14223 )( p:) 24 )(2 p 不 变, 321 , p 3 )(f O )(f )(p p 3 3f11f 2 2fpf1 2 当 缩 短 后 的 新 区 间 确 定 后 , 既 可 重 复 前 述 的插 值 计 算 。 这 样 , 多 次 重 复 “ 插 值 区 间 缩短 插 值 ” 的 计 算 循 环 。 插 值 函 数 的 就极 其 接 近 目 标 函 数 的 最 优 点 。 最 后 可 按 终止 准 则 规 定 的 精 度 满 足 要 求 而 终 止 计 算* p )1(1 )()1( kkpkp 、 点 距 准 则 )(2 教 科 书 中 的 框 图 使 用、 函 数 下 降 量 准 则 : )(: * )(* ff kp上 式 满 足 (见 教 科 书 ) 例 题 分 析 分 别 用 黄 金 分 割 法 与 二 次 插 值 法 求 目 标 函 数3510)( 2 xxXf 的 最 优 解 初 始 区 间 为 1.5, 7.5 迭 代 精 度 为 1、 0.618 法 : 1.0 208.5 )5.15.7(618.05.1)(618.0792.3 )5.15.7(382.05.1)(382.0 13112 13111 xxxx xxxx解 : 取 内 分 点 求 相 应 的 函 数 值)()( 1211 xfxf 、 1211 xx 、 043264.103510)( 459264.113510)( 12212122 11211111 xxxff xxxff 1x 21x 初 始 区 间 : , 31 312111 1x 3x12x2f11x1f )1( 3)1(1131 , xxxx 新 区 间 缩 短 区 间 1221 11)1(1 11121 : xx xx xxff 并 做 置 换 , 舍 去 : 不 变 )1(3x 验 证 精 度 要 求 1.0708.3792.35.7)1(1)1(3 xx :22x增 补 新 分 点 083544.6)792.35.7(618.0792.322 x )(618.0 )1(1)3(1)1(122 xxxx 不 满 足 精 度 要 求 , 须 返 回 步 骤 2继 续 缩 小 区 间各次缩短区间结果如下: K次 数 x1 x3 xK1 xK2 f1 f2 比 较0 1.5 7.5 3.792 5.208 11.459264 10.043264 1 3.792 7.5 5.208 6.083544 10.043264 11.1740676 3 4.66736908 6.083544 5.208 5.54256546 10.043264 10.29437728 4 4.66736908 5.54256546 5.00169455 5.208 10.0000029 10.043264 6 4.87389054 5.208 5.00169455 5.08037019 10.0159036 10.00645937 8 4.95276577 5.08037019 5.00169455 5.0316253 10.0000029 10.00100016 9 4.95276577 5.0316253 4.98289011 5.00169455 10.00029275 10.0000029 则 终 止 迭 代 , 最 优 解 为 : 00006091.10)( 99219553.42* )9(1)9(3* xff xxx经 九 次 迭 代 得 新 区 间 长 度 : 0487352.095276577.403162533.5)9(1)9(3 xx2、 “ 二 次 插 值 法 ” : 310解 : 、 取 初 始 插 值 结 点 1.5, 7.5 1)()(1 32 11212213 131 xx cxxffcxx ffc 、 计 算 插 值 函 数 的 极 小 点 与 极 小 值10)( 5)(5.0 )1*()1*( 2131)1*( ppp xff ccxxx 25.16)(5.7 )5.4(25.10)()(5.0 25.22)(5.1 333 22232 111 xffx xxffxxx xffx , , 、 缩 短 区 间 )1(32 2)1*(24)1*( 5.75.4 ,新 区 间 : ; old pp xx ffxxx )( xf O x)( xf px 3x 3f1x1f 2x 2f pf1x 2x 105)2*(* )2*(* ppff xx最 优 点 和 最 优 值 : 、 检 验 终 止 条 件 105 12 )2*()2*( 21 pp fx cc , 、 重 复 步 骤 055 )1*()2*( pp xx 通 知 : 本 周 三 不 上 课 , 上 机 实 践 。 望 各 位 同 学 提 前 做 好 准 备 ! 上 机 内 容 : 一 维 优 化 方 法 程 序 调 试 、 一 维 优 化 方 法 作 业 为 教 科书 本 章 全 部 作 业 ) ; 上 机 地 点 : 机 械 学 院 机 房 (C座 地 下 室 )。 作 业 要 求 : 1) 打 印 程 序 清 单 和 程 序 运 行 结 果 ( 须 注 明 题 号 ) 。 2) 第 7周 周 五 交 作 业 , 过 期 不 候 !选 做 作 业 :1、 编 程 图 解 下 列 函 数 的 图 像 和 等 值 线 图 形 ( 补 充 ) 2 2 2 22 1 12 2 22 2 1 21 2 41 1 21. ( ) 100( ) (1 )1 100 12. ( ) 12 ( )10( )f X x x xx x xf X x x x x 2、 试 编 写 “ 黄 金 分 割 法 ” 和 “ 二 次 插 值 法 ” 的 求 优 程 序 预 习 :5 无 约 束 优 化 方 法 坐 标 轮 换 法 用 黄 金 分 割 法 和 二 次 插 值 法 分 别 求 f(x)=3x2+12/x3-5在 0.5,2.5内 的 最 优 解 ; 求 f(x)=x4-5x3+4x2-6x+60的 最 优 解 。
展开阅读全文