非线性规划中的混合罚函数法进阶题

字数 3875 2025-12-05 20:47:21

非线性规划中的混合罚函数法进阶题

题目描述：
考虑如下非线性规划问题：

\[\begin{aligned} \min_{x \in \mathbb{R}^2} \quad & f(x) = (x_1 - 3)^2 + (x_2 - 2)^2 \\ \text{s.t.} \quad & g_1(x) = x_1 + x_2 - 4 \le 0 \\ & g_2(x) = -x_1 \le 0 \\ & h(x) = x_1^2 - x_2 = 0 \end{aligned} \]

请使用混合罚函数法（也称为“乘子罚函数法”或“增广拉格朗日法”）求解此问题。要求详细推导混合罚函数的构造，并阐述算法迭代步骤，包括如何更新拉格朗日乘子和惩罚参数，直到满足收敛条件。

解题过程：

算法思想回顾
混合罚函数法结合了拉格朗日乘子法和罚函数法的优点。其核心思想是：对等式约束和不等式约束，构造一个“增广拉格朗日函数”，其中包含拉格朗日乘子项和惩罚项。通过交替更新乘子估计和增大惩罚参数，最终在有限惩罚参数下收敛到原问题的KKT点，避免了纯罚函数法中惩罚参数趋于无穷导致的病态问题。
构造混合罚函数（增广拉格朗日函数）
对于一般问题：

\[ \min f(x), \quad \text{s.t.} \quad g_i(x) \le 0, \quad h_j(x)=0 \]

引入松弛变量 $s_i \ge 0$ 将不等式约束转化为等式：$g_i(x)+s_i=0$。对应的增广拉格朗日函数为：

\[ L_\rho(x,s,\lambda,\mu) = f(x) + \sum_i \left[ \lambda_i (g_i(x)+s_i) + \frac{\rho}{2} (g_i(x)+s_i)^2 \right] + \sum_j \left[ \mu_j h_j(x) + \frac{\rho}{2} h_j(x)^2 \right] \]

其中 $\lambda_i \ge 0$ 为不等式约束乘子，$\mu_j$ 为等式约束乘子，$\rho > 0$ 为惩罚参数。通过关于 $s_i$ 最小化（由于 $s_i \ge 0$），可消去 $s_i$，得到简化形式：

\[ \phi_\rho(x,\lambda,\mu) = f(x) + \frac{1}{2\rho} \sum_i \left[ (\max(0, \lambda_i + \rho g_i(x)))^2 - \lambda_i^2 \right] + \sum_j \left[ \mu_j h_j(x) + \frac{\rho}{2} h_j(x)^2 \right] \]

此即实际计算中使用的混合罚函数。对于本例，代入具体函数：

不等式约束 $g_1(x) \le 0$ 对应乘子 $\lambda_1 \ge 0$，惩罚项为：

\[ P_1 = \frac{1}{2\rho} \left[ (\max(0, \lambda_1 + \rho (x_1+x_2-4)))^2 - \lambda_1^2 \right] \]

不等式约束 $g_2(x) \le 0$（即 $-x_1 \le 0$）对应乘子 $\lambda_2 \ge 0$，惩罚项为：

\[ P_2 = \frac{1}{2\rho} \left[ (\max(0, \lambda_2 - \rho x_1))^2 - \lambda_2^2 \right] \]

等式约束 $h(x)=0$ 对应乘子 $\mu$，惩罚项为：

\[ P_3 = \mu (x_1^2 - x_2) + \frac{\rho}{2} (x_1^2 - x_2)^2 \]

因此混合罚函数为：

\[ \phi_\rho(x,\lambda,\mu) = (x_1-3)^2 + (x_2-2)^2 + P_1 + P_2 + P_3 \]

算法迭代步骤
步骤0：初始化
- 给定初始点 $x^{(0)}=(x_1^{(0)}, x_2^{(0)})$，例如 $(1,1)$。
- 初始化乘子 $\lambda_1^{(0)} \ge 0, \lambda_2^{(0)} \ge 0, \mu^{(0)}$，可取零。
- 初始惩罚参数 $\rho_0 > 0$（例如 $\rho_0=1$），放大系数 $\beta > 1$（例如 $\beta=10$）。
- 设定收敛容差 $\epsilon > 0$（例如 $10^{-6}$），置迭代计数 $k=0$。
步骤1：求解无约束子问题
固定当前乘子 $\lambda^{(k)},\mu^{(k)}$ 和惩罚参数 $\rho_k$，求解：

