外点罚函数法基础题
字数 2299 2025-10-27 11:27:25

外点罚函数法基础题

题目描述
考虑非线性规划问题：
最小化 \(f(x)1 = x_1^2 + x_2^2\)
满足约束 \(g(x) = x_1 + x_2 - 1 \geq 0\)
初始点 \(x^{(0)} = (0, 0)\)，该点不满足约束 \(g(x) \geq 0\)。

请使用外点罚函数法求解该问题，详细说明构造罚函数、求解无约束子问题以及参数更新的过程。

解题过程

  1. 方法原理介绍
    外点罚函数法用于求解约束优化问题。其核心思想是将约束违反量作为惩罚项加入原目标函数，构造一个无约束优化问题。通过逐步增大惩罚因子，迫使解趋向可行域。

  2. 构造罚函数

  • 对于不等式约束 \(g(x) \geq 0 \，惩罚项定义为 \( \max(0, -g(x))^2\)
  • 罚函数形式：\(P(x, \mu) = f(x) + \mu \cdot \max(0, -g(x))^2\)
  • 代入本题函数：
    \(P(x, \mu) = x_1^2 + x_2^2 + \mu \cdot \max(0, -(x_1 + x_2 - 1))^2\)
  • 由于初始点 \(x^{(0)} = (0,0)\) 不满足约束（\(0+0-1 = -1 < 0\)），惩罚项激活：
    \(P(x, \mu) = x_1^2 + x_2^2 + \mu \cdot (1 - x_1 - x_2)^2\)
  1. 求解无约束子问题（μ=1）
  • 令初始惩罚因子 \(\mu_1 = 1\)，最小化 \(P(x,1) = x_1^2 + x_2^2 + (1 - x_1 - x_2)^2\)
  • 求梯度并令其为零：
    \(\frac{\partial P}{\partial x_1} = 2x_1 - 2(1 - x_1 - x_2) = 4x_1 + 2x_2 - 2 = 0\)
    \(\frac{\partial P}{\partial x_2} = 2x_2 - 2(1 - x_1 - x_2) = 2x_1 + 4x_2 - 2 = 0\)
  • 解得线性方程组：
    \(4x_1 + 2x_2 = 2\)
    \(2x_1 + 4x_2 = 2\)
  • 解为：\(x_1^{(1)} = \frac{1}{3}, x_2^{(1)} = \frac{1}{3}\)，此时约束函数值 \(g(x^{(1)}) = \frac{1}{3} + \frac{1}{3} - 1 = -\frac{1}{3} < 0\)，仍不可行。
  1. 增大惩罚因子（μ=10）
  • 令 \(\mu_2 = 10\)，最小化 \(P(x,10) = x_1^2 + x_2^2 + 10(1 - x_1 - x_2)^2\)
  • 求梯度并令其为零：
    \(\frac{\partial P}{\partial x_1} = 2x_1 - 20(1 - x_1 - x_2) = 22x_1 + 20x_2 - 20 = 0\)
    \(\frac{\partial P}{\partial x_2} = 2x_2 - 20(1 - x_1 - x_2) = 20x_1 + 22x_2 - 20 = 0\)
  • 解得：\(x_1^{(2)} = \frac{10}{21} \approx 0.476, x_2^{(2)} = \frac{10}{21} \approx 0.476\)
  • 约束函数值 \(g(x^{(2)}) \approx 0.476 + 0.476 - 1 = -0.048 < 0\)，接近可行域边界。
  1. 进一步增大惩罚因子（μ=100）
  • 令 \(\mu_3 = 100\)，最小化 \(P(x,100) = x_1^2 + x_2^2 + 100(1 - x_1 - x_2)^2\)
  • 求梯度并令其为零：
    \(\frac{\partial P}{\partial x_1} = 2x_1 - 200(1 - x_1 - x_2) = 202x_1 + 200x_2 - 200 = 0\)
    \(\frac{\partial P}{\partial x_2} = 2x_2 - 200(1 - x_1 - x_2) = 200x_1 + 202x_2 - 200 = 0\)
  • 解得：\(x_1^{(3)} = \frac{100}{201} \approx 0.4975, x_2^{(3)} = \frac{100}{201} \approx 0.4975\)
  • 约束函数值 \(g(x^{(3)}) \approx 0.995 - 1 = -0.005\)，非常接近可行域。
  1. 收敛分析
  • 当 \(\mu \to \infty\)，解趋近 \(x_1 = x_2 = 0.5\)，此时约束严格满足 \(g(x) = 0\)（在边界上）
  • 原问题的最优解确实为 \((0.5, 0.5)\)，目标函数值 \(f(x) = 0.5\)
  • 外点罚函数法的解从不可行域逐渐逼近可行域边界，惩罚因子越大，近似解越接近真实解。

关键点总结

  • 外点罚函数法允许从不可行点开始迭代
  • 惩罚项针对约束违反量进行二次惩罚
  • 通过增大惩罚因子迫使解进入可行域
  • 优点：初始点选择灵活；缺点：大μ值可能导致数值困难
外点罚函数法基础题 题目描述 考虑非线性规划问题： 最小化 \( f(x)1 = x_ 1^2 + x_ 2^2 \) 满足约束 \( g(x) = x_ 1 + x_ 2 - 1 \geq 0 \) 初始点 \( x^{(0)} = (0, 0) \)，该点不满足约束 \( g(x) \geq 0 \)。 请使用外点罚函数法求解该问题，详细说明构造罚函数、求解无约束子问题以及参数更新的过程。 解题过程 方法原理介绍 外点罚函数法用于求解约束优化问题。其核心思想是将约束违反量作为惩罚项加入原目标函数，构造一个无约束优化问题。通过逐步增大惩罚因子，迫使解趋向可行域。 构造罚函数 对于不等式约束 \( g(x) \geq 0 \，惩罚项定义为 \( \max(0, -g(x))^2 \) 罚函数形式：\( P(x, \mu) = f(x) + \mu \cdot \max(0, -g(x))^2 \) 代入本题函数： \( P(x, \mu) = x_ 1^2 + x_ 2^2 + \mu \cdot \max(0, -(x_ 1 + x_ 2 - 1))^2 \) 由于初始点 \( x^{(0)} = (0,0) \) 不满足约束（\( 0+0-1 = -1 < 0 \)），惩罚项激活： \( P(x, \mu) = x_ 1^2 + x_ 2^2 + \mu \cdot (1 - x_ 1 - x_ 2)^2 \) 求解无约束子问题（μ=1） 令初始惩罚因子 \( \mu_ 1 = 1 \)，最小化 \( P(x,1) = x_ 1^2 + x_ 2^2 + (1 - x_ 1 - x_ 2)^2 \) 求梯度并令其为零： \( \frac{\partial P}{\partial x_ 1} = 2x_ 1 - 2(1 - x_ 1 - x_ 2) = 4x_ 1 + 2x_ 2 - 2 = 0 \) \( \frac{\partial P}{\partial x_ 2} = 2x_ 2 - 2(1 - x_ 1 - x_ 2) = 2x_ 1 + 4x_ 2 - 2 = 0 \) 解得线性方程组： \( 4x_ 1 + 2x_ 2 = 2 \) \( 2x_ 1 + 4x_ 2 = 2 \) 解为：\( x_ 1^{(1)} = \frac{1}{3}, x_ 2^{(1)} = \frac{1}{3} \)，此时约束函数值 \( g(x^{(1)}) = \frac{1}{3} + \frac{1}{3} - 1 = -\frac{1}{3} < 0 \)，仍不可行。 增大惩罚因子（μ=10） 令 \( \mu_ 2 = 10 \)，最小化 \( P(x,10) = x_ 1^2 + x_ 2^2 + 10(1 - x_ 1 - x_ 2)^2 \) 求梯度并令其为零： \( \frac{\partial P}{\partial x_ 1} = 2x_ 1 - 20(1 - x_ 1 - x_ 2) = 22x_ 1 + 20x_ 2 - 20 = 0 \) \( \frac{\partial P}{\partial x_ 2} = 2x_ 2 - 20(1 - x_ 1 - x_ 2) = 20x_ 1 + 22x_ 2 - 20 = 0 \) 解得：\( x_ 1^{(2)} = \frac{10}{21} \approx 0.476, x_ 2^{(2)} = \frac{10}{21} \approx 0.476 \) 约束函数值 \( g(x^{(2)}) \approx 0.476 + 0.476 - 1 = -0.048 < 0 \)，接近可行域边界。 进一步增大惩罚因子（μ=100） 令 \( \mu_ 3 = 100 \)，最小化 \( P(x,100) = x_ 1^2 + x_ 2^2 + 100(1 - x_ 1 - x_ 2)^2 \) 求梯度并令其为零： \( \frac{\partial P}{\partial x_ 1} = 2x_ 1 - 200(1 - x_ 1 - x_ 2) = 202x_ 1 + 200x_ 2 - 200 = 0 \) \( \frac{\partial P}{\partial x_ 2} = 2x_ 2 - 200(1 - x_ 1 - x_ 2) = 200x_ 1 + 202x_ 2 - 200 = 0 \) 解得：\( x_ 1^{(3)} = \frac{100}{201} \approx 0.4975, x_ 2^{(3)} = \frac{100}{201} \approx 0.4975 \) 约束函数值 \( g(x^{(3)}) \approx 0.995 - 1 = -0.005 \)，非常接近可行域。 收敛分析 当 \( \mu \to \infty \)，解趋近 \( x_ 1 = x_ 2 = 0.5 \)，此时约束严格满足 \( g(x) = 0 \)（在边界上） 原问题的最优解确实为 \( (0.5, 0.5) \)，目标函数值 \( f(x) = 0.5 \) 外点罚函数法的解从不可行域逐渐逼近可行域边界，惩罚因子越大，近似解越接近真实解。 关键点总结 外点罚函数法允许从不可行点开始迭代 惩罚项针对约束违反量进行二次惩罚 通过增大惩罚因子迫使解进入可行域 优点：初始点选择灵活；缺点：大μ值可能导致数值困难