11111111111111111111111111111111111第十组10.16.pptx

111

1. 非线性最优化 约束优化问题 汇报人：第十组 汇报时间： 2025.10.16

2. 目录 /CONENTS 罚函数法 01 广义乘子法 02 等式约束二次规划 03 起作用集法 04 Wolfe 算法 05 Lemke 算法 06

3. 罚 函 数 法 内罚函数 & 外罚函数 01

4. 引言

5. 罚函数法

6. 罚函数法

7. 外罚函数法

8. 求解 - 采用外罚函数法

9. 内罚函数法

10. 求解 - 采用内罚函数法

11. 优势与问题

12. 广义乘子法 02

13. 广义乘子法 ： 超越罚函数的优化 罚 函数法 ：罚 通过 惩罚，迫使解回到可行域。 广义 乘子法 ：罚 + 引导 增加 一个乘子更智能地引导搜索 乘子 缺点： 1 、 σ 很大时， Hess e 矩阵条件数很大，数值计算困难 2 、 σ 为有限值时，解不满足约束 想要 一个在 有限 惩罚系数下就能得到精确解的方法 如何将约束问题转换成无约束问题？

14. 广义乘子法公式的提出 考虑构造 一个新的函数，使 x* = argminΨ （ x,σ* ） 同时保证 σk 适中，避免 Hesse 阵病态而引起的极小点求值困难 KKT 条件之一： 对 x 求导结果= Hesse阵要正定 期望 x* 也是构造 Ψ 函数 的局部（最小）解 局部最小解 拉格朗日函数在切空间上是正定的， 但 在 N 维空间不一定是正定的 。 因此， 构造广义乘子法（增广拉格朗日函数）

15. 等式约束问题的乘子法 分析：对 x 求导= 比较 ： 算法核心：乘子 迭代公式 算法停止条件

16. 例题 乘子法 不要求 σ 趋于无穷大，只要求大于某个整数

17. 一般约束问题的乘子法 思路： 不等式变等式 c(x) <= 0 变换成 c(x) + z （ x ）= n + 2p 维 = > 降维！！ n + p 维 提取z 相关的

18. 一般约束问题的乘子法 求关于 z 的极小值，关于 z 求导= 乘子 迭代公式 终止准则

19. 例题 f(x) = x ₁² + x ₂² g(x) = x ₁ - 1 ≥ 0 第一步：转化为标准形式 将不等式约束改写为 ≤ 0 形式： g(x) = 1 - x ₁ ≤ 0 第二步：构造增广拉格朗日函数 ： L(x, λ, σ) = f(x) + (1/(2σ)) * { [max(0, λ + σ g(x))] ² - λ ² } L(x, λ, σ) = x ₁² + x ₂² + (1/(2σ)) * { [max(0, λ + σ(1 - x ₁ ))] ² - λ ² } 第三步：第 k 次迭代的求解，分别对 x1 、 x2 求导= 当 λ (k) +σ(1−x1 )≥0 时 当 λ (k) +σ(1−x1 )＜0 时 最里面 括号内- >0 解得 λk = 2 因此， x1 = 1 ， x2 = x* = [1 ， 0]T

20. 等式约束二次规划 03

21. 等式约束二次规划的定义 x 为决策变量 G 为对称矩阵（一般考虑 G≥0 ） A 为约束矩阵，   标准形式 KKT 法 变量消去法 零空间法等 常用求解方法

22. 等式二次约束问题的最优性条件 -KKT 条件 在 约束 Ax=b 下，只能沿满足Ad=0的方向d移动 若x*是 局部极小点 ，那么目标函数在可行方向上 不能下降 梯度与所有可行方向正交，即： f(x* ) ⊤ d=0 对所有 d 满足 Ad=0 f(x*)∈(Null(A)) ⟂ 由线性代数中的 正交补定理 可知 (Null(A)) ⟂ =Range(A ⊤ ) 因此，存在某个λ，使得： f(x*)=A ⊤ λ 结合约束Ax=b，得到 KKT条件 ： Gx+c+A T λ=0 Ax=b 将KKT条件写成 矩阵乘积 的形式，即： 方法的缺点：当n和m都非常大的话，求解问题将 非常复杂    

23. 等式约束二次规划例题

24. 起作用集方法 04

