111111111111111111111111111111第九组 10.16.pptx

11

1. 可行方向法 汇报：第九组 金小越 卢青莹 王素婷 黄越伶 石佳颖

2. Zoutendijk 可行方向法 线性约束情形 01 汇报人：金小越

3. 可行方向法：线性约束部分 03

4. 可行方向法：线性约束部分 04

5. 可行方向法：线性约束部分 05

6. 可行方向法：线性约束部分 06

7. 可行方向法：线性约束部分 07

8. 可行方向法：线性约束部分 08

9. 可行方向法：线性约束部分 09

10. 可行方向法：线性约束部分 10

11. 可行方向法：线性约束部分 11

12. 可行方向法：线性约束部分 12

13. 可行方向法：线性约束部分 13

14. 可行方向法：线性约束部分 14

15. Zoutendijk 可行方向法 非线性约束情形 02 汇报人：卢青莹

16. 第二部分： 约束为非线性函数的非线性规划问题

17. 第二部分：约束为非线性函数的非线性规划问题的可行方向

18. 第二部分： 约束为非线性函数的非线性规划问题的可行方向

19. 第二部分： 约束为非线性函数的非线性问题的可行方向

20. 第二部分： 约束为非线性函数的非线性规划问题的步长因子

21. 第二部分：约束为非线性函数的非线性规划 的可行方向法计算步骤

22. 第二部分：约束为非线性函数的非线性规划 的可行方向法计算步骤

23. 第二部分：约束为非线性函数的非线性规划 的可行方向法计算步骤

24. Rosen 梯度投影法 汇报人：王素婷 03

25. 第三部分： Rosen 梯度投影法 在空间 中，给定一个行满秩矩阵 ，即 。矩阵 的 个行向量生成一个子空间 ，其正交补记为 。对于任意向量 ，它可以唯一分解为：     其中： 是 在子空间 上的投影， 是 在子空间 上的投影。       向量 在子空间 上的投影矩阵 定义为：    

26. 第三 部分： Rosen 梯度投影法 设 是一个 的矩阵，且秩为 （即行满秩）， 是任意 维向量。定义两个投影矩阵：   投影矩阵 : 投影矩阵 :   矩阵 和 都具有以下两个特性： 对称性： 幂等性：   对称性证明 由于 是对称矩阵（即 ） ， 其逆矩阵也对称，因此： 于是：   幂等性证明 由于 因此：  

27. 第三 部分： Rosen 梯度投影法 设 是一个 矩阵，若满足 且 ，被称 为一个 投影矩阵（ Projection Matrix ） 。   介绍投影矩阵的三个核心性质： 性质一：投影矩阵是半正定矩阵 陈述： 若 为投影矩阵，则 是 半正定矩阵 。 证明： 对任意向量 ， 有： 推导中使用了 和 。 由于 ， 根据定义，矩阵 为半正定矩阵。   性质二：互补矩阵也是投影矩阵 陈述： 为投影矩阵的 充要条件 是它的互补矩阵 也是投影矩阵。  

28. 第三部分： Rosen 梯度投影法 性质三：正交子空间分解 陈述： 投影矩阵 和其互补矩阵 分别将空间投影到两个 正交的子空间 和 上。 定义子空间：   性质 3.1 ：子空间正交性 子空间 和 是相互正交的。 证明： 对于任意 和 ， 有： 推导中使用了 和 。 因此 。   性质 3.2 ：空间的唯一直和分解 任意向量 都可以 唯一地 分解为两个正交分量之和： 分解方式： 唯一性： 由于 与 正交，这种分解是唯一的。  

29. 问题陈述（仅线性约束） 考虑如下约束优化问题： 其中： 为可微函数， 是 矩阵， 是 矩阵， 与 分别为 m 维与 l 维列向量。   求下降可行方向 定理 12.2.1 ： 设 是上面问题的可行解，在点 处有： ，其中： 又设矩阵： 为满秩矩阵。定义投影矩阵： 若 ， 令： 则 是一个 下降可行方向 。   在梯度投影法中，若迭代点位于可行域内部，则沿负梯度方向下降；若位于约束边界上，则将负梯度投影到矩阵 的零空间中。矩阵 由当前起作用的约束梯度组成。   第三部分： Rosen 梯度投影法

