其中 $ \nabla c(z) = [x_2, x_1]^T $。

 化简目标： $ -2d_1 -4d_2 $。
 约束条件： $ d_1 \geq -1, d_2 \geq 0, d_2 \leq 0.1, |d_1| \leq 0.5, |d_2| \leq 0.5 $。
 由于目标是最小化，且 $ d_2 $ 的系数为-4（负），我们希望 $ d_2 $ 尽可能大以减小目标函数值。约束条件中 $ d_2 $ 的上界是0.1，下界是0，所以取 $ d_2 = 0.1 $ 最佳。对于 $ d_1 $，系数为-2，我们希望 $ d_1 $ 尽可能大。约束条件为 $ d_1 \geq -1 $ 且 $ |d_1| \leq 0.5 $，所以最大可取 $ d_1 = 0.5 $。
 因此，最优解为 $ d^0 = (0.5, 0.1) $。

 化简约束： $ d_1 \geq -1.5, d_2 \geq -0.1, 0.1 d_1 + 1.5 d_2 \leq -0.05 $。
 目标是最小化 $ -d_1 -3.8 d_2 $，我们希望 $ d_1, d_2 $ 尽可能大，但它们受到最后一个线性不等式的限制。这是一个小线性规划，我们可以图解法或单纯形法求解。为了满足 $ 0.1 d_1 + 1.5 d_2 \leq -0.05 $ 并使目标最小，可以取边界 $ 0.1 d_1 + 1.5 d_2 = -0.05 $，并最大化 $ d_1, d_2 $。
 假设我们先最大化 $ d_2 $。从等式解出 $ d_1 = -0.5 -15 d_2 $。代入约束 $ |d_1| \leq 0.75 $ 和 $ d_2 \leq 0.75 $。同时 $ d_2 \geq -0.1 $。目标函数变为 $ -(-0.5-15d_2) -3.8 d_2 = 0.5 + 15d_2 -3.8 d_2 = 0.5 + 11.2 d_2 $。由于系数11.2>0，所以 $ d_2 $ 越大，目标函数值越大（注意我们在最小化，所以这不利）。因此，我们应该最小化 $ d_2 $。在约束下，最小 $ d_2 = -0.1 $（下界）。代入等式得 $ d_1 = -0.5 -15*(-0.1) = 1.0 $，但这违反了 $ |d_1| \leq 0.75 $。所以我们需要满足 $ |d_1| \leq 0.75 $，即 $ -0.75 \leq d_1 \leq 0.75 $。从等式 $ d_1 = -0.5 -15 d_2 $ 和 $ d_1 $ 的范围，可以解出 $ d_2 $ 的范围。当 $ d_1 = 0.75 $ 时， $ d_2 = (-0.5 - 0.75)/15 = -1.25/15 \approx -0.0833 $。当 $ d_1 = -0.75 $ 时， $ d_2 = (-0.5 + 0.75)/15 = 0.25/15 \approx 0.0167 $。所以 $ d_2 $ 的范围大约在 [-0.0833, 0.0167] 之间。目标函数 $ -d_1 -3.8 d_2 $，代入 $ d_1 = -0.5 -15 d_2 $，目标变为 $ -(-0.5-15d_2) -3.8 d_2 = 0.5+15d_2 -3.8d_2 = 0.5 + 11.2 d_2 $。由于系数11.2>0，为使目标最小，应取最小的 $ d_2 $，即 $ d_2 = -0.0833 $，对应的 $ d_1 = 0.75 $（边界）。再检查其他约束： $ d_1=0.75 \geq -1.5 $， $ d_2=-0.0833 \geq -0.1 $？不， $ d_2 = -0.0833 > -0.1 $，所以满足。因此，最优解约为 $ d^1 = (0.75, -0.0833) $。