\[ x^{(k+1)} = \arg\min_{x \in \mathbb{R}^2} \phi_{\rho_k}(x, \lambda^{(k)}, \mu^{(k)}) \]

此子问题由于 $\phi$ 光滑可微，可用拟牛顿法（如BFGS）求解。需计算梯度：

\[ \begin{aligned} \nabla_{x_1} \phi &= 2(x_1-3) + \frac{\partial P_1}{\partial x_1} + \frac{\partial P_2}{\partial x_1} + \frac{\partial P_3}{\partial x_1} \\ \frac{\partial P_1}{\partial x_1} &= \begin{cases} \lambda_1 + \rho_k (x_1+x_2-4), & \text{if } \lambda_1 + \rho_k (x_1+x_2-4) > 0 \\ 0, & \text{otherwise} \end{cases} \\ \frac{\partial P_2}{\partial x_1} &= \begin{cases} -\lambda_2 + \rho_k x_1, & \text{if } \lambda_2 - \rho_k x_1 > 0 \\ 0, & \text{otherwise} \end{cases} \\ \frac{\partial P_3}{\partial x_1} &= 2\mu x_1 + \rho_k (x_1^2 - x_2) \cdot 2x_1 \end{aligned} \]

$x_2$ 梯度类似可得。用优化库或自行实现迭代求解至子问题收敛。

步骤2：检查收敛条件
计算约束违反度和乘子变化：

违反度：$\eta = \max\left\{ |x_1^2 - x_2|, \max(0, x_1+x_2-4), \max(0, -x_1) \right\}$
若 $\eta < \epsilon$ 且 $\|x^{(k+1)}-x^{(k)}\|$ 足够小，则停止，输出 $x^*=x^{(k+1)}$。

步骤3：更新乘子

对不等式约束：

\[ \begin{aligned} \lambda_1^{(k+1)} &= \max\left(0, \lambda_1^{(k)} + \rho_k (x_1^{(k+1)}+x_2^{(k+1)}-4)\right) \\ \lambda_2^{(k+1)} &= \max\left(0, \lambda_2^{(k)} - \rho_k x_1^{(k+1)}\right) \end{aligned} \]

对等式约束：

\[ \mu^{(k+1)} = \mu^{(k)} + \rho_k ( (x_1^{(k+1)})^2 - x_2^{(k+1)} ) \]

步骤4：更新惩罚参数
如果约束违反度 $\eta$ 相比上一次没有显著下降（例如减少不到一半），则增大惩罚参数以加强约束满足：

\[ \rho_{k+1} = \beta \rho_k \]

否则保持 $\rho_{k+1} = \rho_k$。

步骤5：迭代
置 $k := k+1$，返回步骤1。

算法特性说明
- 混合罚函数在乘子估计较好时，只需适中大小的 $\rho$ 即可使子问题解接近原问题解，避免了纯罚函数中 $\rho \to \infty$ 带来的数值困难。
- 乘子更新公式本质是梯度上升法对偶步，步长为 $\rho_k$。
- 收敛时，$x^*$ 满足原问题KKT条件，乘子 $(\lambda^*,\mu^*)$ 即为最优拉格朗日乘子。
本题预期结果
该问题最优解可通过解析法验证：从 $x_1^2=x_2$ 和 $x_1 \ge 0$ 代入约束，得到可行域为曲线一段。最终解约为 $x^* \approx (1.00, 1.00)$（确切解需数值求解），此时 $g_1(x^*)<0$ 非积极，$g_2$ 在边界 $x_1=0$ 可能积极，等式约束满足。混合罚函数法应在10-20次外层迭代内收敛到高精度解。