30. 证明 由于 为投影矩阵，且 ， 则有： 因此， 是 下降方向 。 又由于： 即： 根据 定理 12.1.1 ， 是在点 处的 可行方向 。 可知 是 下降可行方向 。   在 的假设下， 该定理给出了用投影矩阵求解下降可行方向的一种方法。 当 时，有两种可能： 是 K-T 点； 可以构造新的投影矩阵 ，以继续求得下降可行方向。   第三部分： Rosen 梯度投影法

31. 定理 12.2.2 设 是问题的一个可行解，在点 处，有 ，其中 又设 为行满秩矩阵，令 其中 和 分别对应于 与 , 设 ， 则： 若 ，则 为 K–T 点； 证明 设 。由 得 该式即为 K–T 条件，因此𝑥为 K–T 点。 若 中含有负分量（设 ）， 这时从 中去掉 对应的行，得到 令 那么 为下降可行方向。   第三部分： Rosen 梯度投影法

32. 给定初始可行点 ，置 . 在点 处 , 将 和 分解成 ， ，使得 令 ，如果 是空的，则令 （单位矩阵）；否则，令 . 令 . 若 ，则转步骤 (6) ；若 ，则进行步骤 (5). 若 是空矩阵，则停止计算，得到 ；否则，令 . 若 ，则停止计算， 为 K–T 点；若 包含有负分量，选择一个负分量，比如 ，修正 ，去掉 中对应 行，返回步骤 (3). 求解一维搜索问题，得到最优解 . 令 ，置 ，返回步骤 (2).   其中 计算步骤 第三部分： Rosen 梯度投影法

33. 既约梯度法 汇报人：黄越伶 04

34. 既约梯度法 —— 介绍 介绍 ： 1963 年， Wolfe 将 线性规划的单纯形法 推广到具有非线性目标函数的问题，提出了产生可行下降方向的另一类方法，称为 既约梯度法 。 问题： （ 3.1.1 ） 考虑问题 （问题 3.1 ） （ 3.1.2 ） （ 3.1.3 ） 其中， A 为 m × n 矩阵 , m ≤ n, b ∈ R m , x ∈ R n .

35. 既约梯度法 —— 基本原理 基本原理 （ 1 ）用既约梯度构造可行下降方向 假设问题 （ 3.1 ）的约束是非退化的，且 Rank(A)=m ， ， 其中， B 是基矩阵， N 非基矩阵， x B 是基变量列， x N 非基变量列 （ 3.2.1) （ 3.2.2 ） ( 问题 3.2) (3.2.2) （问题 3.3 ） ⇘ ⇘ ⇘

36. 既约梯度法 —— 基本原理 (3.3.1) （ 3.3.2 ） （问题 3.3 ） （ 3.3.3 ） 这是一个 n-m 维问题 ，而且除变量非负约束外不带其它约束条件，因此，问题（ 3.3) 是比原来问题较低维的简单问题。 的梯度，即 f(x) 的既约梯度为： （ 3.4 ）

37. 既约梯度法 —— 基本原理 根据前面的定理，非零向量 d 为 x 处的可行下降方向的 充要条件 ： ( 3.5) (3.6) d Nj 0 , 当 x Nj =0 时 (3.7) 分解 d 为： ≥ ⇘ ⇘ ⇘ ⇘

38. 既约梯度法 —— 基本原理 当 d j ≥ 0, 当 时 （ 3.8 ） （ 3.9 ） （ 3.10 ） 如果取 ，则（ 3.10 ）式成立， d 为下降方向。但是，当某个分量 时，导致（ 3.8 ）式不成立，破坏了可行性 Wolf 的修正式 (3.11) 此修正式可能会使算法收敛到非 K-T 点

39. 既约梯度法 —— 基本原理 Mc Cormick 的修正式 可行下降方向 d 满足 结论：

40. 既约梯度法 —— 基本原理 （ 2 ）确定一维搜索步长 当迭代点 x B ≥ 0, 为保持 ，即确定 ℷ ≥0 的范围，使得 （ 3.14 ） (3.15) (3.16) 一维搜索问题

41. 既约梯度法 —— 算法步骤 算法步骤 step1 step2 step3 step4 step5 setp6 得到最优 即公式（ 3.15 ）

42. Frank-Wolfe 方法 一、算法 二、 Frank-Wolfe 算法的收敛性 05 汇报人：石佳颖

43. Frank-Wolfe 方法 1956 年， Frank 和 Wolfe 提出了一种求解线性约束问题的算法，其基本思想是将目标函数作 线性近似 ，通过求解 线性规划 求得可行下降方向 , 并沿该方向在可行域内作 一维搜索 . 这种方法又称作 近似线性化方法 . 二、问题 考虑 非线性规划问题 其中 是 矩阵，秩为 是 维列向量 ， 是连续可微函数 ， ．我们把这个问题的可行域记作   一、算法简介

