3-8 共轭方向法

共轭方向法

简述

\(\qquad\)上一篇介绍了坐标轮换法。它每次只沿一个坐标轴方向作一维搜索，原理简单，但对等值线斜置的椭圆，收敛很慢；遇到脊线还会失效。最速下降法则取负梯度方向，相邻两次搜索方向互相垂直，路径呈锯齿形，收敛同样不快。

\(\qquad\)这两种方法的共同问题是：搜索方向没有“配合”起来。坐标轮换法沿固定的坐标轴走，最速下降法只盯着当前点的负梯度，都没有利用前几次搜索已经得到的信息。于是自然要问：能不能选一组方向，使得对 \(n\) 元正定二次函数，沿这组方向依次作一维搜索，最多 \(n\) 次就能到达极小点？

\(\qquad\)答案是肯定的。这组方向就是共轭方向。共轭方向法（Conjugate Direction Method）是一类方法，它们的共同特点是迭代过程中利用一族共轭方向，区别在于构造共轭方向时所利用的关键信息不同。本篇介绍共轭方向的概念、性质、构造方法和迭代步骤；下一篇介绍利用梯度构造共轭方向的共轭梯度法。

共轭方向的概念

设 \(A\) 为 \(n \times n\) 阶正定对称矩阵。若一组非零向量 \(S_1, S_2, \dots, S_n\) 满足

则称这组向量关于矩阵 \(A\) 共轭，它们所表示的方向称为共轭方向。为与后文一致，下面也把这组向量记作 \(S^{(1)}, S^{(2)}, \dots, S^{(n)}\)。

当 \(A\) 取单位矩阵 \(I\) 时，条件化为

即这组向量相互正交。可见共轭是正交的推广，正交是共轭的特例：把内积中的单位矩阵换成正定矩阵 \(A\)，正交就成了共轭。

二次函数 \(f(X) = \frac{1}{2}X^T H X + B^T X + C\) 的二次项由 Hessian矩阵 \(H\) 决定，所以讨论二次函数的共轭方向时，定义中的 \(A\) 就取 \(H\)。

共轭方向的引入

先看二元的情形。设

为正定二元二次函数，\(H\) 为 \(2 \times 2\) 正定对称矩阵。

任选初始点 \(X^{(0)}\)，沿某个方向 \(S^{(0)}\) 作一维搜索，得到该方向上的极小点

由于 \(X^{(1)}\) 是沿 \(S^{(0)}\) 的极小点，函数在该点沿 \(S^{(0)}\) 的方向导数为零：

也就是说，\(S^{(0)}\) 与 \(X^{(1)}\) 处的梯度相互垂直。

再从 \(X^{(1)}\) 出发，沿另一个方向 \(S^{(1)}\) 作一维搜索，得到

希望 \(X^{(2)}\) 就是整个函数的极小点。由极值条件，应有 \(\nabla f(X^{(2)}) = 0\)。

二次函数的梯度为 \(\nabla f(X) = HX + B\)，于是

把 \(X^{(2)} = X^{(1)} + \alpha^{(1)} S^{(1)}\) 代入：

其中 \(HX^{(1)} + B = \nabla f(X^{(1)})\)，所以

用 \([S^{(0)}]^T\) 左乘上式：

第一项为零，且 \(\alpha^{(1)} \ne 0\)，故

\(\qquad\)上面的推导说明：要使 \(X^{(2)}\) 成为极小点，两个搜索方向必须关于 \(H\) 共轭。

\(\qquad\)反过来也成立：若 \(S^{(0)}\) 与 \(S^{(1)}\) 共轭，由 \(\nabla f(X^{(2)}) = \nabla f(X^{(1)}) + \alpha^{(1)} H S^{(1)}\) 可知 \(\nabla f(X^{(2)})\) 与 \(S^{(0)}\) 正交；又因为 \(X^{(2)}\) 是沿 \(S^{(1)}\) 的极小点，\(\nabla f(X^{(2)})\) 也与 \(S^{(1)}\) 正交。两个方向线性无关，所以 \(\nabla f(X^{(2)}) = 0\)。因此，对二元二次函数，两个共轭方向就够了。

\(\qquad\)图 4-8 画出了 \(S^{(0)}\) 取负梯度方向的情形：从 \(X^{(0)}\) 沿 \(-\nabla f(X^{(0)})\) 走到 \(X^{(1)}\) 后，如果继续沿负梯度走就会出现锯齿；改沿与 \(S^{(0)}\) 共轭的 \(S^{(1)}\) 走，就能直接到达 \(X^*\)。

