非线性规划中的共轭梯度法基础题

字数 3308 2025-10-27 08:13:40

非线性规划中的共轭梯度法基础题

题目描述
考虑无约束非线性规划问题：

\[\min f(x) = x_1^2 + 2x_2^2 + 2x_1x_2 + 2x_1 + 6x_2 \]

初始点取为 \(x^{(0)} = (0, 0)\)，使用共轭梯度法（Fletcher-Reeves公式）求解该问题的极小值点。

解题过程

1. 问题分析
目标函数为二次函数，可写成矩阵形式：

\[f(x) = \frac{1}{2} x^T A x + b^T x, \quad A = \begin{bmatrix} 2 & 2 \\ 2 & 4 \end{bmatrix}, \quad b = \begin{bmatrix} 2 \\ 6 \end{bmatrix} \]

（注意：原函数展开后二次项系数需调整，这里重新配平：\(x_1^2 + 2x_2^2 + 2x_1x_2 = \frac{1}{2}(2x_1^2 + 4x_2^2 + 4x_1x_2)\)，故 \(A\) 如上所示。）
梯度为：

\[\nabla f(x) = A x + b = \begin{bmatrix} 2x_1 + 2x_2 + 2 \\ 2x_1 + 4x_2 + 6 \end{bmatrix} \]

2. 共轭梯度法原理
用于求解无约束优化问题，特别适合二次函数。步骤：

初始点 \(x^{(0)}\)，计算梯度 \(g_0 = \nabla f(x^{(0)})\)，初始搜索方向 \(d_0 = -g_0\)。
沿 \(d_k\) 进行一维搜索（精确线搜索），求步长 \(\alpha_k\) 使 \(f(x^{(k)} + \alpha_k d_k)\) 最小。
更新点：\(x^{(k+1)} = x^{(k)} + \alpha_k d_k\)。
计算新梯度 \(g_{k+1} = \nabla f(x^{(k+1)})\)。
用 Fletcher-Reeves 公式计算共轭方向：

\[\beta_k = \frac{\|g_{k+1}\|^2}{\|g_k\|^2}, \quad d_{k+1} = -g_{k+1} + \beta_k d_k \]

重复直到梯度足够小。

3. 迭代计算

第 1 步（k=0）

\(x^{(0)} = (0, 0)\)
\(g_0 = \nabla f(0,0) = (2, 6)\)，\(d_0 = -g_0 = (-2, -6)\)
线搜索：优化 \(\phi(\alpha) = f(x^{(0)} + \alpha d_0) = f(-2\alpha, -6\alpha)\)
代入函数：

\[\phi(\alpha) = (-2\alpha)^2 + 2(-6\alpha)^2 + 2(-2\alpha)(-6\alpha) + 2(-2\alpha) + 6(-6\alpha) \]

化简：

\[\phi(\alpha) = 4\alpha^2 + 72\alpha^2 + 24\alpha^2 - 4\alpha - 36\alpha = 100\alpha^2 - 40\alpha \]

