Lecture6算法和算法复杂性一维搜索.ppt

最优化方法 Optimization 第十一讲 第八章 算法和算法复杂性 第九章 一 维 搜 索 主要内容 算法概念 算法收敛准则 全局收敛 , 局部收敛 , 收敛速度 算法二次终止性 算法复杂性 内点法 : 路径跟踪法 算法概念 一下降迭代算法 迭代： ( ) ( 1 ) () () 1 * l im * 0 * kk k k k x A x k k x x xx x 从 一 点 出 发 ， 按 照 某 种 规 则 ， 求 出 后 继 点 ， 用 代 替 ， 重 复 以 上 过 程 ， 得 到 一 个 解 的 序 列 ， 若 该 序 列 有 极 限 点 ， 即 则 称 它 收 敛 于 。 下降 ： 在每次迭代中，后继点处的函数值要有所减少。 下降迭代算法的步骤 ： 。，置选定某一初始点 0.1 )0( kx 。确定搜索方向 )(.2 kd 。迭代点 ，以产生下一个求步长出发，沿方向从 )1( )()(.3 k k kk x dx 。，返回止迭代；否则，令 小点，若是，则停是否为极小点或近似极检查 21: .4 )1( kk x k 选取搜索方向 是最关键的一步，各种算法的区别， 主要在于确定搜索方向的方法不同。 k确 定 步 长 的 主 要 方 法 令它等于某一常数。.1 2. k 可 接 受 点 算 法 ， 即 只 要 能 使 目 标 函 数 值 下 降 ， 可 任 意 选 取 步 长 。 ( ) ( ) ( ) ( ) ( ) ( ) 3. () ( ) m i n ( ) . kk k k k k k x x d fx f x d f x d 基 于 沿 搜 索 方 向 使 目 标 函 数 值 下 降 最 多 ， 即 沿 射 线 求 目 标 函 数 的 极 小 由 于 这 项 工 作 是 求 以 为 变 量 的 一 元 函 数 的 极 小 点 ， 故 常 称 这 一 过 程 为 （ 最 优 ） 一 维 搜 索 ， 这 样 确 定 的 步 长 为 最 佳 步 长 。 定理： ( 1 ) ( ) ( ) ( 1 ) ( ) ( 1 ) () ( ) m in ( ) ( ) 0 k k k k k k k k k k k T k f x x f x d f x d x x d f x d 设 目 标 函 数 具 有 一 阶 偏 导 数 ， 由 下 列 规 则 产 生 ： 则 有 。 证明： 0)( )()( 0)( )( )()( )( )( )( kTk k k kTk k k k k kk kk ddxf ddxf dxf 而 的驻点。为是最优步长，则若 记 二算法映射 定义： ,2 :2 nX X XE AX 给 定 集 合 记 其 幂 集 （ 即 所 有 子 集 构 成 的 集 合 ） 为 ， 称 集 值 映 射 为 一 个 算 法 映 射 (algorithm mapping). 例： ( 0 ) ( 1 ) ( ) m i n | , 0 , | ( ) | () n n kk L P c x Ax b x X x x L P A x y y L P y x x X x A x 考 虑 标 准 形 式 的 线 性 规 划 令 为 的 基 本 可 行 解 ， 若 定 义 算 法 映 射 为 的 基 本 可 行 解 , 并 且 和 的 基 矩 阵 是 相 邻 的 ， 那 么 对 于 任 意 一 个 基 本 可 行 解 ， 迭 代 格 式 就 生 成 一 个 相 邻 的 基 本 可 行 解 序 列 。 例： 2m in . . 1 . x s t x 考 虑 下 列 非 线 性 规 划 ： 1 1 , ( 1 ) 1 ; 2 () 1 ( 1 ) , 1 1. 2 xx Ax xx 定 义 算 法 映 射 ： 3 5 3 9 3 3 5 7 2 5 3 , 2 , , , , 3 , , , , , 3 , , , , 2 4 2 8 3 2 3 6 2 4 A 利 用 算 法 可 以 产 生 不 同 的 点 列 ： x y 1 y=(x+1)/2 A(x(1,k) A(x(2,k) 解集合 把满足某些条件的点集定义为 解集合 当迭代点属 于该集合时，停止迭代 常用的解集合 ： | ( ) 0 | | , ( ) , x f x x x KK T x x S f x b b 为 点 其 中 是 某 个 可 接 受 的 目 标 函 数 值 。 算法收敛问题 定义： ( 1 ) () :2 X k AX Y X x Y A x AY 设 为 解 集 合 ， 为 算 法 映 射 。 给 定 一 个 集 合 ， 若 对 于 任 意 的 初 始 点 ， 算 法 映 射 所 产 生 的 序 列 中 任 一 收 敛 子 序 列 的 极 限 都 属 于 ， 则 称 算 法 映 射 在 上 收 敛 。 ( ) . ( ) . Y g lob a l c o n v e rg e n c e Y loc a l c o n v e rg e n c e 若 集 合 是 任 意 选 取 的 （ 该 集 合 不 必 限 定 在 解 集 合 的 很 小 领 域 内 ） ， 则 相 应 的 收 敛 性 称 为 若 集 合 只 能 取 接 近 的 点 集 ， 则 相 应 的 收 敛 性 称 为 全 局 收 敛 性 局 部 收 敛 性 实用收敛准则 ( 1 ) ( ) ( 1 ) ( ) () 1 . . kk kk k xx xx x 或 者 ( ) ( 1 ) ( ) ( 1 ) () ( ) ( )2 . ( ) ( ) . () kk kk k f x f xf x f x fx 或 者 ()3 . ( ) ( ) .kfx 无 约 束 最 优 化 中 收敛速率 定义： () ( 1 ) _ () () * * l i m * k k p k k k p 设 序 列 收 敛 于 ， 定 义 满 足 的 非 负 数 的 上 确 界 为 序 列 的 收 敛 级 。 p p若 序 列 的 收 敛 级 为 ， 则 序 列 是 级称 收 敛 的 。 11p 序 列 是 以 收 敛 比 线 性若 且 ， 则 称 收 敛 的 。 1 , 1 0pp 若 或 者 且 ， 则 序 列 是 超 线称 性 收 敛 的 。 收敛级 p越大，序列收敛得越快；当收敛级 p 相同时，收敛比 越小， 序列收敛得越快。 例： 01kaa 11 l i m 0 l i m 1 , l i m ( 1 ) () 0 k k kk k k r kk k a aa ar aa aa 又 且 当 时 ， 以 收 敛 比 线 性 收 敛 于 。 例： 2 0 | | 1kaa 1 1 1 1 2 2 2 2 2 2 22 2 l im 0 l im l im 1 , l im ( 2 ) k k k k k kk k k r k k k a a a a r aaa a 又 且 当 时 ， 是 2 级 收 敛 的 。 例： 1 k k 1 1 1 ( 1 ) 1 l i m 0 1 11 l i m l i m 0 111 1 1 l i m l i m ( 1 ) 1 1 1 k k k k k kk k k pk p kk k k k kk kk k kkk p kk k k 又 是 超 线 性 收 敛 的 。 用二次终止性作为判断算法优劣的原因 ： (1)正定二次函数具有某些较好的性质，因此一个好的算法应 能够在有限步内达到其极小点。 (2)对于一般的目标函数，若在其极小点处 Hesse矩阵正定， 因此可以猜想，对正定二次函数好的算法，对于一般目标函 数也应具有较好的性质。 2 ( ) * * * 1 * * * | | * | | 2 T T f x f x f x x x x x f x x x o x x 若某个算法对任意的 正定二次函数 ，从任意的初始点出发，都 能经 有限步 迭代达到其极小点，则称该算法具有 二次终止性 。 算法的二次终止性 算法复杂性 描述算法的存储要求和运行时间要求，分为 算法的空间复杂性和算法的时间复杂性。 利用算法需要的 初等运算次数 表示算法的 时间复杂性 。 算法复杂性 求解实例 I的算法的 基本计算总次数 C(I)是实例输入长度 d(I)的一个函数，该函数被另一个函数 g(x)控制，即存 在一个函数 g(x)和一个常数 a，使得 ( ( ) )C I a g d I 多项式时间算法与指数时间算法 输入规模 (input size)：表示一个 实例 所 需要的字符串长度。 一般的，使用 位二进制就可以 表示任意整数 r。 线性规划的输入规模为： 21 lo g r 2 2 2 1 22 1 1 1 2 1 l o g 1 l o g 1 l o g | | 1 l o g | | 1 l o g | | 2 l o g | | ( , , ) n j j m n m i j j i j i L m n c ab mn m n P P A b c 为 中 所 有 非 零 数 的 乘 积 多项式时间算法与指数时间算法 ( ( ) )C I a g d I 假设问题和解决该问题的一个算法已经给定，若给定该问题 的一个实例 I，存在 多项式函数 g(x)，使得 成立，则称该算法对实例 I是 多项式时间算法 . 若存在 g(x)为多项式函数且对该问题任意一个实例 I ，都有 上式成立，则称该算法为解决该问题的多项式时间算法。 当 g(x)为指数函数时，称相应的算法为 指数时间算法 。 （ 1）随着问题输入规模的增加，算法的计算量（即 算法复杂性）呈多项式增长 . （ 2）一个多项式时间算法利用另一个多项式时间算 法作为其 “ 子程序 ” ，构造一个新的复合型算法， 则新算法仍是多项式时间算法。 多项式时间算法的优点 1 22 m in 10 . . 2 10 10 , 2 , , 0 , 1 , 2 , , n ni i i i j i ij ji i x s t x x i n x i n 上例用单纯形算法需要 2n-1次迭代 单纯形算法的复杂性 精确线搜索 试探法 : 黄金分割法、 Fibonacci法、二分法 函数逼近法 : Newton法、割线法、抛物线法、 三次插值法 非精确线搜索 Armijo步长规则、 Goldstein步长规则、 Wolfe步长规则 一维搜索 ( ) ( ) 0( ) m i n ( ) kkL S f x d ( ) ( ) ( ) ( ) m i n ( E x ac t L i n e S ea rc h ). . k k k k k k k f x d f x d 如 果 求 得 的 ， 使 得 则 称 该 一 维 搜 索 为 精 确 一 维 搜 索 称 为 最 优 步 长 ( ) ( ) ( ) ( I n ex ac t L i n e S ea rc h ). k k k k kf x d f x 如 果 存 在 ， 使 得 则 称 该 一 维 搜 索 为 非 精 确 一 维 搜 索 精确、非精确线搜索 函数逼近法：牛顿法 基本思想： 在极小点附近用二阶 Taylor多项式近似。 )(m in xf 2)()()()()( )( 2 1)()()( kkkkk xxxfxxxfxfx 令 ( ) ( ) ( )( ) ( ) ( ) ( ) 0k k kx f x f x x x 又 令 )( )( )( )( )( )()1( )1( k k kk k xf xf xx xx ，则的驻点，记作得 定理： ( 1 ) () ( ) ( ) 0 ( ) 0 k f x x f x f x x x xx 设 存 在 ， 满 足 ， ， 初 点 充 分 接 近 ， 则 牛 顿 法 产 生 的 序 列 至 少 以 二 级 收 敛 速 度 收 连 续 三 阶 导 敛 于 数 。 证明： )( )( )( xf xf xxA 射牛顿法可定义为算法影 |)( xxx 定义函数 x设解集合为 )(, )()1()( kkk xAxxx 设 ( 1 ) ( 1 ) () ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) () ( ) 2 ( ) () ( ) | | ( ) 1 ( ) ( ) ( ) ( ) | ( ) | 1 ( ) ( ) ( ) ( ) | ( ) | 11 ( ) | ( ) | | ( ) | 2 kk k k k k k k kk k k k k kk k x x x fx x x x f x f x x f x f x f x f x f x x x f x fx x x f x x fx 其 中 在 和 之 间 。 21 )( 21 )( |)(|,|)(| 0, ,0)()()( kxfkxf xxxkk xxxfxfxf k k 处，有的闭区间上的每一点和使得在包含 时，存在接近当连续，和 ( 1) ( ) 2 ( )2 1 ()2k k kkx x x x xk 是 二 级 收 敛 。 1 2 )1( 1 2 )1( xx k k xx ，使得充分接近取初点 | | )()1( )1()( xxxx xxxxxXx kk k 且有 。 上连续在为紧集，是下降函数，且 xx XxAX k )( )( 算法步骤 : ( 0 )1 . , 0 , 0 xk 给 定 初 始 点 允 许 误 差 置 。 .3;,|)(|.2 )()( 否则转则停止计算，得点若 kk xxf 。，返回置 计算点 21 , )( .3 )( )( )()1( )1( kk xf xf xx x k k kk k 缺点： 初 始 点选择十分重要。如果初始点靠近极小点，则 可能很快收敛；如果初始点远离极小点，迭代产生的点 列可能不收敛于极小点。 例： .01.0),21(5m i n xxe x 2)0( x取初始点 解： 00 00 2.060 96.13 01 2.501 2.061 2.12 34 9.534 9.067 7.11 38 8.738 8.220 )()()( kkk xfxfxk 为近似解。6 0 9 6.1 x 0 ( ) m i n a r c t g * 0 . x f x t d t x 最 优 解例： 用 Newton法求解： 2 1( ) , ( ) 1 f x arc tg x f x x 1 1 1 0.785 4 2 2 0.570 8 0.517 8 1.325 8 3 0.116 9 0.116 3 1.013 7 4 0.001 061 k k k k x f x f x 1 1 2 1 . 1 0 7 1 5 2 3 . 5 3 5 7 1 . 2 9 5 2 1 3 . 5 0 3 1 3 . 9 5 k k k k x f x f x 非精确搜索 ( ) ( ) ( ) ( ) ( ) 0 0 1 , ( ) ( ) ( ) km kk k m k k m k T k m f x d f x f x d 设 , ( , ) , ( 0 , 1 ) . 取 步 长 其 中 是 满 足 下 式 的 最 小 非 负 整 数 : Armijo步长规则 根据目标函数的 Taylor展开式， 满足这种规则的步长一定 存在。 非精确搜索 ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) 2 ( ) ( ) ( ) , ( ) ( ) ( 1 ) ( ) . 0 k k k k k T k k k k k T k f x d f x f x d f x d f x f x d 1 设 ( 0 , ) . 取 步 长 满 足 下 式 : 由 于 充 分 小 时 , 第 二 式 必 不 成 立 , 故 该 规 则 在 保 证 目 标 函 数 下 降 的 前 提 下 , 使 下 一 迭 代 点 尽 可 能 远 离 当 前 迭 代 点 . Goldstein步长规则 ( ) ( )( ) 0 , 0. kk k f x d G o l d s t e i n 定 理 : 若 ( ) = 关 于 有 下 界 则 必 存 在 满 足 步 长 规 则 ( ) ( ) ( ) ( ) ( ) 1 1 1 ( ) ( ) ( ) 2 12 ( ) 0 , , ( ) ( ) . 0. 0, ( ) ( 1 ) ( ) k T k k k T k k k T k f x d f x f x d f x f x d 证 明 : 由 于 故 ( ) = 在 充 分 小 时 , ( ) 在 () 的 上 方 由 于 () 关 于 有 下 界 故 () 和 () 在 的 正 半 轴 有 交 点 . 类 似 地 , ( ) = 和 () 在 的 正 半 轴 也 有 交 点 . 取 () 和 () 与 () 的 一 个 最 小 交 点 12 1 2 2 1 1 0) 2 . k G o ld ste in , . 因 . 则 存 在 (, 使 步 长 规 则 成 立 非精确搜索 12 ( ) ( ) ( ) ( ) ( ) 1 ( ) ( ) ( ) ( ) ( ) ( ) 2 ( ) ( ) 0 1 ( ) ( ) ( ) , ( ) ( ) ( ) . () 0 k k k k k T k k k T k k k T k kk k f x d f x f x d f x d d f x f x d f x d 设 . 取 步 长 满 足 下 式 : 该 规 则 使 函 数 的 陡 度 在 点 比 在 = 点 有 所 减 缓 , 从 而 使 下 一 迭 代 点 尽 可 能 远 离 当 前 迭 代 点 . Wolfe步长规则