符号说明：图中 \(x^0\)、\(x^1\)、\(x^*\) 对应正文的 \(X^{(0)}\)、\(X^{(1)}\)、\(X^*\)；\(d^0 = -\nabla f(x^0)\) 是第一次搜索的负梯度方向；图中从 \(x^1\) 指向 \(x^*\) 的方向标为 \(d^2\)，即正文的 \(S^{(1)}\)。

共轭方向的性质

性质 1：共轭向量组线性无关

\(\qquad\)设 \(A\) 为 \(n \times n\) 阶正定矩阵，\(S^{(i)}\ (i=1,2,\dots,n)\) 为关于 \(A\) 共轭的 \(n\) 个非零向量，则这组向量线性无关。

\(\qquad\)由性质 1 还可得到一个推论：\(n\) 维空间中，两两共轭的非零向量最多只有 \(n\) 个。因为 \(n+1\) 个向量在 \(n\) 维空间中必线性相关，而共轭的非零向量组线性无关。

性质 2：n 次搜索到达极小点

\(\qquad\)对于 \(n\) 元正定二次函数，若向量组 \(S^{(i)}\ (i=1,2,\dots,n)\) 关于函数的 Hessian矩阵 \(H\) 共轭，则从任意点 \(X^{(0)}\) 出发，依次沿这 \(n\) 个方向作一维搜索，最多只需 \(n\) 次搜索即可到达极小点。

\(\qquad\)二元情形的证明就是上一节：两个共轭方向对应两次搜索，第二个迭代点的梯度为零。\(n\) 元情形可按同样的思路归纳证明，这里不再展开。

\(\qquad\)这个性质是共轭方向法的出发点。坐标轮换法和最速下降法都没有保证方向共轭，所以即使对二次函数也要反复迭代，不能保证 \(n\) 步收敛。

性质 3：平行搜索产生共轭方向

\(\qquad\)对于二次函数 \(f(X) = \frac{1}{2}X^T H X + B^T X + C\)，从任意两个点 \(X_1^{(0)}\)、\(X_2^{(0)}\) 出发，分别沿同一方向 \(S^{(0)}\) 作一维搜索，得到两个一维极小点 \(X_1^{(1)}\)、\(X_2^{(1)}\)，则连接这两点的向量

与搜索方向 \(S^{(0)}\) 关于 \(H\) 共轭。

共轭方向的构造

\(\qquad\)性质 2 说明共轭方向能保证 \(n\) 步收敛，但还没有回答怎样得到共轭方向。常用构造方法有两类：平行搜索和利用梯度。本节先介绍平行搜索。

方法一：平行搜索

由性质 3，从两个点分别沿同一方向 \(S^{(0)}\) 搜索，把两个极小点连起来，就得到一个与 \(S^{(0)}\) 共轭的新方向。具体做法如下：

• ① 任取两个初始点 \(X_1^{(0)}\)、\(X_2^{(0)}\)，选定初始搜索方向 \(S^{(0)}\)；
• ② 分别从 \(X_1^{(0)}\)、\(X_2^{(0)}\) 出发，沿 \(S^{(0)}\) 作一维搜索，得到 \(X_1^{(1)}\)、\(X_2^{(1)}\)；
• ③ 令 \(S^{(1)} = X_1^{(1)} - X_2^{(1)}\)，则 \(S^{(1)}\) 与 \(S^{(0)}\) 关于 \(H\) 共轭。

\(\qquad\)对二元二次函数，得到 \(S^{(1)}\) 就够用了：从 \(X_1^{(1)}\)（或 \(X_2^{(1)}\)）出发，沿 \(S^{(1)}\) 再搜索一次，即可到达极小点。整个过程只用函数值，不需要梯度，也不需要 Hessian矩阵。

\(\qquad\)注意：两个初始点的连线不能与 \(S^{(0)}\) 平行。否则两次搜索会落在同一条搜索直线上，得到同一个极小点，\(S^{(1)} = 0\)，构造失败。例如取 \(X_1^{(0)} = [0,0]^T\)、\(X_2^{(0)} = [0,1]^T\)、\(S^{(0)} = [0,1]^T\)，两点连线与 \(S^{(0)}\) 平行，两次搜索都停在 \([0,0]^T\)。实际计算时，如果发现 \(\|S^{(1)}\|\) 接近零，就应重新选点或换一个初始方向。