25. 起作用集方法概念与定义 起作用集概念 一个小思考 我们在前面讲的等式约束二次规划（ EQP ），只能处理严格的等式条件。 但现实优化问题中，常常还要考虑 “ 不超过 ”“ 非负 ” 等不等式条件。 在最优点处，有些约束 “ 紧贴 ” ， 有些 “ 松弛 ” 。 这组 “ 紧贴 ” 的约束集合，就是 起作用集（ Active Set ） 比如  

26. 几何角度理解起作用集方法 最优点在可行域内 => 无约束起作用 => 起作用集为空 最优点在可行域边界 => 边界即为起作用集 最优点在可行域外 => 真正的最优点在离最优点函数值最近的可行域边界上 => 对应的边界为起作用集 Case 1:Interlor optimum-INTERIOR Case2:Boundaryoptimum- BOUNDARY Case 3: Unconstrained minimizer outside -》 pushed to boundary - BOUNDARY 几何 角度

27. 数学角度理解起作用集方法 步骤一：初始化 选择一个初始可行点 （满足所有等式约束和不等式约束）； 构造初始起作用集 ，包含： 所有在 处取等号的不等式约束 （即 ）。   步骤三：判断是否是最优解 （ 1 ） 若 =0 （即无下降可行方向），说明当前点在起作用集约束子空间中已是最优点； 此时需要检查对起作用约束的乘子是否满足互补松弛条件： 起作用的不等式约束，对应的乘子 ≥0 ； 若所有乘子非负，则当前点满足 KKT 条件，算法终止； 若存在某个起作用不等式约束对应的   <0 ，说明该约束不应在起作用集中，将其移除，并返回步骤二（重新求解子问题）。 （ 2 ） 若 ≠0 ，进行线性搜索； 从当前点沿方向 移动： + α ； 由于 满足 ，所以起作用约束仍被满足； 但松弛约束可能被违反，因此需确定最大步长 α max​ ，使得所有不等式约束仍满足： 如果 ，那么说明沿这个方向永远不会破坏约束，则问题无下界 否则，取步长 （或略小于它），得到新点： （ 3 ） 若在该步长下有新的不等式约束变为等式（即 “ 碰到 ” 边界），将其加入起作用集   更新迭代，返回步骤二   步骤二：在当前起作用集下求解子问题 构造子问题，可行方法搜索： 求解得到搜索方向   数学 角度

28. Wolfe 算法 05

29. Wolfe 算法背景及思想 “Wolfe 算法 ” 通常指为了找到满足 Wolfe 条件的步长 α 而设计的迭代程序。 Wolfe 算法的核心思想是 通过线搜索确定 在每一步迭代中最优的步长，以便有效地沿着当前的搜索方向更新解。它特别用于无约束优化问题中，结合梯度下降法或牛顿法来优化目标函数。 具体而言， Wolfe 条件用于指导 线搜索的过程，保证所选步长能够有效改善目标函数，并确保迭代收敛。 算法背景 算法思想

30. Wolfe 算法的黄金准则 充分下降条件 (Armijo 条件 ) 曲率 条件 弱 强

31. Wolfe 算法的黄金准则 曲率 条件（强） 曲率 条件（例）

32. Wolfe 算法步骤 括号 搜索（ Bracketing ） 目标：在已经找到的括号区间 [α low ，α high ] 内，通过不断插 值，高效地找到一个满足所有条件的步长 1. 插值：在区间 [α low ，α high ] 内，利用二次或三次插值等方 法，生成一个新的试探步长 α j 2. 检查 Armijo 条件：如果不满足，或者 说明步长太大，设置 α high = α j 3. 如果满足 Armijo 条件，则检查曲率条件： ①如果满足，那么这个 α j 就是可接受的，算法成功结束 ②如果不满足，说明 α j 还是太短。检查 ，如果它为 负，更新左端点，设置 α low = α j ，否则令 α high = α j 3. 循环步骤 1 和 2 ，直到找到一个满足条件的步长，或区间 变得非常小   目标：快速找到一个区间 [α low ，α high ] ，这个区间必然包含满足 Wolfe 条件的可接受步长 标志：区间左端 α low 满足 Armijo 条件且斜率向下，右端 α high 不满足 Armijo 条件或斜率向上 1. 初始化：设定一个初始步长α，并设置α low = 2. 检查 Armijo 条件：如果 ，说明步长太长，函数值没有充分下降。 此时，我们找到了区间的右端点，令 α high = α ，然后跳转到精细搜索阶段 3. 如果 Armijo 条件满足，则检查曲率条件 如果满足，那么这个 α 就是可接受的，算法成功结束 如果不满足，分两种情况： ①如果 ，说明已经越过局部极小点。此时，令 α high = α ，进入精细搜索阶段 ②如果 ，说明当前点坡度仍然很陡，步长太短，还有很大的下降空间。此时， 更新左端点，令 α low = α ，然后选择一个更大的步长继续尝试，回到第 2 步开头   精细搜索（ Zoom ）