非线性规划中的混合罚函数法进阶题题目描述：考虑如下非线性规划问题： $$ \begin{aligned} \min_ {x \in \mathbb{R}^2} \quad & f(x) = (x_ 1 - 3)^2 + (x_ 2 - 2)^2 \\ \text{s.t.} \quad & g_ 1(x) = x_ 1 + x_ 2 - 4 \le 0 \\ & g_ 2(x) = -x_ 1 \le 0 \\ & h(x) = x_ 1^2 - x_ 2 = 0 \end{aligned} $$ 请使用混合罚函数法（也称为“乘子罚函数法”或“增广拉格朗日法”）求解此问题。要求详细推导混合罚函数的构造，并阐述算法迭代步骤，包括如何更新拉格朗日乘子和惩罚参数，直到满足收敛条件。解题过程：算法思想回顾混合罚函数法结合了拉格朗日乘子法和罚函数法的优点。其核心思想是：对等式约束和不等式约束，构造一个“增广拉格朗日函数”，其中包含拉格朗日乘子项和惩罚项。通过交替更新乘子估计和增大惩罚参数，最终在有限惩罚参数下收敛到原问题的KKT点，避免了纯罚函数法中惩罚参数趋于无穷导致的病态问题。构造混合罚函数（增广拉格朗日函数）对于一般问题： $$ \min f(x), \quad \text{s.t.} \quad g_ i(x) \le 0, \quad h_ j(x)=0 $$ 引入松弛变量 $s_ i \ge 0$ 将不等式约束转化为等式：$g_ i(x)+s_ i=0$。对应的增广拉格朗日函数为： $$ L_ \rho(x,s,\lambda,\mu) = f(x) + \sum_ i \left[ \lambda_ i (g_ i(x)+s_ i) + \frac{\rho}{2} (g_ i(x)+s_ i)^2 \right] + \sum_ j \left[ \mu_ j h_ j(x) + \frac{\rho}{2} h_ j(x)^2 \right ] $$ 其中 $\lambda_ i \ge 0$ 为不等式约束乘子，$\mu_ j$ 为等式约束乘子，$\rho > 0$ 为惩罚参数。通过关于 $s_ i$ 最小化（由于 $s_ i \ge 0$），可消去 $s_ i$，得到简化形式： $$ \phi_ \rho(x,\lambda,\mu) = f(x) + \frac{1}{2\rho} \sum_ i \left[ (\max(0, \lambda_ i + \rho g_ i(x)))^2 - \lambda_ i^2 \right] + \sum_ j \left[ \mu_ j h_ j(x) + \frac{\rho}{2} h_ j(x)^2 \right ] $$ 此即实际计算中使用的混合罚函数。对于本例，代入具体函数：不等式约束 $g_ 1(x) \le 0$ 对应乘子 $\lambda_ 1 \ge 0$，惩罚项为： $$ P_ 1 = \frac{1}{2\rho} \left[ (\max(0, \lambda_ 1 + \rho (x_ 1+x_ 2-4)))^2 - \lambda_ 1^2 \right ] $$ 不等式约束 $g_ 2(x) \le 0$（即 $-x_ 1 \le 0$）对应乘子 $\lambda_ 2 \ge 0$，惩罚项为： $$ P_ 2 = \frac{1}{2\rho} \left[ (\max(0, \lambda_ 2 - \rho x_ 1))^2 - \lambda_ 2^2 \right ] $$ 等式约束 $h(x)=0$ 对应乘子 $\mu$，惩罚项为： $$ P_ 3 = \mu (x_ 1^2 - x_ 2) + \frac{\rho}{2} (x_ 1^2 - x_ 2)^2 $$ 因此混合罚函数为： $$ \phi_ \rho(x,\lambda,\mu) = (x_ 1-3)^2 + (x_ 2-2)^2 + P_ 1 + P_ 2 + P_ 3 $$ 算法迭代步骤步骤0：初始化给定初始点 $x^{(0)}=(x_ 1^{(0)}, x_ 2^{(0)})$，例如 $(1,1)$。初始化乘子 $\lambda_ 1^{(0)} \ge 0, \lambda_ 2^{(0)} \ge 0, \mu^{(0)}$，可取零。初始惩罚参数 $\rho_ 0 > 0$（例如 $\rho_ 0=1$），放大系数 $\beta > 1$（例如 $\beta=10$）。设定收敛容差 $\epsilon > 0$（例如 $10^{-6}$），置迭代计数 $k=0$。步骤1：求解无约束子问题固定当前乘子 $\lambda^{(k)},\mu^{(k)}$ 和惩罚参数 $\rho_ k$，求解： $$ x^{(k+1)} = \arg\min_ {x \in \mathbb{R}^2} \phi_ {\rho_ k}(x, \lambda^{(k)}, \mu^{(k)}) $$ 此子问题由于 $\phi$ 光滑可微，可用拟牛顿法（如BFGS）求解。需计算梯度： $$ \begin{aligned} \nabla_ {x_ 1} \phi &= 2(x_ 1-3) + \frac{\partial P_ 1}{\partial x_ 1} + \frac{\partial P_ 2}{\partial x_ 1} + \frac{\partial P_ 3}{\partial x_ 1} \\ \frac{\partial P_ 1}{\partial x_ 1} &= \begin{cases} \lambda_ 1 + \rho_ k (x_ 1+x_ 2-4), & \text{if } \lambda_ 1 + \rho_ k (x_ 1+x_ 2-4) > 0 \\ 0, & \text{otherwise} \end{cases} \\ \frac{\partial P_ 2}{\partial x_ 1} &= \begin{cases} -\lambda_ 2 + \rho_ k x_ 1, & \text{if } \lambda_ 2 - \rho_ k x_ 1 > 0 \\ 0, & \text{otherwise} \end{cases} \\ \frac{\partial P_ 3}{\partial x_ 1} &= 2\mu x_ 1 + \rho_ k (x_ 1^2 - x_ 2) \cdot 2x_ 1 \end{aligned} $$ $x_ 2$ 梯度类似可得。用优化库或自行实现迭代求解至子问题收敛。步骤2：检查收敛条件计算约束违反度和乘子变化：违反度：$\eta = \max\left\{ |x_ 1^2 - x_ 2|, \max(0, x_ 1+x_ 2-4), \max(0, -x_ 1) \right\}$ 若 $\eta < \epsilon$ 且 $\|x^{(k+1)}-x^{(k)}\|$ 足够小，则停止，输出 $x^* =x^{(k+1)}$。步骤3：更新乘子对不等式约束： $$ \begin{aligned} \lambda_ 1^{(k+1)} &= \max\left(0, \lambda_ 1^{(k)} + \rho_ k (x_ 1^{(k+1)}+x_ 2^{(k+1)}-4)\right) \\ \lambda_ 2^{(k+1)} &= \max\left(0, \lambda_ 2^{(k)} - \rho_ k x_ 1^{(k+1)}\right) \end{aligned} $$ 对等式约束： $$ \mu^{(k+1)} = \mu^{(k)} + \rho_ k ( (x_ 1^{(k+1)})^2 - x_ 2^{(k+1)} ) $$ 步骤4：更新惩罚参数如果约束违反度 $\eta$ 相比上一次没有显著下降（例如减少不到一半），则增大惩罚参数以加强约束满足： $$ \rho_ {k+1} = \beta \rho_ k $$ 否则保持 $\rho_ {k+1} = \rho_ k$。步骤5：迭代置 $k := k+1$，返回步骤1。算法特性说明混合罚函数在乘子估计较好时，只需适中大小的 $\rho$ 即可使子问题解接近原问题解，避免了纯罚函数中 $\rho \to \infty$ 带来的数值困难。乘子更新公式本质是梯度上升法对偶步，步长为 $\rho_ k$。收敛时，$x^ $ 满足原问题KKT条件，乘子 $(\lambda^ ,\mu^* )$ 即为最优拉格朗日乘子。本题预期结果该问题最优解可通过解析法验证：从 $x_ 1^2=x_ 2$ 和 $x_ 1 \ge 0$ 代入约束，得到可行域为曲线一段。最终解约为 $x^* \approx (1.00, 1.00)$（确切解需数值求解），此时 $g_ 1(x^* )<0$ 非积极，$g_ 2$ 在边界 $x_ 1=0$ 可能积极，等式约束满足。混合罚函数法应在10-20次外层迭代内收敛到高精度解。