\(\qquad\)平行搜索每次只能保证新方向与本次的搜索方向共轭。要用它组织 \(n\) 元问题的完整算法，还要处理方向替换和退化问题，这部分留到鲍威尔法再讨论。

方法二：利用梯度

另一种构造方式不需要预先选两个点，而是利用迭代点处的梯度。在第 \(k\) 步取

沿 \(S^{(k)}\) 作一维搜索得到 \(X^{(k+1)}\)，再令

只要适当选取系数 \(\beta^{(k)}\)，就能使 \(S^{(k+1)}\) 与 \(S^{(k)}\) 关于 \(H\) 共轭。这样构造出的方向只用到梯度，不需要 Hessian矩阵，这就是共轭梯度法。\(\beta^{(k)}\) 的具体表达式和完整步骤将在下一篇给出。

具体步骤

对于给定初始点 \(X^{(0)}\)、初始搜索方向 \(S^{(0)}\) 和收敛精度 \(\varepsilon\)：

① 令 \(k=0\)；

② 沿 \(S^{(k)}\) 作一维搜索，求最优步长 \(\alpha^{(k)}\)，得

③ 若 \(\|\nabla f(X^{(k+1)})\| < \varepsilon\)，则停止，输出 \(X^* = X^{(k+1)}\)；否则转④；

④ 构造新的共轭方向 \(S^{(k+1)}\)，使它和已有的 \(S^{(0)}, S^{(1)}, \dots, S^{(k)}\) 都关于 \(H\) 共轭，即

⑤ 令 \(k=k+1\)，转②。

\(\qquad\)第④步是各种共轭方向法的区别所在。平行搜索在二元情形下做一次平行搜索（两次一维搜索）就能得到所需的第二个方向；对 \(n\) 元问题，还要配合方向替换（鲍威尔法）。利用梯度递推构造方向，则得到下一篇的共轭梯度法。

程序框图

符号说明：图中 \(x\)、\(d^k\)、\(\alpha_k\) 分别对应正文的 \(X\)、\(S^{(k)}\)、\(\alpha^{(k)}\)；判据为 \(\|\nabla f(x^{k+1})\| < \varepsilon\)；框“提供新的共轭方向”即第④步。

实例计算

仍用前面几篇的标准函数，演示如何用平行搜索构造共轭方向，再沿共轭方向搜索到极小点。

题目

它的梯度和 Hessian矩阵为

理论最优解为 \(X^* = [4,2]^T\)，\(f(X^*) = -8\)。

解答

1. 坐标轴方向不共轭

先看坐标轴方向。取两个坐标轴方向 \(e_1 = [1,0]^T\)、\(e_2 = [0,1]^T\)，则

两个坐标轴方向不共轭，所以坐标轮换法只能一轮一轮地逼近，这正是上一篇看到的现象。

2. 用平行搜索构造 \(S^{(1)}\)

\(\qquad\)取初始搜索方向 \(S^{(0)} = [1,0]^T\)。题目给出的 \(X^{(0)} = [1,1]^T\) 作为第一个初始点 \(X_1^{(0)}\)，另取 \(X_2^{(0)} = [0,0]^T\) 作为第二个初始点。两点连线方向为 \([1,1]^T\)，与 \(S^{(0)}\) 不平行，满足要求。

先从 \(X_1^{(0)} = [1,1]^T\) 沿 \(S^{(0)}\) 搜索。此时 \(X = [1+\alpha, 1]^T\)，