求导：\(\phi'(\alpha) = 200\alpha - 40 = 0 \Rightarrow \alpha_0 = 0.2\)

更新：\(x^{(1)} = (0, 0) + 0.2(-2, -6) = (-0.4, -1.2)\)
\(g_1 = \nabla f(-0.4, -1.2) = (2(-0.4) + 2(-1.2) + 2, 2(-0.4) + 4(-1.2) + 6)\)
计算：

\[g_1 = (-0.8 - 2.4 + 2, -0.8 - 4.8 + 6) = (-1.2, 0.4) \]

第 2 步（k=1）

\(\beta_0 = \frac{\|g_1\|^2}{\|g_0\|^2} = \frac{(-1.2)^2 + (0.4)^2}{2^2 + 6^2} = \frac{1.44 + 0.16}{4 + 36} = \frac{1.6}{40} = 0.04\)
\(d_1 = -g_1 + \beta_0 d_0 = -(-1.2, 0.4) + 0.04(-2, -6) = (1.2, -0.4) + (-0.08, -0.24) = (1.12, -0.64)\)
线搜索：设 \(x^{(1)} + \alpha d_1 = (-0.4 + 1.12\alpha, -1.2 - 0.64\alpha)\)
代入 \(f(x)\) 并化简得：

\[\phi(\alpha) = [2(1.12)^2 + 4(0.64)^2 + 4(1.12)(-0.64)] \frac{\alpha^2}{2} + [2(-0.4)(1.12) + 4(-1.2)(-0.64) + 2(1.12) + 6(-0.64)] \alpha + \text{常数} \]

计算系数（忽略常数项）：
二次项系数：\(2(1.2544) + 4(0.4096) - 4(0.7168) = 2.5088 + 1.6384 - 2.8672 = 1.28\)
一次项系数：\(-0.896 + 3.072 + 2.24 - 3.84 = 0.576\)
（注意：这里需完整展开，但简便法：由于共轭性，二次函数在共轭方向上前两步即可收敛，可直接解 \(\phi'(\alpha)=0\)）
实际上，对于二次函数，共轭梯度法在 n 步内收敛（n 为变量数）。这里 n=2，第二次线搜索直接得到极小点。
解 \(\alpha_1\)：由 \(\nabla f(x^{(1)} + \alpha d_1) \cdot d_1 = 0\)：

\[g_1 \cdot d_1 + \alpha (A d_1) \cdot d_1 = 0 \]

先算 \(A d_1 = \begin{bmatrix} 2 & 2 \\ 2 & 4 \end{bmatrix} \begin{bmatrix} 1.12 \\ -0.64 \end{bmatrix} = (2.24 - 1.28, 2.24 - 2.56) = (0.96, -0.32)\)
\((A d_1) \cdot d_1 = 0.96 \times 1.12 + (-0.32) \times (-0.64) = 1.0752 + 0.2048 = 1.28\)
\(g_1 \cdot d_1 = (-1.2)(1.12) + (0.4)(-0.64) = -1.344 - 0.256 = -1.6\)
所以：\(-1.6 + \alpha \times 1.28 = 0 \Rightarrow \alpha_1 = 1.25\)

更新：\(x^{(2)} = (-0.4, -1.2) + 1.25(1.12, -0.64) = (-0.4 + 1.4, -1.2 - 0.8) = (1, -2)\)
梯度：\(g_2 = \nabla f(1, -2) = (2(1) + 2(-2) + 2, 2(1) + 4(-2) + 6) = (0, 0)\)

梯度为零，停止迭代。

4. 结论
极小点 \(x^* = (1, -2)\)，最小值 \(f(x^*) = 1^2 + 2(-2)^2 + 2(1)(-2) + 2(1) + 6(-2) = 1 + 8 - 4 + 2 - 12 = -5\)。
共轭梯度法在两步内收敛（因目标函数为二次函数且维数为 2）。

非线性规划中的共轭梯度法基础题题目描述考虑无约束非线性规划问题： \[ \min f(x) = x_ 1^2 + 2x_ 2^2 + 2x_ 1x_ 2 + 2x_ 1 + 6x_ 2 \] 初始点取为 \( x^{(0)} = (0, 0) \)，使用共轭梯度法（Fletcher-Reeves公式）求解该问题的极小值点。解题过程 1. 问题分析目标函数为二次函数，可写成矩阵形式： \[ f(x) = \frac{1}{2} x^T A x + b^T x, \quad A = \begin{bmatrix} 2 & 2 \\ 2 & 4 \end{bmatrix}, \quad b = \begin{bmatrix} 2 \\ 6 \end{bmatrix} \] （注意：原函数展开后二次项系数需调整，这里重新配平：\( x_ 1^2 + 2x_ 2^2 + 2x_ 1x_ 2 = \frac{1}{2}(2x_ 1^2 + 4x_ 2^2 + 4x_ 1x_ 2) \)，故 \( A \) 如上所示。）梯度为： \[ \nabla f(x) = A x + b = \begin{bmatrix} 2x_ 1 + 2x_ 2 + 2 \\ 2x_ 1 + 4x_ 2 + 6 \end{bmatrix} \] 2. 共轭梯度法原理用于求解无约束优化问题，特别适合二次函数。步骤：初始点 \( x^{(0)} \)，计算梯度 \( g_ 0 = \nabla f(x^{(0)}) \)，初始搜索方向 \( d_ 0 = -g_ 0 \)。沿 \( d_ k \) 进行一维搜索（精确线搜索），求步长 \( \alpha_ k \) 使 \( f(x^{(k)} + \alpha_ k d_ k) \) 最小。更新点：\( x^{(k+1)} = x^{(k)} + \alpha_ k d_ k \)。计算新梯度 \( g_ {k+1} = \nabla f(x^{(k+1)}) \)。用 Fletcher-Reeves 公式计算共轭方向： \[ \beta_ k = \frac{\|g_ {k+1}\|^2}{\|g_ k\|^2}, \quad d_ {k+1} = -g_ {k+1} + \beta_ k d_ k \] 重复直到梯度足够小。 3. 迭代计算第 1 步（k=0） \( x^{(0)} = (0, 0) \) \( g_ 0 = \nabla f(0,0) = (2, 6) \)，\( d_ 0 = -g_ 0 = (-2, -6) \) 线搜索：优化 \( \phi(\alpha) = f(x^{(0)} + \alpha d_ 0) = f(-2\alpha, -6\alpha) \) 代入函数： \[ \phi(\alpha) = (-2\alpha)^2 + 2(-6\alpha)^2 + 2(-2\alpha)(-6\alpha) + 2(-2\alpha) + 6(-6\alpha) \] 化简： \[ \phi(\alpha) = 4\alpha^2 + 72\alpha^2 + 24\alpha^2 - 4\alpha - 36\alpha = 100\alpha^2 - 40\alpha \] 求导：\( \phi'(\alpha) = 200\alpha - 40 = 0 \Rightarrow \alpha_ 0 = 0.2 \) 更新：\( x^{(1)} = (0, 0) + 0.2(-2, -6) = (-0.4, -1.2) \) \( g_ 1 = \nabla f(-0.4, -1.2) = (2(-0.4) + 2(-1.2) + 2, 2(-0.4) + 4(-1.2) + 6) \) 计算： \[ g_ 1 = (-0.8 - 2.4 + 2, -0.8 - 4.8 + 6) = (-1.2, 0.4) \] 第 2 步（k=1） \( \beta_ 0 = \frac{\|g_ 1\|^2}{\|g_ 0\|^2} = \frac{(-1.2)^2 + (0.4)^2}{2^2 + 6^2} = \frac{1.44 + 0.16}{4 + 36} = \frac{1.6}{40} = 0.04 \) \( d_ 1 = -g_ 1 + \beta_ 0 d_ 0 = -(-1.2, 0.4) + 0.04(-2, -6) = (1.2, -0.4) + (-0.08, -0.24) = (1.12, -0.64) \) 线搜索：设 \( x^{(1)} + \alpha d_ 1 = (-0.4 + 1.12\alpha, -1.2 - 0.64\alpha) \) 代入 \( f(x) \) 并化简得： \[ \phi(\alpha) = [ 2(1.12)^2 + 4(0.64)^2 + 4(1.12)(-0.64)] \frac{\alpha^2}{2} + [ 2(-0.4)(1.12) + 4(-1.2)(-0.64) + 2(1.12) + 6(-0.64) ] \alpha + \text{常数} \] 计算系数（忽略常数项）：二次项系数：\( 2(1.2544) + 4(0.4096) - 4(0.7168) = 2.5088 + 1.6384 - 2.8672 = 1.28 \) 一次项系数：\( -0.896 + 3.072 + 2.24 - 3.84 = 0.576 \) （注意：这里需完整展开，但简便法：由于共轭性，二次函数在共轭方向上前两步即可收敛，可直接解 \( \phi'(\alpha)=0 \)）实际上，对于二次函数，共轭梯度法在 n 步内收敛（n 为变量数）。这里 n=2，第二次线搜索直接得到极小点。解 \( \alpha_ 1 \)：由 \( \nabla f(x^{(1)} + \alpha d_ 1) \cdot d_ 1 = 0 \)： \[ g_ 1 \cdot d_ 1 + \alpha (A d_ 1) \cdot d_ 1 = 0 \] 先算 \( A d_ 1 = \begin{bmatrix} 2 & 2 \\ 2 & 4 \end{bmatrix} \begin{bmatrix} 1.12 \\ -0.64 \end{bmatrix} = (2.24 - 1.28, 2.24 - 2.56) = (0.96, -0.32) \) \( (A d_ 1) \cdot d_ 1 = 0.96 \times 1.12 + (-0.32) \times (-0.64) = 1.0752 + 0.2048 = 1.28 \) \( g_ 1 \cdot d_ 1 = (-1.2)(1.12) + (0.4)(-0.64) = -1.344 - 0.256 = -1.6 \) 所以：\( -1.6 + \alpha \times 1.28 = 0 \Rightarrow \alpha_ 1 = 1.25 \) 更新：\( x^{(2)} = (-0.4, -1.2) + 1.25(1.12, -0.64) = (-0.4 + 1.4, -1.2 - 0.8) = (1, -2) \) 梯度：\( g_ 2 = \nabla f(1, -2) = (2(1) + 2(-2) + 2, 2(1) + 4(-2) + 6) = (0, 0) \) 梯度为零，停止迭代。 4. 结论极小点 \( x^* = (1, -2) \)，最小值 \( f(x^* ) = 1^2 + 2(-2)^2 + 2(1)(-2) + 2(1) + 6(-2) = 1 + 8 - 4 + 2 - 12 = -5 \)。共轭梯度法在两步内收敛（因目标函数为二次函数且维数为 2）。