44. Frank-Wolfe 方法 假设已知可行点 （ 当前迭代点） , 我们将 在 展开，并 用一阶 Talor 式 其中： 是函数在当前点的值。 是函数在当前点    处的梯度（一个向量）。 是从当前点到任意点  的方向向量。 是梯度和方向向量的内积，代表了函数在这个方向上的变化率。   三 、基本原理 （ 1 ）近似线性化 线性部分 常数项，不会影响最优化问题的解

45. Frank-Wolfe 方法 去掉目标函数的常数项，将问题改写   三、基本原理 （ 1 ） 近似线性化 线性部分 常数项，不会影响最优化问题的解 线性函数 线性约束 线性规划问题  

46. Frank-Wolfe 方法 假设此问题存在有限最优解 ，由线性规划的基本性质可知 ，这个 最优解可在某极点 达到 ，即 是 可行域 S 的一个极点   三、基本原理 （ 2 ）可行下降方向 线性规划问题 S 最优解     可行方向 d

47. Frank-Wolfe 方法 假设此问题存在有限最优解 ，由线性规划的基本性质可知 ，这个 最优解可在某极点 达到，即 是可行域 S 的一个极点 求解线性规划问题的结果： 停止 迭代， 原来 问题的 K-T 点。（ d 与梯度垂直， 沿 d 这个方向走目标函数值不会变）   三、基本原理 （ 2 ）可行下降方向 S 最优解     可行方向 d 梯度 可行方向 d

48. Frank-Wolfe 方法 求解线性规划问题的结果： (2) ，由于 ，则 , 则 d 与梯度的夹角大于 90 度， d － 是 下降方向 由于 是凸集 ， 是 S 的极点 ，连结 与 的线段必含于 S ， 即对每一个 λ∈ ［０ ，１］ ， 有 λ ＋ （１ － λ ） ＝ ＋ λ （ － ） ∈ S ， 因此 － 是 可行方向 d= － 可行下降方向   三、基本原理 （ 2 ）可行下降方向 S 最优解     可行方向 d

49. Frank-Wolfe 方法 － 可行下降方向 这时，从 出发，沿此方向作一维搜索： 解这个一维数组问题，从而得到步长 － 且为下降方法 得到 再重复以上过程   三、基本原理 （ 3 ）一维搜索 S 最优解     可行方向 d

50. Frank-Wolfe 方法 四 、算法步骤 Step1 选取初始数据 . 选取初始可行点 ，允许误差 ，令 Step2 求解近似线性规划 . 求解线性规划问题 得最优解 Step3 构造可行下降方向 , 若 ，停止计算，输出 ；否则， 为可行下降方向，转 step4 Step4 进行一维搜索 . 求解 , 得最优解 ，令 ， , 转 step2  

51. Frank-Wolfe 方法的收敛性 设 是线性规划的最优解，且满足 则 是问题的 K-T 点。 其中： K-T 点是满足优化问题的 Karush-Kuhn-Tucker 条件的解，这些条件包括原始可行性、对偶可行性、互补松弛性和梯度零条件。 K-T 点 是局部最优解的必要条件。   一、定理 1

52. Frank-Wolfe 方法的收敛性 其中： 一、定理 2

53. Frank-Wolfe 方法 Frank-Wolfe 算法是一种 可行方向法 . 使用这种方法，在每次迭代内， 搜索方向总是指向某个极点 ，并且当迭代点接近最优解时，搜索方向与目标函数的梯度趋于正交，这样的搜索方向并非最好的下降方向，因此算法收敛速度比较慢 . 但是，这种方法 把求解非线性最优化问题转化为为求解一系列线性规划问题 ，而且各线性规划具有相同的约束条件，因而该方法在实际应用中仍然是一种有用的算法，在某些情形下，也能收到较好计算效果

54. 小组分工 金小越： zoutendijk 方法 - 线性约束部分 PPT 制作 + 讲解 卢青莹： zoutendijk 方法 - 非线性约束部分 PPT 制作 + 讲解 王素婷： Rosen 梯度投影法 部分 PPT 制作 + 讲解 黄越伶： 既约梯度法 部分PP T 制作 + 讲解 石佳颖： Fran k-Wolfe方法 PPT制作 + 讲解

55. 谢谢各位！ 导师：小北