令 \(\varphi'(\alpha) = 2\alpha - 4 = 0\)，得 \(\alpha^{(0)} = 2\)，所以

再从 \(X_2^{(0)} = [0,0]^T\) 沿同一方向搜索。此时 \(X = [\alpha,0]^T\)，

同样得 \(\alpha^{(0)} = 2\)，所以

连接两个极小点，得到

验证共轭性：

确实共轭。

3. 沿共轭方向搜索

从 \(X_1^{(1)} = [3,1]^T\) 出发，沿 \(S^{(1)} = [1,1]^T\) 搜索。此时 \(X = [3+\alpha, 1+\alpha]^T\)，

令 \(\varphi'(\alpha) = 2\alpha - 2 = 0\)，得 \(\alpha^{(1)} = 1\)，所以

此时

已到达精确极小点。

把三次一维搜索列成表：

\(\qquad\)前两次搜索是为了构造 \(S^{(1)}\)，第三次才沿共轭方向走向极小点。如果方向已经给定，从 \(X_1^{(0)}\) 出发先沿 \(S^{(0)}\) 到 \([3,1]^T\)，再沿 \(S^{(1)}\) 到 \([4,2]^T\)，两次搜索就够了，这正是性质 2 的结论。

与上一篇的坐标轮换法对比：

代码示例

\(\qquad\)程序沿用进退法和黄金分割法作一维搜索。核心是三步：从两个点沿 \(S^{(0)}\) 各搜索一次，把两个极小点相减得到 \(S^{(1)}\)，再从第一个极小点沿 \(S^{(1)}\) 搜索。这里只演示二元情形的三步搜索，没有写通用循环；通用流程见上面的程序框图。

// 1. 从两个点分别沿 s0 作一维搜索
vector p1 = line_search(func, x1, s0, eps);
vector p2 = line_search(func, x2, s0, eps);

// 2. 两个极小点的连线方向与 s0 共轭
vector s1(n);
double norm = 0.0;
for (int i = 0; i < n; ++i) {
    s1[i] = p1[i] - p2[i];
    norm += s1[i] * s1[i];
}
norm = sqrt(norm);
// 省略输出与退化判断，完整写法见下
for (int i = 0; i < n; ++i) s1[i] /= norm;

// 3. 从 p1 沿 s1 再作一次一维搜索
return line_search(func, p1, s1, eps);

完整程序如下，函数定义、一维搜索子程序和输出都在其中。

#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

// 进退法求初始区间 (复用)
pair bracket_minimum(function func, double a0, double h) {
    const int MAX_ITER = 1e4;
    if (h <= 0) throw invalid_argument("Step size h must be positive.");
    if (func(a0) <= func(a0 + h)) {
        double x0 = a0 + h, x1 = a0;
        h *= 2;
        double x2 = x1 - h;
        int iter = 0;
        while (func(x2) < func(x1)) {
            if (iter++ > MAX_ITER) throw runtime_error("Max iterations exceeded");
            x0 = x1; x1 = x2; h *= 2; x2 = x1 - h;
        }
        return make_pair(x2, x0);
    } else {
        double x0 = a0;
        double x1 = a0 + h;
        h *= 2;
        double x2 = x1 + h;
        int iter = 0;
        while (func(x2) < func(x1)) {
            if (iter++ > MAX_ITER) throw runtime_error("Max iterations exceeded");
            x0 = x1; x1 = x2; h *= 2; x2 = x1 + h;
        }
        return make_pair(x0, x2);
    }
}

// 黄金分割法 (复用)
double golden_section(function func, double l, double r, double eps) {
    double a = l, b = r, aa, bb;
    while (b - a > eps) {
        aa = b - 0.618 * (b - a);
        bb = a + 0.618 * (b - a);
        if (func(aa) < func(bb)) b = bb;
        else a = aa;
    }
    return (a + b) / 2;
}

// 从点 x 出发，沿方向 s 作一维搜索
vector line_search(
    function&)> func,
    const vector& x,
    const vector& s,
    double eps
) {
    auto phi = [&](double alpha) {
        vector y(x.size());
        for (size_t i = 0; i < x.size(); ++i) y[i] = x[i] + alpha * s[i];
        return func(y);
    };

    pair bracket;
    try { bracket = bracket_minimum(phi, 0.0, 0.1); }
    catch (...) { bracket = make_pair(0.0, 10.0); }

    double alpha_star = golden_section(phi, bracket.first, bracket.second, eps);

    vector y(x.size());
    for (size_t i = 0; i < x.size(); ++i) y[i] = x[i] + alpha_star * s[i];
    return y;
}

// 共轭方向法（二元函数）：先平行搜索构造共轭方向，再沿共轭方向搜索
vector conjugate_direction(
    function&)> func,
    const vector& x1,
    const vector& x2,
    const vector& s0,
    double eps
) {
    int n = x1.size();

    // 1. 从两个点分别沿 s0 作一维搜索
    vector p1 = line_search(func, x1, s0, eps);
    vector p2 = line_search(func, x2, s0, eps);

    cout << "沿 S0 搜索得到两个一维极小点:" << endl;
    cout << "  X1 = [";
    for (int i = 0; i < n; ++i) cout << p1[i] << (i == n - 1 ? "" : ", ");
    cout << "]^T" << endl;
    cout << "  X2 = [";
    for (int i = 0; i < n; ++i) cout << p2[i] << (i == n - 1 ? "" : ", ");
    cout << "]^T" << endl;

    // 2. 两个极小点的连线方向与 s0 共轭
    vector s1(n);
    double norm = 0.0;
    for (int i = 0; i < n; ++i) {
        s1[i] = p1[i] - p2[i];
        norm += s1[i] * s1[i];
    }
    norm = sqrt(norm);
    if (norm < 1e-12)
        throw runtime_error("平行搜索退化：两个极小点重合");
    for (int i = 0; i < n; ++i) s1[i] /= norm;

    cout << "构造的共轭方向 S1 = [";
    for (int i = 0; i < n; ++i) cout << s1[i] << (i == n - 1 ? "" : ", ");
    cout << "]^T" << endl;

    // 3. 从 p1 沿 s1 再作一次一维搜索
    return line_search(func, p1, s1, eps);
}

