Python和Java代码实现：切线法求解一维最优化问题

切线法原理

在上一篇文章中，我们使用黄金分割法求解了一维最优化问题。
本文介绍另一种求解该问题的算法：切线法。
该方法的逻辑是：首先在$[a,b]$内随机选择一点${\alpha }_k$，沿着该点做一条切线，切线和$x$轴的交点被选择为下一个点${\alpha }_{k+1}$，如此反复直至$|{\alpha }_{k+1}-{\alpha }_k|$小于给定阈值，即得到最优解。

接下来，我们看一下该方法的数学原理。
针对点${\alpha }_k$，切线方程为
$$y=f^{\prime }({\alpha }_k)+f^{\prime \prime }({\alpha }_k)(\alpha -{\alpha }_k)$$
令$y=0$，得到对应的${\alpha }_{k+1}$为
$${\alpha }_{k+1}={\alpha }_k-\frac{f^{\prime }({\alpha }_k)}{f^{\prime \prime }({\alpha }_k)}$$

随着$k$的增大，$f^{\prime }({\alpha }_k)$如果能趋向于0，$|{\alpha }_{k+1}-{\alpha }_k|$就能小于任意给定阈值，最终得到最优解。
当然，如果待优化函数一阶或者二阶不可导，那么切线法就无法使用了。

代码实现

Python代码

以下的tangent_method函数为切线法的Python代码。
除待优化函数$f(t)$外，代码中还定义了对应的一阶导数$d\_f(t)$和二阶导数$d\_2\_f(t)$。

# 待优化函数
def f(t):
    return t ** 2 - t * 5 + 8


# 待优化函数一阶导数
def d_f(t):
    return 2 * t - 5


# 待优化函数二阶导数
def d_2_f(t):
    return 2


# 切线法
def tangent_method(x, eps):

    cnt = 0
    while abs(-d_f(x) / d_2_f(x)) > eps:
        # 更新x，并增加迭代次数
        x += -d_f(x) / d_2_f(x)
        cnt += 1

    return x, f(x), cnt


if __name__ == '__main__':
    # 参数设置
    left_point = 1
    right_point = 7
    min_interval_value = 0.1

    # 选取初始点
    x0 = 6
    # 调用切线法求解最小值
    best_x, best_y, iter_cnt = tangent_method(x0, min_interval_value)
    # 输出最优解
    print('best_x: {}, best_y: {}, iter_cnt: {}.'.format(best_x, best_y, iter_cnt))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

Java代码

以下的tangentMethod函数为切线法的Java代码。

public class TangentMethod {

    public static void main(String[] args) {
        // 参数设置
        int leftPoint = 1;
        int rightPoint = 7;
        double minIntervalValue = 0.1;

        double x0 = 6.0;
        Solution best_solution = tangentMethod(x0, minIntervalValue);
        System.out.println("best_x: " + best_solution.best_x);
        System.out.println("best_y: " + best_solution.best_y);
        System.out.println("cnt: " + best_solution.cnt);
    }

    // 切线法
    private static Solution tangentMethod(double x, double eps) {
        // 统计迭代次数
        int cnt = 0;

        while (Math.abs(df(x) / d2f(x)) > eps) {
            // 更新x，并增加迭代次数
            x -= df(x) / d2f(x);
            cnt ++;
        }

        // 构造最优解对象
        Solution best_solution = new Solution();
        best_solution.best_x = x;
        best_solution.best_y = f(x);
        best_solution.cnt = cnt;

        return best_solution;
    }

    // 待优化函数
    private static double f(double t) {
        return t * t - t * 5 + 8;
    }

    // 待优化函数一阶导数
    private static double df(double t) {
        return t * 2 - 5;
    }

    // 待优化函数二阶导数
    private static double d2f(double t) {
        return 2;
    }

    // 解对象
    private static class Solution {
        double best_x;
        double best_y;
        int cnt;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

求解实例

无论运行Python程序还是Java程序，可以得到最优解如下：

best_x: 2.5, best_y: 1.75, iter_cnt: 1.
1

从结果上可以看出，切线法只需要迭代一次即可得到最优解；
而使用黄金分割法需要迭代的次数为9。
这主要是因为切线法使用了待优化函数更多的信息，包括一阶和二阶导数，所以计算效率更高，这在文章中也有提到过该理论。

此外，相比黄金分割法，切线法并不依赖左右端点的值，但是会对初值更加敏感（虽然文中的实例对初值不敏感），这也是值得注意的。