非线性规划中的精确罚函数法进阶题

字数 7243 2025-12-08 04:35:08

非线性规划中的精确罚函数法进阶题

题目描述

考虑一个带有等式约束和不等式约束的非线性规划问题：

\[\min_{x \in \mathbb{R}^n} f(x) \]

\[ \text{subject to} \quad h_i(x) = 0, \quad i = 1, \ldots, m \]

\[ g_j(x) \leq 0, \quad j = 1, \ldots, p \]

其中，函数 $f, h_i, g_j: \mathbb{R}^n \rightarrow \mathbb{R}$ 都是连续可微的。

精确罚函数法的核心思想是构造一个无约束优化问题，其目标函数（罚函数）在惩罚参数大于某个阈值时，其极小点正好是原约束问题的极小点。常见的精确罚函数形式之一是 $l_1$ 精确罚函数：

\[\phi_1(x; \mu) = f(x) + \mu \left( \sum_{i=1}^{m} |h_i(x)| + \sum_{j=1}^{p} \max(0, g_j(x)) \right) \]

其中，惩罚参数 $\mu > 0$。

进阶题具体描述：假设我们已知一个局部极小点 $x^*$ 及其对应的拉格朗日乘子向量 $\lambda^*$（对应等式约束）和 $\mu^*$（对应不等式约束），且满足二阶充分条件（正定的拉格朗日函数Hessian矩阵在临界切空间上）。证明：对于所有满足 $\mu > \|\lambda^*\|_{\infty} + \|\mu^*\|_{\infty}$ 的惩罚参数 $\mu$，$x^*$ 也是无约束精确罚函数 $\phi_1(x; \mu)$ 的一个严格局部极小点。这里 $\|\cdot\|_{\infty}$ 表示向量各分量绝对值中的最大值。你需要清晰阐述证明的思路和关键步骤。

解题过程循序渐进讲解

第一步：理解精确罚函数的基本性质和目标

首先，我们回忆罚函数 $\phi_1(x; \mu)$ 的定义：

\[\phi_1(x; \mu) = f(x) + \mu \left( \sum_{i=1}^{m} |h_i(x)| + \sum_{j=1}^{p} \max(0, g_j(x)) \right) \]

这个函数是原目标函数加上一个惩罚项，惩罚项度量了约束违反的程度。在 $\mu$ 足够大时，罚函数的极小点应该与原始问题的极小点一致。

我们要证明的是：如果 $x^*$ 是原问题的一个局部极小点，且满足一定的正则性条件（拉格朗日乘子存在），那么当 $\mu$ 大于所有拉格朗日乘子绝对值的最大值时，$x^*$ 也是罚函数 $\phi_1(\cdot; \mu)$ 的一个严格局部极小点。

第二步：写出原问题的KKT条件

由于 $x^*$ 是局部极小点且我们假设乘子存在，则它必须满足KKT条件。记等式约束乘子为 $\lambda_i^*$（$i=1, \ldots, m$），不等式约束乘子为 $\nu_j^*$（$j=1, \ldots, p$）。KKT条件如下：

平稳性：

\[ \nabla f(x^*) + \sum_{i=1}^{m} \lambda_i^* \nabla h_i(x^*) + \sum_{j=1}^{p} \nu_j^* \nabla g_j(x^*) = 0 \]

原始可行性：

\[ h_i(x^*) = 0, \quad i = 1, \ldots, m \]

\[ g_j(x^*) \leq 0, \quad j = 1, \ldots, p \]

互补松弛性：

\[ \nu_j^* \cdot g_j(x^*) = 0, \quad \nu_j^* \geq 0, \quad j = 1, \ldots, p \]

此外，我们还假设二阶充分条件成立，即拉格朗日函数 $L(x, \lambda, \nu) = f(x) + \sum \lambda_i h_i(x) + \sum \nu_j g_j(x)$ 在点 $x^*$ 的Hessian矩阵在临界切空间上是正定的，这保证了 $x^*$ 是严格局部极小点。

第三步：分析罚函数的方向导数（次梯度）

由于 $| \cdot |$ 和 $\max(0, \cdot)$ 在零点不可导，所以 $\phi_1$ 在 $x^*$ 处一般是不可微的。我们需要使用非光滑分析中的次梯度（subgradient）概念。

