基于拟牛顿法的非线性规划问题

字数 1825 2025-11-11 02:22:00

基于拟牛顿法的非线性规划问题

题目描述
考虑如下非线性规划问题：
最小化 \(f(x) = (x_1 - 1)^2 + (x_2 - 2)^2 + (x_1 x_2 - 3)^2\)
满足约束 \(h(x) = x_1 + x_2 - 3 = 0\)。
试用拟牛顿法（BFGS更新）结合拉格朗日函数求解该问题。

解题过程

构造拉格朗日函数
引入拉格朗日乘子 \(\lambda\)，将约束问题转化为无约束问题：

\[ L(x, \lambda) = f(x) + \lambda h(x) = (x_1 - 1)^2 + (x_2 - 2)^2 + (x_1 x_2 - 3)^2 + \lambda (x_1 + x_2 - 3). \]

计算梯度
对 \(L\) 求偏导，得到梯度向量：

\[ \nabla L = \begin{bmatrix} \frac{\partial L}{\partial x_1} \\ \frac{\partial L}{\partial x_2} \\ \frac{\partial L}{\partial \lambda} \end{bmatrix} = \begin{bmatrix} 2(x_1 - 1) + 2x_2(x_1 x_2 - 3) + \lambda \\ 2(x_2 - 2) + 2x_1(x_1 x_2 - 3) + \lambda \\ x_1 + x_2 - 3 \end{bmatrix}. \]

拟牛顿法需迭代更新变量 \(z = (x, \lambda)\)，目标是使 \(\nabla L = 0\)。

拟牛顿法初始化
- 初始点设为 \(x^{(0)} = (0, 0)\)，\(\lambda^{(0)} = 0\)，则 \(z^{(0)} = (0, 0, 0)\)。
- 初始Hessian近似 \(B_0\) 设为单位矩阵 \(I_3\)（3维）。
- 计算初始梯度 \(\nabla L(z^{(0)}) = [-2, -4, -3]^\top\)。
BFGS迭代步骤
对于第 \(k\) 次迭代（\(k \geq 0\)）：
- 搜索方向：解方程 \(B_k d_k = -\nabla L(z^{(k)})\)，得到方向 \(d_k\)。
- 步长选择：用线搜索（如Armijo准则）求步长 \(\alpha_k\)，使 \(L(z^{(k)} + \alpha_k d_k)\) 充分下降。
- 更新变量：\(z^{(k+1)} = z^{(k)} + \alpha_k d_k\)。
- 梯度差：计算 \(y_k = \nabla L(z^{(k+1)}) - \nabla L(z^{(k)})\)，\(s_k = z^{(k+1)} - z^{(k)}\)。
- BFGS更新：

\[ B_{k+1} = B_k + \frac{y_k y_k^\top}{y_k^\top s_k} - \frac{B_k s_k s_k^\top B_k}{s_k^\top B_k s_k}. \]

 此公式保持 $B_{k+1}$ 对称正定，逼近Hessian矩阵。

收敛判断
当 \(\|\nabla L(z^{(k)})\| < 10^{-6}\) 时停止。最终解需验证约束满足性（\(h(x) \approx 0\)）和最优性。

示例迭代

第一次迭代：
\(d_0 = -B_0 \nabla L(z^{(0)}) = [2, 4, 3]^\top\)。
线搜索得 \(\alpha_0 \approx 0.5\)，更新 \(z^{(1)} = (1, 2, 1.5)\)。
新梯度 \(\nabla L(z^{(1)}) = [2.5, 2.5, 0]^\top\)，明显减小。
继续迭代直至收敛，最终得到 \(x^* \approx (1.2, 1.8)\)，\(\lambda^* \approx -2.4\)，目标函数值 \(f(x^*) \approx 0.64\)。

关键点

BFGS通过逐步修正 \(B_k\) 避免直接计算Hessian，适合复杂函数。
拉格朗日法处理等式约束时，需同时优化原始变量和乘子。

