共轭方向法和共轭梯度法.pdf

邵建峰 最优化理论与方法最优化理论与方法 最优化理论与方法最优化理论与方法 邵建峰 第三章第三章 无约束无约束最优化最优化的梯度的梯度方法方法 信息与计算科学系信息与计算科学系 邵建峰邵建峰 邵建峰 本章内容 本章内容 3 1 3 1 无约束最优化问题的最优性条件无约束最优化问题的最优性条件 3 2 3 2 最速下降法最速下降法 3 3 3 3 NewtonNewton法法 3 4 3 4 共轭方向法和共轭梯度法共轭方向法和共轭梯度法 3 5 3 5 拟拟NewtonNewton法法 3 6 3 6 最小二乘最小二乘问题问题 邵建峰 3 4 3 4 共轭方向法和共轭梯度法共轭方向法和共轭梯度法 信息与计算科学系信息与计算科学系 邵建峰邵建峰 本节内容 本节内容 一一 共轭方向法共轭方向法 二 共轭梯度法二 共轭梯度法 一一 共轭方向法共轭方向法 针对二次函数针对二次函数 s t min 21n xxxfxf n RDx 求使求使 的点的点 0 xf x x k x k xf 1 k x 最速下降法最速下降法是 若已知目标函数是 若已知目标函数 的梯度的梯度 xf xfxg 则选取初始搜索方向与每个当前点处的搜索方向为则选取初始搜索方向与每个当前点处的搜索方向为 kk gp 1 1 最速下降法最速下降法 一一 共轭方向法共轭方向法 针对二次函数针对二次函数 在在 点处 用二次函数来近似原函数点处 用二次函数来近似原函数 即 即 k x xf k xfxQxf 2 1 kk T kk T k xxxGxxxxxg 寻找近似二次函数的寻找近似二次函数的 中心中心 点 即令点 即令 0 kkk xxxGxgxQ 2 2 牛顿法牛顿法 1 1kkkk xgxGxx x k x k xf 1 kkk pG xg x 1 0 TT kkkkk g xpg xG xg x 1kkk xxp 1 1 对对 n 元二次函数元二次函数 1 2 TT f xx Qxb xC 其中其中 RcRbx n Q是 是n阶正定阵 阶正定阵 1 xQ b 0 x 0 p 0001 ptxx 1 xf 1 p 001 pxslx 即即 min 00 0 0001 ptxfptxfxf t 现在令现在令 10 pxx ls Linear search 下面下面 对对 n 元二次函数元二次函数 1 2 TT f xx Qxb xC 0 x 0 p 0001 ptxx 1 xf 1 p 1 p 0 p研究方向研究方向 与与 有什么关系有什么关系 因为因为 minarg 11 0 111 ptxfptxx t 又又 bxQxfxg 0 bxQxfxg 1 2 1 式代入 式代入 2 式 得 式 得 0 111 bptxQ 用用 0 p 与 与 3 3 式两边做内积 有 式两边做内积 有 0 10 pQp T 即即 0 111 pQtxf 3 0 p 1 p Q我们称满足 我们称满足 式的方向 式的方向 是是 共轭共轭的 的 共轭 是 共轭 是 正交正交 概念的推广 概念的推广 minarg 11 0 111 ptxfptxx t 0 bxQxfxg 1 2 0 10 pQp T 定义定义1 1 Q 共轭共轭 设设 Q 为为n阶正定矩阵 阶正定矩阵 p1 p2 pk为为 n 维非零向量组 维非零向量组 如果如果 piT Q pj 0 i j 则称向量组则称向量组 p1 p2 pk关于关于 Q 共扼共扼 实际上 在新的内积意义下 实际上 在新的内积意义下 在空间在空间Rn上 重新定义上 重新定义内积与范数内积与范数 Q T x yyQx 1 21 2 Q T Q xx xx Qx Q 共扼共扼即为即为正交正交 性质性质1 1 线性无关线性无关 设 设 011 m ppp Q是已知的 是已知的 n 阶正定矩阵 阶正定矩阵 的向量组的向量组 必定是必定是线性无关线性无关的的 则则Q共轭共轭 定义定义2 2 线性流型线性流型 0 1 k iii i Lx xxpR 设设 p1 p2 pm 1 是是 m 个线性无关的向量 个线性无关的向量 0 n xR 则称集合则称集合 是由点是由点x0和线性无关向量组和线性无关向量组 p1 p2 pm 1 所产生的一个所产生的一个线性流型线性流型 m 叫做流形的叫做流形的维数维数 显然 在三维空间中 一维流形是显然 在三维空间中 一维流形是直线直线 二维流形是 二维流形是平面平面 而 而 三维流形是三维流形是整个空间整个空间 性质性质2 2 共轭化共轭化 设设 011 m ppp Q 共轭共轭的 的 是已知的是已知的 n 阶正定矩阵 阶正定矩阵 任何线性任何线性 无关的向量组无关的向量组 必定可以必定可以 Q 共轭化 共轭化 即若令即若令 00 pq 0 00 10 11 q qQq pQq pq T T 1 11 21 0 00 20 22 q qQq pQq q qQq pQq pq T T T T 2 22 11 1 11 11 0 00 10 11 m m T m m T T m T T m T mm q qQq pQq q qQq pQq q qQq pQq pq 011 m ppp 则向量组则向量组 Q是是 1 1 2 T b Q b 1 1 2 T cb Q b 共扼方向法的思路共扼方向法的思路 1 min 2 TT f xx Qxb xc 其中其中 RcRbx n Q是 是n阶正定阵 阶正定阵 1 xQ b 则则 因此原问题等价于 因此原问题等价于 12 min QxQ b 12 1 2 QxQ b 11 1 2 T xQ bQ xQ b c 1 2 TT f xx Qxb xc 2 Qxx 在在Rn上 按照上面定义的内积给出一组上 按照上面定义的内积给出一组Q 共扼共扼的的 基底基底 p1 p2 pn 则则 p1 p2 pn 线性无关 且线性无关 且 0 Qij p pij 设问题的最优解设问题的最优解 x Q 1b 在这组基底下的表示为在这组基底下的表示为 x u1 p1 u2 p2 un pn 并任取初始点并任取初始点 x0 s1 p1 s2 p2 sn pn p1上进行一维搜索 上进行一维搜索 即求解问题即求解问题 先在方向先在方向 x0 s1 p1 s2 p2 sn pn x u1 p1 u2 p2 un pn x x0 a1 p1 a1 R s1 a1 p1 s2 p2 sn pn 1 2 1111222 min nnnQ R su psupsup 1 2 min R Q xx 因为因为 所以即求所以即求 2 min Qxx 1 111 2 2221 min nnn R Q supsusupp 1222111 nnn su psupsup 2212111 nnnQ supsupsu p 因为对任意因为对任意 221 2 1211 nQnn supsspuup x0 s1 p1 s2 p2 sn pn x u1 p1 u2 p2 un pn 因为因为 Q T yyQxx Q ab ab 2 TTT QQaaabbQb 2 Q ab T abQ ab 2 Q a 2 Q a b 2 Q b 如果如果 0 Q a b 即向量即向量 a b 是是Q共轭的 共轭的 则有则有 2 Q ab 2 Q a 2 Q b 于是于是 1222111 nnn su psupsup 2212111 nnnQ supsupsu p 2 1111 Qsu p 22 2 2 nnQn supsup 221 2 1211 nQnn supsspuup 从而从而 因为对任意因为对任意 定值定值 x0 s1 p1 s2 p2 sn pn x u1 p1 u2 p2 un pn 1 2 1111 min R Q su p 显然 当显然 当 a1 u1 s1 时 上面的函数取最小值时 上面的函数取最小值 此时此时 x0 x1 u1 p1 s2 p2 sn pn 即即 x1 与最优点在基底中第一个向量与最优点在基底中第一个向量 p1 前的系数达到一致前的系数达到一致 x1也就是也就是二次目标函数二次目标函数在集合在集合 x x x0 a1 p1 a1 R 上的极小点上的极小点 1 111 2 2221 min nnn R Q supsusupp 11 22 11 Qsup 0 1 1 1 2 min x xp R Q xx x0 s1 p1 s2 p2 sn pn x u1 p1 u2 p2 un pn x0 s1 p1 s2 p2 sn pn 即即 x u1 p1 u2 p2 un pn 1 min 2 TT f xx Qxb xc 其中其中 RcRbx n Q是 是n阶正定阵 阶正定阵 1 xQ b 得知 从任取初始点得知 从任取初始点 x0 s1 p1 s2 p2 sn pn出发出发 逐次逐次沿着沿着Q 共扼共扼的的基向量基向量 p1 p2 pn 进行一维搜索 进行一维搜索 最终必将得到二次函数在整个空间最终必将得到二次函数在整个空间 Rn 上的上的极小点极小点 x1 u1 p1 s2 p2 sn pn x2 u1 p1 u2 p2 sn pn 定理定理 共轭方向法的收敛性共轭方向法的收敛性 1 Q 为为 n 阶阶正定矩阵正定矩阵 2 p0 p1 pm 1为一组为一组 n 维维Q 共扼共扼的向量的向量 如果对二次函数如果对二次函数 设设 1 2 TT f xx Qxb xc 从任何初始点从任何初始点 x0 出发 出发 逐次逐次沿着方向沿着方向 p0 p1 pm 1 做做 精确的线性搜索精确的线性搜索 i gTm pj 0 j 0 1 m 1 ii xm是二次函数是二次函数 f x 在在 m 维维线性流型线性流型 1 iii xls x p 0 1 1im 推论推论 1 0 0 m iii i Lx xxpR argmin iiiii t R xtpf xt p 最后得到的点为最后得到的点为 xm 则 则 上的上的极小点极小点 当当 m n 时 时 xn为二次函数在为二次函数在 Rn 上的极小点上的极小点 证明要点证明要点 共扼方向法共扼方向法 用于二次函数用于二次函数 对任意对任意i 只要证明 只要证明gTm pi 0 0 1 1im 211 TTTTTT mimkiiiiii g pggpggpgp 1211 TTT mmiiiiii QxQxpQxQxpgp g xf xQxb 11111 TTT mmiiiiii tpQptpQpgp 1iiii xxtp 1 T ii gp 0 0 T ji p Gp 精确一维搜索精确一维搜索 二 共轭梯度法二 共轭梯度法 共扼方向法共扼方向法有如下前提条件 有如下前提条件 1 Q 为为 n 阶阶正定矩阵正定矩阵 2 p0 p0 pn 1为一组为一组 n 个个 n 维维Q 共扼共扼的向量的向量 1 2 TT f xx Qxb xc 但是但是共扼方向共扼方向向量的产生与向量的产生与负梯度负梯度无关 无关 我们现在构造一种与负梯度方向有关的共轭方向我们现在构造一种与负梯度方向有关的共轭方向 法法 共轭梯度法共轭梯度法 0 10 pQp T 0 10 pQp T 1 1 共轭方向的形成 共轭方向的形成 1 2 TT f xx Qxb xc 其中其中 RcRbx n Q是 是n阶正定阵 阶正定阵 1 xQ b 0 x 0 p 0001 ptxx 1 xf 1 p 001 pxslx 即即 min 00 0 0001 ptxfptxfxf t 现在令现在令 10 pxx ls Linear search 则有则有 00 pg 针对二次函数针对二次函数 bxQxfxg 第一步第一步 00 pg 00 pg 取取 作线性作线性搜索搜索 001 pxslx min 00 0 0001 ptxfptxfxf t 因为因为 000 gg xQxb 111 gg xQxb 其中其中 1000 xxtp 则则 10 0 T g p 0000 0 T Q xtpbp 00000 0 T gt Q pp 00 0 00 T T g p t p Q p 00 100 00 T T g p xxp p Q p 00 0 00 T T g p t p Q p 第二步第二步 当当 1 0 g 产生第二个共轭方向 产生第二个共轭方向 1100 pgp 且且 0 10 pQp T 可解得可解得 00 01 0 pQp pQg T T 又作又作线性搜索线性搜索 211 xls x p 即即 min 11 0 1112 ptxfptxfxf t 对二次函数 同理有对二次函数 同理有 11 1 11 T T g p t p Q p 即即 0100 0 T p Qgp 01000 TT p Qgp Q p 11 211 11 T T g p xxp p Q p 再令再令 00 01 0 pQp pQg T T 第三步第三步 当 当 2 0 g 产生下一个共轭方向 产生下一个共轭方向 令令 22 pg 且且 02 0 T p Q p 12 0 T p Q p 00 p 11 p 于是由于是由 02 0 T p Q p 解得解得 20 0 00 T T g Q p p Q p 01020001 0 TTT p Qgp Qp Qpp 0 T p Q 20011 gpp 0 同理有同理有 21 1 11 T T g Q p p Q p 推导过程推导过程 第三步第三步 当 当 2 0 g 产生下一个共轭方向 产生下一个共轭方向 令令 22 pg 且且 02 0 T p Q p 12 0 T p Q p 00 p 11 p 有有 20 0 00 T T g Q p p Q p 21 1 11 T T g Q p p Q p 又因为又因为 20 gp 21 gp 0 g 100 gp 由由共轭方向法的收敛性共轭方向法的收敛性定理定理 20 gg 21 gg 20 0 T g g 21 0 T g g 推导过程推导过程 第三步第三步 当 当 2 0 g 产生下一个共轭方向 产生下一个共轭方向 令令 22 pg 且且 02 0 T p Q p 12 0 T p Q p 00 p 11 p 有有 20 0 00 T T g Q p p Q p 21 1 11 T T g Q p p Q p 且且 20 0 T g g 21 0 T g g 又因为又因为 000 gg xQxb 111 gg xQxb 1010 ggQ xx 1000 xxtp 00 t Q p 推导过程推导过程 第三步第三步 当 当 2 0 g 产生下一个共轭方向 产生下一个共轭方向 令令 22 pg 且且 02 0 T p Q p 12 0 T p Q p 00 p 11 p 有有 20 0 00 T T g Q p p Q p 21 1 11 T T g Q p p Q p 且且 20 0 T g g 21 0 T g g 又因为又因为 1010 ggQ xx 所以所以 20 T g Q p 00 t Q p 10 0 gg t 0 1 t 2120 TT g gg g 0 即即 0 0 0 0 总之 总之 2 T g 推导过程推导过程 第三步第三步 还是还是令令 2211 pgp 且且 12 0 T p Q p 可解得可解得 21 1 11 T T g Q p p Q p 又作又作线性搜索线性搜索 322 xls x p 即即 322222 0 min t f xf xtpf xt p 对二次函数 同理有对二次函数 同理有 22 2 22 T T gp t p Q p 22 322 22 T T g p xxp p Q p 21 1 11 T T g Q p p Q p 当当 2 0 g 产生下一个共轭方向 产生下一个共轭方向 02 0 T p Q p 推导结论推导结论 共轭梯度算法共轭梯度算法 已知二次目标函数已知二次目标函数 1 2 TT f xx Qxb xc Q 正定正定 终止限终止限 设初始可行点设初始可行点x0 计算计算 00 pg 令令 k 0 Step 1 作线性搜索作线性搜索 1 kkk xls x p 即即 1 0 min kkkkkk t f xf xtpf xt p 对二次函数 同理有对二次函数 同理有 T kk k T kk g p t p Q p Step 2 判别 判别 1k g 是是 打印并停机 打印并停机 否否 令令 11 kkkk pgp 且且 k T k k T k k pQp pQg 1 并并令令 k k 1 转 转step 1 例例1 1 1 12 2 2 1 82 x x x x 22 12 4f xxx 2 8 Q 其中其中 并且并且 1 2 2 8 x g x x 用用共轭梯度法共轭梯度法迭代如下迭代如下 用共轭梯度法求解用共轭梯度法求解 2 2 2 121 4 minxxxxf 解解 Step 1 取初始点取初始点 1 1 0 x 8 2 00 gp 计算线性搜索步长计算线性搜索步长 22 00 0 22 00 2 8 68 0 13077 2 2 8 8 520 T T g p t p Q p 从而从而 001 pxslx 000 ptx 04616 0 73846 0 8 2 13077 0 1 1 且且 36923 0 47692 1 1 g Step 2 因为因为0 1 g 计算 计算 03408 0 520 72304 17 00 01 0 pQp pQg T T 并产生并产生共轭方向共轭方向 09659 0 54508 1 0011 pgp 不难验证不难验证 0 10 pQp T 计算线性搜索步长计算线性搜索步长 11 1 11 2 31762 0 47794 4 89918 T T g p t p Q p 所以所以 0 0 1112 ptxx 且 且 0 0 2 g 算法终止 算法终止 对对 n 元二次函数 元二次函数 共轭梯度法共轭梯度法迭迭代二步收敛代二步收敛 2 2 对一般目标函数 对一般目标函数 为了使算法能用于非二次函数 为了使算法能用于非二次函数 要消去算法要消去算法step 2 k T k k T k k pQp pQg 1 中的矩阵中的矩阵 Q 因为因为 bxQxfxg minarg 0 1kk t kkkk ptxfptxx 所以所以 1 kkkk ggtQ p 即即 1 kk k k gg Q p t 代入代入上面上面式式子子中 则有中 则有 11 1 T kkk k T kkk ggg pgg 11 1 T kkk k T kkk ggg pgg 11kkkk pgp 11 1 T kkk k T kkk ggg pgg 11kkkk pgp 又又 0 1111 kkk T kk T k pgggp 1111 k T kkk T k pggg 由由 11 0 T kk gp 1 0 T kk gg 并且并且 1 0 T kk gg 1