设 $d \in \mathbb{R}^n$ 为任意方向向量。考虑罚函数 $\phi_1$ 在 $x^*$ 沿方向 $d$ 的方向导数（或更准确地说，是Clarke广义方向导数）：

\[\phi_1'(x^*; d, \mu) = \nabla f(x^*)^T d + \mu \left( \sum_{i=1}^{m} \sigma_i h_i'(x^*; d) + \sum_{j=1}^{p} \tau_j g_j'(x^*; d) \right) \]

其中：

$h_i'(x^*; d) = \nabla h_i(x^*)^T d$ （因为 $h_i$ 可微）
$g_j'(x^*; d) = \nabla g_j(x^*)^T d$ （因为 $g_j$ 可微）
$\sigma_i \in \partial |h_i(x^*)|$，由于 $h_i(x^*) = 0$，所以 $\sigma_i \in [-1, 1]$。
$\tau_j \in \partial \max(0, g_j(x^*))$。我们需要分情况讨论：
- 若 $g_j(x^*) < 0$，则 $\max(0, g_j(x^*)) = 0$ 且在 $x^*$ 处可导，导数为0，所以 $\tau_j = 0$。
- 若 $g_j(x^*) = 0$，则次梯度 $\tau_j \in [0, 1]$。

但更简单的办法是直接利用KKT条件构造一个特定的次梯度，从而判断 $x^*$ 是否为 $\phi_1$ 的驻点（即0属于次微分）。

第四步：构造罚函数在 $x^*$ 处的次梯度，并利用KKT条件

定义向量 $\xi \in \mathbb{R}^n$ 为：

\[\xi = \nabla f(x^*) + \mu \left( \sum_{i=1}^{m} \operatorname{sgn}(h_i(x^*)) \nabla h_i(x^*) + \sum_{j=1}^{p} \delta_j \nabla g_j(x^*) \right) \]

但因为 $h_i(x^*) = 0$，$\operatorname{sgn}(0)$ 未定义。实际上，我们需要选择 $\sigma_i \in [-1, 1]$ 和 $\tau_j \in [0,1]$（当 $g_j(x^*) = 0$ 时）或 $\tau_j = 0$（当 $g_j(x^*) < 0$ 时），使得 $\xi = 0$。如果我们能选择合适的 $\sigma_i, \tau_j$ 使得 $\xi = 0$，那么 $0$ 就属于 $\phi_1(x^*; \mu)$ 的次微分，即 $x^*$ 是罚函数的驻点。

观察KKT条件的平稳性方程：

\[\nabla f(x^*) + \sum_{i=1}^{m} \lambda_i^* \nabla h_i(x^*) + \sum_{j=1}^{p} \nu_j^* \nabla g_j(x^*) = 0 \]

我们希望把它和 $\xi = 0$ 的式子匹配起来。为此，我们选择：

$\sigma_i = \frac{\lambda_i^*}{\mu}$，只要 $|\lambda_i^*| \leq \mu$，就有 $\sigma_i \in [-1, 1]$。
对于不等式约束：
- 若 $g_j(x^*) < 0$，则 $\nu_j^* = 0$（由互补松弛性），我们取 $\tau_j = 0 = \frac{\nu_j^*}{\mu}$。
- 若 $g_j(x^*) = 0$，我们取 $\tau_j = \frac{\nu_j^*}{\mu}$，由于 $\nu_j^* \geq 0$ 且我们要求 $\tau_j \in [0, 1]$，所以需要 $\nu_j^* \leq \mu$。

因此，如果我们有 $\mu > \max \{ |\lambda_i^*|, \nu_j^* \}$ 对所有 $i, j$ 成立，即 $\mu > \|\lambda^*\|_{\infty} + \|\nu^*\|_{\infty}$（实际上严格大于两者中的最大值即可，但题目中用了和的形式，本质一样，因为只要 $\mu$ 大于两者最大值，条件自然满足），那么我们可以取 $\sigma_i = \lambda_i^* / \mu$，$\tau_j = \nu_j^* / \mu$，使得：

\[0 = \nabla f(x^*) + \mu \left( \sum_{i=1}^{m} \sigma_i \nabla h_i(x^*) + \sum_{j=1}^{p} \tau_j \nabla g_j(x^*) \right) \]

这意味着 $0 \in \partial \phi_1(x^*; \mu)$，即 $x^*$ 是罚函数的一个驻点。

第五步：证明 $x^*$ 是罚函数的严格局部极小点

仅仅驻点还不够，我们还需证明它是严格局部极小点。这需要用到二阶充分条件。考虑在 $x^*$ 附近的一个点 $x = x^* + d$，其中 $\|d\|$ 很小。我们要证明 $\phi_1(x; \mu) \geq \phi_1(x^*; \mu)$，且等号仅在 $d = 0$ 时成立。

由于 $x^*$ 可行，$\phi_1(x^*; \mu) = f(x^*)$。对于附近的 $x$，展开 $f, h_i, g_j$ 到二阶：

\[f(x) = f(x^*) + \nabla f(x^*)^T d + \frac{1}{2} d^T \nabla^2 f(x^*) d + o(\|d\|^2) \]

\[ h_i(x) = \nabla h_i(x^*)^T d + \frac{1}{2} d^T \nabla^2 h_i(x^*) d + o(\|d\|^2) \]

\[ g_j(x) = \nabla g_j(x^*)^T d + \frac{1}{2} d^T \nabla^2 g_j(x^*) d + o(\|d\|^2) \]

罚函数变为：

\[\phi_1(x; \mu) = f(x^*) + \nabla f(x^*)^T d + \frac{1}{2} d^T \nabla^2 f(x^*) d \\ + \mu \sum_{i=1}^{m} | \nabla h_i(x^*)^T d + \frac{1}{2} d^T \nabla^2 h_i(x^*) d + o(\|d\|^2) | \\ + \mu \sum_{j=1}^{p} \max \left( 0, \nabla g_j(x^*)^T d + \frac{1}{2} d^T \nabla^2 g_j(x^*) d + o(\|d\|^2) \right) + o(\|d\|^2) \]

关键的一步：由于 $\mu$ 足够大，且 $0 \in \partial \phi_1(x^*; \mu)$ 由前述构造给出，我们可以利用拉格朗日函数 $L$ 的二阶展开来比较。

考虑拉格朗日函数在 $x^*$ 附近的二阶展开：

\[L(x, \lambda^*, \nu^*) = f(x^*) + \nabla f(x^*)^T d + \frac{1}{2} d^T \nabla^2_{xx} L(x^*, \lambda^*, \nu^*) d + o(\|d\|^2) \]

其中平稳性条件保证了线性项与约束的线性项组合后消失。更精确地，由于 $h_i(x^*) = 0$ 和互补松弛性 $\nu_j^* g_j(x^*) = 0$，我们有：

\[L(x, \lambda^*, \nu^*) = f(x) + \sum \lambda_i^* h_i(x) + \sum \nu_j^* g_j(x) \]

现在，我们想证明 $\phi_1(x; \mu) \geq L(x, \lambda^*, \nu^*)$ 在 $x^*$ 附近成立，且等号在 $x = x^*$ 时取到。这是因为：

对于每个 $i$，$|h_i(x)| \geq h_i(x)$ 如果 $\lambda_i^* \geq 0$，但 $\lambda_i^*$ 可正可负。更一般地，利用 $\mu > |\lambda_i^*|$，有 $\mu |h_i(x)| \geq \lambda_i^* h_i(x)$（因为 $|\lambda_i^*| \cdot |h_i(x)| \leq \mu |h_i(x)|$）。
对于每个 $j$，若 $\nu_j^* > 0$，则 $g_j(x^*) = 0$，且 $\mu > \nu_j^*$。对于附近的 $x$，如果 $g_j(x) > 0$，则 $\mu \max(0, g_j(x)) = \mu g_j(x) \geq \nu_j^* g_j(x)$；如果 $g_j(x) \leq 0$，则 $\mu \max(0, g_j(x)) = 0 \geq \nu_j^* g_j(x)$（因为 $\nu_j^* \geq 0, g_j(x) \leq 0$）。

因此，我们有逐项不等式：

\[\mu |h_i(x)| \geq \lambda_i^* h_i(x), \quad \mu \max(0, g_j(x)) \geq \nu_j^* g_j(x) \]

对所有 $i, j$ 成立（当 $\mu > \|\lambda^*\|_{\infty} + \|\nu^*\|_{\infty}$ 时）。求和得到：

\[\phi_1(x; \mu) \geq f(x) + \sum \lambda_i^* h_i(x) + \sum \nu_j^* g_j(x) = L(x, \lambda^*, \nu^*) \]

此外，在 $x^*$ 处，等号成立：$\phi_1(x^*; \mu) = f(x^*) = L(x^*, \lambda^*, \nu^*)$。

由于 $x^*$ 满足原问题的二阶充分条件，$L(x, \lambda^*, \nu^*)$ 在 $x^*$ 处有严格局部极小值。因此，在 $x^*$ 附近，对于 $x \neq x^*$，有：

\[\phi_1(x; \mu) \geq L(x, \lambda^*, \nu^*) > L(x^*, \lambda^*, \nu^*) = \phi_1(x^*; \mu) \]

这说明 $x^*$ 是 $\phi_1(\cdot; \mu)$ 的一个严格局部极小点。

第六步：结论

我们证明了：当惩罚参数 $\mu$ 大于所有拉格朗日乘子（包括等式和不等式约束）绝对值的最大值时，原问题的局部极小点 $x^*$（满足KKT条件和二阶充分条件）也是 $l_1$ 精确罚函数 $\phi_1(x; \mu)$ 的一个严格局部极小点。这解释了为什么这种罚函数被称为“精确”的——不需要让 $\mu \to \infty$，只需大于一个有限的阈值即可精确恢复原问题的解。

非线性规划中的精确罚函数法进阶题题目描述考虑一个带有等式约束和不等式约束的非线性规划问题： $$ \min_ {x \in \mathbb{R}^n} f(x) $$ $$ \text{subject to} \quad h_ i(x) = 0, \quad i = 1, \ldots, m $$ $$ g_ j(x) \leq 0, \quad j = 1, \ldots, p $$ 其中，函数 $ f, h_ i, g_ j: \mathbb{R}^n \rightarrow \mathbb{R} $ 都是连续可微的。精确罚函数法的核心思想是构造一个无约束优化问题，其目标函数（罚函数）在惩罚参数大于某个阈值时，其极小点正好是原约束问题的极小点。常见的精确罚函数形式之一是 $ l_ 1 $ 精确罚函数： $$ \phi_ 1(x; \mu) = f(x) + \mu \left( \sum_ {i=1}^{m} |h_ i(x)| + \sum_ {j=1}^{p} \max(0, g_ j(x)) \right) $$ 其中，惩罚参数 $ \mu > 0 $。进阶题具体描述：假设我们已知一个局部极小点 $ x^* $ 及其对应的拉格朗日乘子向量 $ \lambda^* $（对应等式约束）和 $ \mu^* $（对应不等式约束），且满足二阶充分条件（正定的拉格朗日函数Hessian矩阵在临界切空间上）。证明：对于所有满足 $ \mu > \|\lambda^ \|_ {\infty} + \|\mu^ \| {\infty} $ 的惩罚参数 $ \mu $，$ x^* $ 也是无约束精确罚函数 $ \phi_ 1(x; \mu) $ 的一个严格局部极小点。这里 $ \|\cdot\| {\infty} $ 表示向量各分量绝对值中的最大值。你需要清晰阐述证明的思路和关键步骤。解题过程循序渐进讲解第一步：理解精确罚函数的基本性质和目标首先，我们回忆罚函数 $ \phi_ 1(x; \mu) $ 的定义： $$ \phi_ 1(x; \mu) = f(x) + \mu \left( \sum_ {i=1}^{m} |h_ i(x)| + \sum_ {j=1}^{p} \max(0, g_ j(x)) \right) $$ 这个函数是原目标函数加上一个惩罚项，惩罚项度量了约束违反的程度。在 $ \mu $ 足够大时，罚函数的极小点应该与原始问题的极小点一致。我们要证明的是：如果 $ x^* $ 是原问题的一个局部极小点，且满足一定的正则性条件（拉格朗日乘子存在），那么当 $ \mu $ 大于所有拉格朗日乘子绝对值的最大值时，$ x^* $ 也是罚函数 $ \phi_ 1(\cdot; \mu) $ 的一个严格局部极小点。第二步：写出原问题的KKT条件由于 $ x^* $ 是局部极小点且我们假设乘子存在，则它必须满足KKT条件。记等式约束乘子为 $ \lambda_ i^* $（$ i=1, \ldots, m $），不等式约束乘子为 $ \nu_ j^* $（$ j=1, \ldots, p $）。KKT条件如下：平稳性： $$ \nabla f(x^ ) + \sum_ {i=1}^{m} \lambda_ i^ \nabla h_ i(x^ ) + \sum_ {j=1}^{p} \nu_ j^ \nabla g_ j(x^* ) = 0 $$ 原始可行性： $$ h_ i(x^ ) = 0, \quad i = 1, \ldots, m $$ $$ g_ j(x^ ) \leq 0, \quad j = 1, \ldots, p $$ 互补松弛性： $$ \nu_ j^* \cdot g_ j(x^ ) = 0, \quad \nu_ j^ \geq 0, \quad j = 1, \ldots, p $$ 此外，我们还假设二阶充分条件成立，即拉格朗日函数 $ L(x, \lambda, \nu) = f(x) + \sum \lambda_ i h_ i(x) + \sum \nu_ j g_ j(x) $ 在点 $ x^* $ 的Hessian矩阵在临界切空间上是正定的，这保证了 $ x^* $ 是严格局部极小点。第三步：分析罚函数的方向导数（次梯度）由于 $ | \cdot | $ 和 $ \max(0, \cdot) $ 在零点不可导，所以 $ \phi_ 1 $ 在 $ x^* $ 处一般是不可微的。我们需要使用非光滑分析中的次梯度（subgradient）概念。设 $ d \in \mathbb{R}^n $ 为任意方向向量。考虑罚函数 $ \phi_ 1 $ 在 $ x^* $ 沿方向 $ d $ 的方向导数（或更准确地说，是Clarke广义方向导数）： $$ \phi_ 1'(x^ ; d, \mu) = \nabla f(x^ )^T d + \mu \left( \sum_ {i=1}^{m} \sigma_ i h_ i'(x^ ; d) + \sum_ {j=1}^{p} \tau_ j g_ j'(x^ ; d) \right) $$ 其中： $ h_ i'(x^ ; d) = \nabla h_ i(x^ )^T d $ （因为 $ h_ i $ 可微） $ g_ j'(x^ ; d) = \nabla g_ j(x^ )^T d $ （因为 $ g_ j $ 可微） $ \sigma_ i \in \partial |h_ i(x^ )| $，由于 $ h_ i(x^ ) = 0 $，所以 $ \sigma_ i \in [ -1, 1 ] $。 $ \tau_ j \in \partial \max(0, g_ j(x^* )) $。我们需要分情况讨论：若 $ g_ j(x^ ) < 0 $，则 $ \max(0, g_ j(x^ )) = 0 $ 且在 $ x^* $ 处可导，导数为0，所以 $ \tau_ j = 0 $。若 $ g_ j(x^* ) = 0 $，则次梯度 $ \tau_ j \in [ 0, 1 ] $。但更简单的办法是直接利用KKT条件构造一个特定的次梯度，从而判断 $ x^* $ 是否为 $ \phi_ 1 $ 的驻点（即0属于次微分）。第四步：构造罚函数在 $ x^* $ 处的次梯度，并利用KKT条件定义向量 $ \xi \in \mathbb{R}^n $ 为： $$ \xi = \nabla f(x^ ) + \mu \left( \sum_ {i=1}^{m} \operatorname{sgn}(h_ i(x^ )) \nabla h_ i(x^ ) + \sum_ {j=1}^{p} \delta_ j \nabla g_ j(x^ ) \right) $$ 但因为 $ h_ i(x^ ) = 0 $，$ \operatorname{sgn}(0) $ 未定义。实际上，我们需要选择 $ \sigma_ i \in [ -1, 1] $ 和 $ \tau_ j \in [ 0,1] $（当 $ g_ j(x^ ) = 0 $ 时）或 $ \tau_ j = 0 $（当 $ g_ j(x^ ) < 0 $ 时），使得 $ \xi = 0 $。如果我们能选择合适的 $ \sigma_ i, \tau_ j $ 使得 $ \xi = 0 $，那么 $ 0 $ 就属于 $ \phi_ 1(x^ ; \mu) $ 的次微分，即 $ x^* $ 是罚函数的驻点。观察KKT条件的平稳性方程： $$ \nabla f(x^ ) + \sum_ {i=1}^{m} \lambda_ i^ \nabla h_ i(x^ ) + \sum_ {j=1}^{p} \nu_ j^ \nabla g_ j(x^* ) = 0 $$ 我们希望把它和 $ \xi = 0 $ 的式子匹配起来。为此，我们选择： $ \sigma_ i = \frac{\lambda_ i^ }{\mu} $，只要 $ |\lambda_ i^ | \leq \mu $，就有 $ \sigma_ i \in [ -1, 1 ] $。对于不等式约束：若 $ g_ j(x^ ) < 0 $，则 $ \nu_ j^ = 0 $（由互补松弛性），我们取 $ \tau_ j = 0 = \frac{\nu_ j^* }{\mu} $。若 $ g_ j(x^ ) = 0 $，我们取 $ \tau_ j = \frac{\nu_ j^ }{\mu} $，由于 $ \nu_ j^* \geq 0 $ 且我们要求 $ \tau_ j \in [ 0, 1] $，所以需要 $ \nu_ j^* \leq \mu $。因此，如果我们有 $ \mu > \max \{ |\lambda_ i^ |, \nu_ j^ \} $ 对所有 $ i, j $ 成立，即 $ \mu > \|\lambda^ \|_ {\infty} + \|\nu^ \| {\infty} $（实际上严格大于两者中的最大值即可，但题目中用了和的形式，本质一样，因为只要 $ \mu $ 大于两者最大值，条件自然满足），那么我们可以取 $ \sigma_ i = \lambda_ i^* / \mu $，$ \tau_ j = \nu_ j^* / \mu $，使得： $$ 0 = \nabla f(x^* ) + \mu \left( \sum {i=1}^{m} \sigma_ i \nabla h_ i(x^ ) + \sum_ {j=1}^{p} \tau_ j \nabla g_ j(x^ ) \right) $$ 这意味着 $ 0 \in \partial \phi_ 1(x^ ; \mu) $，即 $ x^ $ 是罚函数的一个驻点。第五步：证明 $ x^* $ 是罚函数的严格局部极小点仅仅驻点还不够，我们还需证明它是严格局部极小点。这需要用到二阶充分条件。考虑在 $ x^* $ 附近的一个点 $ x = x^* + d $，其中 $ \|d\| $ 很小。我们要证明 $ \phi_ 1(x; \mu) \geq \phi_ 1(x^* ; \mu) $，且等号仅在 $ d = 0 $ 时成立。由于 $ x^* $ 可行，$ \phi_ 1(x^ ; \mu) = f(x^ ) $。对于附近的 $ x $，展开 $ f, h_ i, g_ j $ 到二阶： $$ f(x) = f(x^ ) + \nabla f(x^ )^T d + \frac{1}{2} d^T \nabla^2 f(x^ ) d + o(\|d\|^2) $$ $$ h_ i(x) = \nabla h_ i(x^ )^T d + \frac{1}{2} d^T \nabla^2 h_ i(x^ ) d + o(\|d\|^2) $$ $$ g_ j(x) = \nabla g_ j(x^ )^T d + \frac{1}{2} d^T \nabla^2 g_ j(x^* ) d + o(\|d\|^2) $$ 罚函数变为： $$ \phi_ 1(x; \mu) = f(x^ ) + \nabla f(x^ )^T d + \frac{1}{2} d^T \nabla^2 f(x^* ) d \\ \mu \sum_ {i=1}^{m} | \nabla h_ i(x^ )^T d + \frac{1}{2} d^T \nabla^2 h_ i(x^ ) d + o(\|d\|^2) | \\ \mu \sum_ {j=1}^{p} \max \left( 0, \nabla g_ j(x^ )^T d + \frac{1}{2} d^T \nabla^2 g_ j(x^ ) d + o(\|d\|^2) \right) + o(\|d\|^2) $$ 关键的一步：由于 $ \mu $ 足够大，且 $ 0 \in \partial \phi_ 1(x^* ; \mu) $ 由前述构造给出，我们可以利用拉格朗日函数 $ L $ 的二阶展开来比较。考虑拉格朗日函数在 $ x^* $ 附近的二阶展开： $$ L(x, \lambda^ , \nu^ ) = f(x^ ) + \nabla f(x^ )^T d + \frac{1}{2} d^T \nabla^2_ {xx} L(x^ , \lambda^ , \nu^ ) d + o(\|d\|^2) $$ 其中平稳性条件保证了线性项与约束的线性项组合后消失。更精确地，由于 $ h_ i(x^ ) = 0 $ 和互补松弛性 $ \nu_ j^* g_ j(x^ ) = 0 $，我们有： $$ L(x, \lambda^ , \nu^ ) = f(x) + \sum \lambda_ i^ h_ i(x) + \sum \nu_ j^* g_ j(x) $$ 现在，我们想证明 $ \phi_ 1(x; \mu) \geq L(x, \lambda^ , \nu^ ) $ 在 $ x^* $ 附近成立，且等号在 $ x = x^* $ 时取到。这是因为：对于每个 $ i $，$ |h_ i(x)| \geq h_ i(x) $ 如果 $ \lambda_ i^* \geq 0 $，但 $ \lambda_ i^* $ 可正可负。更一般地，利用 $ \mu > |\lambda_ i^ | $，有 $ \mu |h_ i(x)| \geq \lambda_ i^ h_ i(x) $（因为 $ |\lambda_ i^* | \cdot |h_ i(x)| \leq \mu |h_ i(x)| $）。对于每个 $ j $，若 $ \nu_ j^* > 0 $，则 $ g_ j(x^ ) = 0 $，且 $ \mu > \nu_ j^ $。对于附近的 $ x $，如果 $ g_ j(x) > 0 $，则 $ \mu \max(0, g_ j(x)) = \mu g_ j(x) \geq \nu_ j^* g_ j(x) $；如果 $ g_ j(x) \leq 0 $，则 $ \mu \max(0, g_ j(x)) = 0 \geq \nu_ j^* g_ j(x) $（因为 $ \nu_ j^* \geq 0, g_ j(x) \leq 0 $）。因此，我们有逐项不等式： $$ \mu |h_ i(x)| \geq \lambda_ i^* h_ i(x), \quad \mu \max(0, g_ j(x)) \geq \nu_ j^* g_ j(x) $$ 对所有 $ i, j $ 成立（当 $ \mu > \|\lambda^ \|_ {\infty} + \|\nu^ \|_ {\infty} $ 时）。求和得到： $$ \phi_ 1(x; \mu) \geq f(x) + \sum \lambda_ i^* h_ i(x) + \sum \nu_ j^* g_ j(x) = L(x, \lambda^ , \nu^ ) $$ 此外，在 $ x^* $ 处，等号成立：$ \phi_ 1(x^ ; \mu) = f(x^ ) = L(x^ , \lambda^ , \nu^* ) $。由于 $ x^* $ 满足原问题的二阶充分条件，$ L(x, \lambda^ , \nu^ ) $ 在 $ x^* $ 处有严格局部极小值。因此，在 $ x^* $ 附近，对于 $ x \neq x^* $，有： $$ \phi_ 1(x; \mu) \geq L(x, \lambda^ , \nu^ ) > L(x^ , \lambda^ , \nu^ ) = \phi_ 1(x^ ; \mu) $$ 这说明 $ x^* $ 是 $ \phi_ 1(\cdot; \mu) $ 的一个严格局部极小点。第六步：结论我们证明了：当惩罚参数 $ \mu $ 大于所有拉格朗日乘子（包括等式和不等式约束）绝对值的最大值时，原问题的局部极小点 $ x^* $（满足KKT条件和二阶充分条件）也是 $ l_ 1 $ 精确罚函数 $ \phi_ 1(x; \mu) $ 的一个严格局部极小点。这解释了为什么这种罚函数被称为“精确”的——不需要让 $ \mu \to \infty $，只需大于一个有限的阈值即可精确恢复原问题的解。