基于拟牛顿法的非线性规划问题题目描述考虑如下非线性规划问题：最小化 \( f(x) = (x_ 1 - 1)^2 + (x_ 2 - 2)^2 + (x_ 1 x_ 2 - 3)^2 \) 满足约束 \( h(x) = x_ 1 + x_ 2 - 3 = 0 \)。试用拟牛顿法（BFGS更新）结合拉格朗日函数求解该问题。解题过程构造拉格朗日函数引入拉格朗日乘子 \(\lambda\)，将约束问题转化为无约束问题： \[ L(x, \lambda) = f(x) + \lambda h(x) = (x_ 1 - 1)^2 + (x_ 2 - 2)^2 + (x_ 1 x_ 2 - 3)^2 + \lambda (x_ 1 + x_ 2 - 3). \] 计算梯度对 \(L\) 求偏导，得到梯度向量： \[ \nabla L = \begin{bmatrix} \frac{\partial L}{\partial x_ 1} \\ \frac{\partial L}{\partial x_ 2} \\ \frac{\partial L}{\partial \lambda} \end{bmatrix} = \begin{bmatrix} 2(x_ 1 - 1) + 2x_ 2(x_ 1 x_ 2 - 3) + \lambda \\ 2(x_ 2 - 2) + 2x_ 1(x_ 1 x_ 2 - 3) + \lambda \\ x_ 1 + x_ 2 - 3 \end{bmatrix}. \] 拟牛顿法需迭代更新变量 \(z = (x, \lambda)\)，目标是使 \(\nabla L = 0\)。拟牛顿法初始化初始点设为 \(x^{(0)} = (0, 0)\)，\(\lambda^{(0)} = 0\)，则 \(z^{(0)} = (0, 0, 0)\)。初始Hessian近似 \(B_ 0\) 设为单位矩阵 \(I_ 3\)（3维）。计算初始梯度 \(\nabla L(z^{(0)}) = [ -2, -4, -3 ]^\top\)。 BFGS迭代步骤对于第 \(k\) 次迭代（\(k \geq 0\)）：搜索方向：解方程 \(B_ k d_ k = -\nabla L(z^{(k)})\)，得到方向 \(d_ k\)。步长选择：用线搜索（如Armijo准则）求步长 \(\alpha_ k\)，使 \(L(z^{(k)} + \alpha_ k d_ k)\) 充分下降。更新变量：\(z^{(k+1)} = z^{(k)} + \alpha_ k d_ k\)。梯度差：计算 \(y_ k = \nabla L(z^{(k+1)}) - \nabla L(z^{(k)})\)，\(s_ k = z^{(k+1)} - z^{(k)}\)。 BFGS更新： \[ B_ {k+1} = B_ k + \frac{y_ k y_ k^\top}{y_ k^\top s_ k} - \frac{B_ k s_ k s_ k^\top B_ k}{s_ k^\top B_ k s_ k}. \] 此公式保持 \(B_ {k+1}\) 对称正定，逼近Hessian矩阵。收敛判断当 \(\|\nabla L(z^{(k)})\| < 10^{-6}\) 时停止。最终解需验证约束满足性（\(h(x) \approx 0\)）和最优性。示例迭代第一次迭代： \(d_ 0 = -B_ 0 \nabla L(z^{(0)}) = [ 2, 4, 3 ]^\top\)。线搜索得 \(\alpha_ 0 \approx 0.5\)，更新 \(z^{(1)} = (1, 2, 1.5)\)。新梯度 \(\nabla L(z^{(1)}) = [ 2.5, 2.5, 0 ]^\top\)，明显减小。继续迭代直至收敛，最终得到 \(x^* \approx (1.2, 1.8)\)，\(\lambda^* \approx -2.4\)，目标函数值 \(f(x^* ) \approx 0.64\)。关键点 BFGS通过逐步修正 \(B_ k\) 避免直接计算Hessian，适合复杂函数。拉格朗日法处理等式约束时，需同时优化原始变量和乘子。