非线性规划中的松弛线性规划法（Relaxed Linear Programming Method）进阶题：处理具有互补约束的数学规划问题（MPCC） 题目描述 考虑如下 具有互补约束的数学规划问题 （Mathematical Program with Complementarity Constraints, MPCC）： \[ \begin{aligned} \min_ {x,y} \quad & f(x,y) \\ \text{s.t.} \quad & g_ i(x,y) \leq 0, \quad i = 1, \dots, m, \\ & h_ j(x,y) = 0, \quad j = 1, \dots, p, \\ & 0 \leq G_ k(x,y) \perp H_ k(x,y) \geq 0, \quad k = 1, \dots, q. \end{aligned} \] 其中，\( x \in \mathbb{R}^n, y \in \mathbb{R}^l \) 是决策变量，目标函数 \( f: \mathbb{R}^{n+l} \to \mathbb{R} \) 和约束函数 \( g_ i, h_ j, G_ k, H_ k: \mathbb{R}^{n+l} \to \mathbb{R} \) 都是连续可微的。问题中的核心难点在于 互补约束 （Complementarity Constraints）： \[ 0 \leq G_ k(x,y) \perp H_ k(x,y) \geq 0, \quad k = 1, \dots, q. \] 它的含义是，对于每个 \( k \)，必须同时满足 \( G_ k \geq 0 \)， \( H_ k \geq 0 \)，并且 \( G_ k \cdot H_ k = 0 \)。这意味着对于每一对 \( (G_ k, H_ k) \)，至少有一个必须为0（即“互补松弛”）。这种约束使得可行域非凸、甚至不连通，标准约束规范（如MFCQ）在可行点处常常不成立，因此传统的非线性规划算法（如SQP）直接应用会失效。 你的任务 ：使用 松弛线性规划法 （Relaxed Linear Programming Method, RLPM）来求解此MPCC问题。该方法的核心思想是将互补约束用一系列参数化的松弛约束来近似，从而将原问题转化为一系列更容易处理的非线性规划子问题，通过逐步收紧松弛参数来逼近原问题的解。 我们将通过一个具体实例来理解该方法。考虑如下MPCC问题： \[ \begin{aligned} \min_ {x_ 1, x_ 2} \quad & (x_ 1 - 2)^2 + (x_ 2 - 2)^2 \\ \text{s.t.} \quad & x_ 1 \geq 0, \quad x_ 2 \geq 0, \\ & 0 \leq x_ 1 \perp x_ 2 \geq 0. \end{aligned} \] 这个问题直观上要求 \( (x_ 1, x_ 2) \) 位于第一象限，但两者不能同时为正（互补性），目标是最小化到点(2,2)的距离平方。 解题过程 我们将循序渐进地讲解松弛线性规划法的步骤。 第1步：理解原问题与互补约束 互补约束分析 ：约束 \( 0 \leq x_ 1 \perp x_ 2 \geq 0 \) 意味着： \( x_ 1 \geq 0 \) 且 \( x_ 2 \geq 0 \)。 \( x_ 1 \cdot x_ 2 = 0 \)。 因此，可行点只能是坐标轴上的非负部分，即 \( \{ (x_ 1, 0) \mid x_ 1 \geq 0 \} \cup \{ (0, x_ 2) \mid x_ 2 \geq 0 \} \)。 几何解释 ：可行域是两条射线。目标函数是到(2,2)的距离平方。显然，最近的可行点是(0,0)、(2,0)或(0,2)？计算可知： \( f(0,0) = 8 \) \( f(2,0) = 4 \) \( f(0,2) = 4 \) 所以，最优解为 \( (2,0) \) 或 \( (0,2) \)，最优值为4。这是一个非凸、不连通的可行域上的优化问题。 第2步：引入松弛变量，构造松弛问题 松弛线性规划法的核心是引入一个 松弛参数 \( t > 0 \)，将互补约束 \( G_ k H_ k = 0 \) 放松为不等式约束 \( G_ k H_ k \leq t \)。但更常见且数值稳定的方式是引入松弛变量 \( s_ k \geq 0 \)，将互补约束重写为： \[ G_ k(x,y) \geq 0, \quad H_ k(x,y) \geq 0, \quad G_ k(x,y) H_ k(x,y) \leq s_ k, \quad s_ k \geq 0. \] 然后，我们希望 \( s_ k \) 尽可能小。但 \( G_ k H_ k \) 是非线性的，不利于构造线性规划子问题。因此，另一种更“线性”的松弛方式（适用于RLPM）是： 将互补约束 \( 0 \leq G_ k \perp H_ k \geq 0 \) 替换为： \[ G_ k(x,y) \geq 0, \quad H_ k(x,y) \geq 0, \quad G_ k(x,y) + H_ k(x,y) \leq t. \] 其中 \( t > 0 \) 是松弛参数。注意，当 \( t=0 \) 时， \( G_ k+H_ k \leq 0 \) 结合非负性迫使 \( G_ k = H_ k = 0 \)，这比原互补约束更强（原互补允许一个为正，一个为0）。所以这种松弛可能会“过紧”，但通过迭代调整 \( t \)，可以逐渐逼近。 对于我们的例题，互补约束是 \( x_ 1 \geq 0, x_ 2 \geq 0, x_ 1 x_ 2 = 0 \)。我们采用另一种常见且适合线性化的松弛形式： 引入一个小的正数 \( \epsilon > 0 \) 作为松弛参数，将互补约束放松为： \[ x_ 1 \geq 0, \quad x_ 2 \geq 0, \quad x_ 1 \cdot x_ 2 \leq \epsilon. \] 这样，当 \( \epsilon = 0 \) 时，恢复原互补约束；当 \( \epsilon > 0 \) 时，允许 \( x_ 1 \) 和 \( x_ 2 \) 同时为正，但只要乘积不超过 \( \epsilon \)，它们不能同时“太大”。这种方法称为“乘积形式松弛”。 第3步：构造序列线性规划（SLP）子问题 松弛线性规划法是一个 序列线性规划 方法。在每一步迭代 \( \nu \) 中，我们有一个当前迭代点 \( z^\nu = (x_ 1^\nu, x_ 2^\nu) \) 和一个当前的松弛参数 \( \epsilon_ \nu > 0 \)。我们在当前点对目标函数和约束进行 一阶泰勒展开（线性化） ，构造一个线性规划（LP）子问题。 在当前点 \( z^\nu \) 处线性化 ： 目标函数 \( f(x) = (x_ 1-2)^2 + (x_ 2-2)^2 \)，其梯度为 \( \nabla f(x) = [ 2(x_ 1-2), 2(x_ 2-2) ]^T \)。 线性近似： \( f(z) \approx f(z^\nu) + \nabla f(z^\nu)^T (z - z^\nu) \)。由于我们只关心最小化方向，常数项 \( f(z^\nu) \) 可忽略，因此线性化目标为： \( \nabla f(z^\nu)^T (z - z^\nu) \)。 约束 \( x_ 1 \geq 0, x_ 2 \geq 0 \) 已是线性，保持不变。 松弛的互补约束 \( x_ 1 x_ 2 \leq \epsilon_ \nu \) 是非线性的。我们需要将其线性化。定义函数 \( c(x) = x_ 1 x_ 2 - \epsilon_ \nu \leq 0 \)。在当前点 \( z^\nu \) 处，其一阶近似为： \[ c(z) \approx c(z^\nu) + \nabla c(z^\nu)^T (z - z^\nu) \leq 0, \] 其中 \( \nabla c(z) = [ x_ 2, x_ 1 ]^T \)。 构建线性规划子问题 （在第 \( \nu \) 次迭代）： \[ \begin{aligned} \min_ {d_ 1, d_ 2} \quad & 2(x_ 1^\nu - 2) d_ 1 + 2(x_ 2^\nu - 2) d_ 2 \\ \text{s.t.} \quad & x_ 1^\nu + d_ 1 \geq 0, \quad (即 \, x_ 1 \geq 0) \\ & x_ 2^\nu + d_ 2 \geq 0, \quad (即 \, x_ 2 \geq 0) \\ & x_ 1^\nu x_ 2^\nu + x_ 2^\nu d_ 1 + x_ 1^\nu d_ 2 \leq \epsilon_ \nu. \quad (\text{线性化后的松弛互补约束}) \\ & \|d\| \infty \leq \Delta \nu. \quad (\text{信赖域约束，限制步长大小}) \end{aligned} \] 这里， \( d = (d_ 1, d_ 2) = z - z^\nu \) 是搜索步长。我们引入了信赖域约束 \( \|d\| \infty \leq \Delta \nu \)（通常使用 \( \ell_ \infty \) 范数以保持线性性），其中 \( \Delta_ \nu > 0 \) 是信赖域半径，用于保证线性近似的有效性。 这个子问题是一个 线性规划（LP） ，可以用单纯形法或内点法高效求解。我们记其最优解为 \( d^\nu \)，然后计算候选点 \( z^{\text{tmp}} = z^\nu + d^\nu \)。 第4步：接受性检验与参数更新 实际下降量与预测下降量 ： 定义实际下降量： \( \text{Ared} \nu = f(z^\nu) - f(z^{\text{tmp}}) \)。 预测下降量： \( \text{Pred} \nu = -\left( 2(x_ 1^\nu - 2) d_ 1^\nu + 2(x_ 2^\nu - 2) d_ 2^\nu \right) \)（由于线性化目标函数是原目标下降量的线性近似）。 计算比值 \( \rho_ \nu = \frac{\text{Ared} \nu}{\text{Pred} \nu} \)。 信赖域半径更新 （标准信赖域策略）： 如果 \( \rho_ \nu \) 很大（例如 > 0.75），说明线性模型拟合很好，可以增加信赖域半径： \( \Delta_ {\nu+1} = 1.5 \Delta_ \nu \)。 如果 \( \rho_ \nu \) 很小（例如 < 0.25），说明线性模型拟合差，应减小信赖域半径： \( \Delta_ {\nu+1} = 0.5 \Delta_ \nu \)。 否则，保持 \( \Delta_ {\nu+1} = \Delta_ \nu \)。 迭代点更新 ： 如果 \( \rho_ \nu > \eta \)（例如 \( \eta = 10^{-4} \)），说明下降足够，接受步长： \( z^{\nu+1} = z^{\text{tmp}} \)。 否则，拒绝步长： \( z^{\nu+1} = z^\nu \)。 松弛参数更新 ： 这是松弛线性规划法的关键。我们希望在算法收敛的过程中，逐渐将松弛参数 \( \epsilon_ \nu \) 减小到0，以迫使互补约束被满足。 更新策略： \( \epsilon_ {\nu+1} = \max(\epsilon_ {\min}, \tau \cdot \epsilon_ \nu) \)，其中 \( 0 < \tau < 1 \) 是缩减因子（例如0.5）， \( \epsilon_ {\min} \) 是一个很小的正数（例如 \( 10^{-6} \)）作为下限，防止数值问题。 通常，当算法接近稳定（例如连续几次迭代步长很小）时，再减小 \( \epsilon_ \nu \)。 第5步：算法流程与初始化 初始化 ：选择初始点 \( z^0 \)（需满足简单约束 \( x_ 1 \geq 0, x_ 2 \geq 0 \)），例如 \( z^0 = (1, 0) \)。初始松弛参数 \( \epsilon_ 0 = 0.1 \)，初始信赖域半径 \( \Delta_ 0 = 0.5 \)。设置参数 \( \tau = 0.5, \epsilon_ {\min} = 10^{-6}, \eta = 10^{-4} \)。设定最大迭代次数 \( N_ {\max} = 100 \)，收敛容差 \( \text{tol} = 10^{-6} \)。 主迭代循环 （对于 \( \nu = 0, 1, 2, \dots \)）： a. 在当前点 \( z^\nu \) 和当前松弛参数 \( \epsilon_ \nu \) 下，构造并求解上述线性规划子问题，得到步长 \( d^\nu \)。 b. 计算候选点 \( z^{\text{tmp}} = z^\nu + d^\nu \)。 c. 计算实际下降量与预测下降量之比 \( \rho_ \nu \)。 d. 根据 \( \rho_ \nu \) 更新信赖域半径 \( \Delta_ {\nu+1} \)。 e. 如果 \( \rho_ \nu > \eta \)，则接受新点： \( z^{\nu+1} = z^{\text{tmp}} \)，否则 \( z^{\nu+1} = z^\nu \)。 f. 检查收敛条件：如果 \( \|d^\nu\| < \text{tol} \) 且 \( \epsilon_ \nu \leq \epsilon_ {\min} \)，则终止。 g. 更新松弛参数：如果迭代点变化很小（例如 \( \|d^\nu\| < 0.1 \cdot \Delta_ \nu \)），则令 \( \epsilon_ {\nu+1} = \max(\epsilon_ {\min}, \tau \cdot \epsilon_ \nu) \)，否则 \( \epsilon_ {\nu+1} = \epsilon_ \nu \)。 第6步：应用于例题的数值演示（迭代思路） 让我们手动推演前几步，以理解算法如何工作。 初始点 ： \( z^0 = (1, 0) \)，满足 \( x_ 1 \geq 0, x_ 2 \geq 0 \)。 \( f(z^0) = (1-2)^2 + (0-2)^2 = 1 + 4 = 5 \)。 初始松弛参数 \( \epsilon_ 0 = 0.1 \)，信赖域半径 \( \Delta_ 0 = 0.5 \)。 第一次迭代（ν=0） ： 计算梯度： \( \nabla f(z^0) = [ 2(1-2), 2(0-2)] = [ -2, -4 ] \)。 线性化松弛互补约束： \( c(x) = x_ 1 x_ 2 - 0.1 \leq 0 \)。在 \( z^0=(1,0) \)， \( c(z^0) = 1\cdot0 - 0.1 = -0.1 \)，梯度 \( \nabla c(z^0) = [ x_ 2, x_ 1]^T = [ 0, 1 ]^T \)。 构造线性规划子问题： \[ \begin{aligned} \min_ {d_ 1, d_ 2} \quad & (-2) d_ 1 + (-4) d_ 2 \\ \text{s.t.} \quad & 1 + d_ 1 \geq 0, \quad 0 + d_ 2 \geq 0, \\ & -0.1 + 0 \cdot d_ 1 + 1 \cdot d_ 2 \leq 0 \quad (\text{即 } d_ 2 \leq 0.1), \\ & |d_ 1| \leq 0.5, \quad |d_ 2| \leq 0.5. \end{aligned} \] 化简目标： \( -2d_ 1 -4d_ 2 \)。 约束条件： \( d_ 1 \geq -1, d_ 2 \geq 0, d_ 2 \leq 0.1, |d_ 1| \leq 0.5, |d_ 2| \leq 0.5 \)。 由于目标是最小化，且 \( d_ 2 \) 的系数为-4（负），我们希望 \( d_ 2 \) 尽可能大以减小目标函数值。约束条件中 \( d_ 2 \) 的上界是0.1，下界是0，所以取 \( d_ 2 = 0.1 \) 最佳。对于 \( d_ 1 \)，系数为-2，我们希望 \( d_ 1 \) 尽可能大。约束条件为 \( d_ 1 \geq -1 \) 且 \( |d_ 1| \leq 0.5 \)，所以最大可取 \( d_ 1 = 0.5 \)。 因此，最优解为 \( d^0 = (0.5, 0.1) \)。 候选点： \( z^{\text{tmp}} = (1+0.5, 0+0.1) = (1.5, 0.1) \)。 计算实际下降量： \( f(z^{\text{tmp}}) = (1.5-2)^2 + (0.1-2)^2 = 0.25 + 3.61 = 3.86 \)。实际下降 \( \text{Ared} = 5 - 3.86 = 1.14 \)。 预测下降量： \( \text{Pred} = -((-2) 0.5 + (-4) 0.1) = -(-1 -0.4) = 1.4 \)。 比值 \( \rho = 1.14 / 1.4 \approx 0.814 > 0.75 \)。 更新：由于 \( \rho > 0.75 \)，扩大信赖域半径： \( \Delta_ 1 = 1.5 * 0.5 = 0.75 \)。因为 \( \rho > \eta = 10^{-4} \)，接受新点： \( z^1 = (1.5, 0.1) \)。 由于步长 \( \|d^0\|_ \infty = 0.5 \) 较大，不减少 \( \epsilon \)，所以 \( \epsilon_ 1 = \epsilon_ 0 = 0.1 \)。 第二次迭代（ν=1） ： 当前点 \( z^1 = (1.5, 0.1) \)， \( f(z^1) = 3.86 \)。 梯度： \( \nabla f(z^1) = [ 2(1.5-2), 2(0.1-2)] = [ -1, -3.8 ] \)。 线性化松弛互补约束： \( c(z) = x_ 1 x_ 2 - 0.1 \)。在 \( z^1 \)， \( c(z^1) = 1.5* 0.1 - 0.1 = 0.15 - 0.1 = 0.05 \)，梯度 \( \nabla c(z^1) = [ 0.1, 1.5 ]^T \)。 构造线性规划子问题： \[ \begin{aligned} \min_ {d_ 1, d_ 2} \quad & (-1) d_ 1 + (-3.8) d_ 2 \\ \text{s.t.} \quad & 1.5 + d_ 1 \geq 0, \quad 0.1 + d_ 2 \geq 0, \\ & 0.05 + 0.1 d_ 1 + 1.5 d_ 2 \leq 0, \\ & |d_ 1| \leq 0.75, \quad |d_ 2| \leq 0.75. \end{aligned} \] 化简约束： \( d_ 1 \geq -1.5, d_ 2 \geq -0.1, 0.1 d_ 1 + 1.5 d_ 2 \leq -0.05 \)。 目标是最小化 \( -d_ 1 -3.8 d_ 2 \)，我们希望 \( d_ 1, d_ 2 \) 尽可能大，但它们受到最后一个线性不等式的限制。这是一个小线性规划，我们可以图解法或单纯形法求解。为了满足 \( 0.1 d_ 1 + 1.5 d_ 2 \leq -0.05 \) 并使目标最小，可以取边界 \( 0.1 d_ 1 + 1.5 d_ 2 = -0.05 \)，并最大化 \( d_ 1, d_ 2 \)。 假设我们先最大化 \( d_ 2 \)。从等式解出 \( d_ 1 = -0.5 -15 d_ 2 \)。代入约束 \( |d_ 1| \leq 0.75 \) 和 \( d_ 2 \leq 0.75 \)。同时 \( d_ 2 \geq -0.1 \)。目标函数变为 \( -(-0.5-15d_ 2) -3.8 d_ 2 = 0.5 + 15d_ 2 -3.8 d_ 2 = 0.5 + 11.2 d_ 2 \)。由于系数11.2>0，所以 \( d_ 2 \) 越大，目标函数值越大（注意我们在最小化，所以这不利）。因此，我们应该最小化 \( d_ 2 \)。在约束下，最小 \( d_ 2 = -0.1 \)（下界）。代入等式得 \( d_ 1 = -0.5 -15* (-0.1) = 1.0 \)，但这违反了 \( |d_ 1| \leq 0.75 \)。所以我们需要满足 \( |d_ 1| \leq 0.75 \)，即 \( -0.75 \leq d_ 1 \leq 0.75 \)。从等式 \( d_ 1 = -0.5 -15 d_ 2 \) 和 \( d_ 1 \) 的范围，可以解出 \( d_ 2 \) 的范围。当 \( d_ 1 = 0.75 \) 时， \( d_ 2 = (-0.5 - 0.75)/15 = -1.25/15 \approx -0.0833 \)。当 \( d_ 1 = -0.75 \) 时， \( d_ 2 = (-0.5 + 0.75)/15 = 0.25/15 \approx 0.0167 \)。所以 \( d_ 2 \) 的范围大约在 [ -0.0833, 0.0167] 之间。目标函数 \( -d_ 1 -3.8 d_ 2 \)，代入 \( d_ 1 = -0.5 -15 d_ 2 \)，目标变为 \( -(-0.5-15d_ 2) -3.8 d_ 2 = 0.5+15d_ 2 -3.8d_ 2 = 0.5 + 11.2 d_ 2 \)。由于系数11.2>0，为使目标最小，应取最小的 \( d_ 2 \)，即 \( d_ 2 = -0.0833 \)，对应的 \( d_ 1 = 0.75 \)（边界）。再检查其他约束： \( d_ 1=0.75 \geq -1.5 \)， \( d_ 2=-0.0833 \geq -0.1 \)？不， \( d_ 2 = -0.0833 > -0.1 \)，所以满足。因此，最优解约为 \( d^1 = (0.75, -0.0833) \)。 候选点： \( z^{\text{tmp}} = (1.5+0.75, 0.1-0.0833) = (2.25, 0.0167) \)。 计算实际下降量： \( f(z^{\text{tmp}}) = (2.25-2)^2 + (0.0167-2)^2 = 0.0625 + 3.9306 = 3.9931 \)。这比当前值3.86还大，实际下降为负！这意味着线性模型在信赖域内指向了使目标函数值增加的方向。这是因为线性模型在当前点附近不是目标函数的良好近似，特别是由于互补约束线性化可能引入了误差。 此时， \( \rho \) 将为负，因此不会接受这一步，算法会缩小信赖域半径，重新求解子问题或直接拒绝步长。 由于手动计算在后续步骤会变得复杂，我们就此打住。实际算法中，当发生这种情况（实际上升），会拒绝步长，缩小信赖域半径，并在下一次迭代中求解一个更小范围内的线性规划子问题。通过反复迭代，最终算法会收敛到一个满足互补约束（当 \( \epsilon_ \nu \) 很小时）的稳定点。 第7步：收敛性说明 松弛线性规划法（RLPM）结合了序列线性规划和松弛策略。通过逐步减小松弛参数 \( \epsilon_ \nu \rightarrow 0 \)，迫使松弛互补约束趋近于严格的互补约束 \( x_ 1 x_ 2 = 0 \)。同时，信赖域机制保证了线性近似的准确性。在适当的条件下（例如，目标函数和约束的导数 Lipschitz 连续，且子问题的线性独立约束规范在极限点满足），算法生成的迭代点序列的极限点，是原MPCC问题的 C-稳定点 （一种一阶必要条件，类似于KKT点，但针对互补约束进行了修正）。需要注意的是，由于互补约束导致可行域不满足标准约束规范，极限点可能不是KKT点，而是更弱的稳定点。 总结 你已学习了如何应用 松弛线性规划法 求解带有互补约束的数学规划问题（MPCC）。关键步骤包括： 用松弛参数 \( \epsilon \) 替换互补约束 \( G_ k H_ k = 0 \) 为 \( G_ k H_ k \leq \epsilon \) 或类似形式。 在当前点线性化目标函数和所有约束（包括松弛后的互补约束），构建一个带信赖域约束的线性规划子问题。 求解子问题得到搜索方向，通过实际下降与预测下降之比判断是否接受步长，并更新信赖域半径。 在迭代过程中，逐步减小松弛参数 \( \epsilon \)，使其趋于0，从而逐渐恢复原互补约束。 算法最终收敛到原问题的一个近似解。 这种方法将复杂的、非凸且不规则的互补约束问题，转化为一系列相对容易求解的线性规划问题，是处理MPCC的一类实用数值方法。