int main() {
    cout << fixed << setprecision(6);
    cout << "共轭方向法求解二元二次函数极小值" << endl;
    cout << "目标函数: f(X) = x1^2 + 2*x2^2 - 4*x1 - 2*x1*x2" << endl;
    cout << "理论最优解: X* = [4.0, 2.0]^T, f(X*) = -8.0" << endl << endl;

    auto f = [](const vector& x) {
        return x[0] * x[0] + 2 * x[1] * x[1] - 4 * x[0] - 2 * x[0] * x[1];
    };

    vector x1 = {1.0, 1.0};
    vector x2 = {0.0, 0.0};
    vector s0 = {1.0, 0.0};
    double eps = 0.01;

    vector result = conjugate_direction(f, x1, x2, s0, eps);

    cout << "\n最终结果:" << endl;
    cout << "最优解 X* = [";
    for (size_t i = 0; i < result.size(); ++i) cout << result[i] << (i == result.size() - 1 ? "" : ", ");
    cout << "]^T" << endl;
    cout << "目标函数值 f(X*) = " << f(result) << endl;

    return 0;
}

\(\qquad\)程序把构造出的方向单位化，所以输出的是 \([0.707107, 0.707107]^T\)，与手算的 \([1,1]^T\) 同向，不影响共轭性。实测沿 \(S^{(0)}\) 得到的两个极小点为 \((3.002196, 1.000000)\) 和 \((2.002196, 0.000000)\)，与手算的 \((3,1)\)、\((2,0)\) 略有差异；最终收敛到 \((4.003483, 2.001287)\)，\(f = -7.999994\)，与理论值 \((4,2)\)、\(-8\) 相差极小，误差来自一维搜索的精度。

方法分析

1. 二次函数 \(n\) 步收敛：只要方向关于 \(H\) 共轭，\(n\) 元正定二次函数最多 \(n\) 次一维搜索就能到达极小点。与坐标轮换法、最速下降法相比，这是本质上的改进。

2. 平行搜索不需要梯度：构造过程只比较函数值，适合导数难以计算的函数。但每构造一个新方向都要作两次一维搜索，构造本身有代价；两点连线与搜索方向平行时，还会退化。

3. \(n\) 步收敛只对二次函数严格成立：对非二次函数，共轭性只在局部近似成立，实际计算时通常需要周期性地重置方向，或者结合方向替换，才能保持较好的收敛性。

4. 两种构造思路通向两种方法：平行搜索配合方向替换，就是鲍威尔法；利用梯度递推构造方向，就是共轭梯度法。具体步骤把“构造新方向”留作第④步，用哪种方法填这一步，就得到哪种共轭方向法，共轭方向法是它们的共同基础。

总结

\(\qquad\)共轭方向法把“选方向”这件事从坐标轴和负梯度中解放出来：只要方向关于 Hessian矩阵共轭，二次函数就能在 \(n\) 步内收敛。平行搜索给出了一种只用函数值就能构造共轭方向的办法，思路巧妙，但构造一个方向要两次搜索，维数高时并不经济。

\(\qquad\)下一篇介绍共轭梯度法。它不再用两次平行搜索，而是用相邻两点的梯度直接递推出共轭方向，既保留了 \(n\) 步收敛的性质，又避免了 Hessian矩阵的计算。

本学习笔记参考资料：

[1] 白清顺, 孙靖民, 梁迎春. 机械优化设计 第7版[M]. 北京: 机械工业出版社, 2024. ISBN: 978-7-111-75103-8 在线链接

[2] 武汉理工大学《最优化技术B》课程课件，授课教师：颜彬老师