33. Lemke 算法 06

34. Lemke 算法背景及思想 算法背景 Lemke 旨在求解线性互补问题，其标准形式如下： 给定矩阵 和向量 ，寻找向量 使得： 其中， 为互补性条件，等价于分量形式 对所有 i 成立。 这意味着对于每一对互补变量 ，至少有一个为零。   算法思想 Lemke 算法的核心思想可概括为：通过引入一个人工变量，将原始的互补问题转化为一个易于启动的辅助问题，随后沿着一条称为“几乎互补路径”的边界路径进行系统搜索，直至找到解。

35. Lemke 算法的关键点 人工变量启动 Lemke 算法引入一个非负人工变量  z ，构造辅助 LCP ： 这使得我们可以从一个平凡的基可行解（如  z=0, = 0, ​  足够大使  ）开始。在此起点，除了    没有互补变量外，所有原始互补对  均满足互补性。这种状态称为几乎互补。   几乎互补路径 算法在迭代过程中，始终维持一种“几乎互补”的状态。即，在  n  对原始互补变量中，始终有  n−1 对严格满足互补性（一个在基中为正，另一个不在基中为零），而有一对是“异常”的（当前正在被驱动的变量及其互补变量）。算法被限制在由这种几乎互补基定义的可行域边界的一维路径上移动。 强制性互补转轴 算法的移动规则是强制性的，而非启发式的。在每一步，当前驱动变量的增加会导致另一个变量下降至零（阻塞变量）。算法规则强制要求：新的驱动变量必须是刚刚变为零（离开基）的那个变量的互补变量。这种“互补跳转”规则确保了路径的几乎互补性得以保持。算法的终极目标是通过一系列互补转轴，最终将人工变量  驱离基（即使其值降为 ）。一旦  = 0 ，我们便得到了原始 LCP 的一个解。  

36. Lemke 算法步骤 步骤一：初始化 1. 构造辅助 LCP ： 2. 设置初始基：令 = 0 计算 确保 3. 初始基变量为 和 ，非基变量为 。 4. 选择第一个驱动变量：通常，选择在初始解中值最小的 所对应的互补变量 作为第一个进入基的变量（这等价于开始减小 时最先阻塞的变量）。设这个变量为 ，令驱动变量 =   步骤 三 ： 输出 成功终止时，输出解   射线终止时，报告失败   步骤 二 ： 主循环（互补转轴） 重复以下步骤直到终止： 1. 确定阻塞变量： 增加当前驱动变量的值，同时调整其他基变量的值以保持等式约束。 通过最小比值检验确定哪个基变量最先下降到零。该变量即为“阻塞变量” 如果没有任何变量阻塞（即驱动变量可无限增加），则算法射线终止，表明无解或算法失败 2. 检查终止条件： 如果阻塞变量是 ，则进行转轴操作，让驱动变量进入基， 离开基。此时 = 0 ，算法成功终止。当前的 （忽略 ）即为 LCP 的解 3. 执行互补跳转： 如果阻塞变量是某个 （或 ），则其互补变量 （或 ）必须成为新的驱动变量 进行转轴操作：让新的驱动变量进入基，阻塞变量离开基。 更新当前驱动变量为这个新进入的互补变量。  

37. 谢谢大家观看 李欣怡 ： 内 & 外罚函数 戴飞扬 ： 广义乘子法 代玥 ： 等式约束二次规划 & 起作用集法 谷宇晴 ：Wolfe 算法 & Lemke 算法 汇报人：第十组