最优化算法速通 - 线搜索

duanyll

2022-12-06

课程

最优化

在区间上求一元单值函数的极小值点.

区间压缩方法

黄金分割法

要求目标函数是单峰的.

确定合适的参数使得每次迭代只需计算一次函数的值. 每一步只需要确定一个新点并计算一次目标函数的值(第1 步除外)。

goldenSearch[fun_, var_, l0_, r0_, delta_] := 
  Module[{f, a, b, fa, fb, l, r, \[Rho], n}, (
    f[x_] = N[fun /. var -> x, precision];
    \[Rho] = 2 - GoldenRatio;
    l[1] = l0;
    r[1] = r0;
    a[n_] = l[n] + \[Rho] (r[n] - l[n]);
    b[n_] = l[n] + (1 - \[Rho]) (r[n] - l[n]);
    fa[n_] = f[a[n]];
    fb[n_] = f[b[n]];
    n = 1;
    While[r[n] - l[n] > delta,
     If[fa[n] > fb[n], (
       l[n + 1] = a[n];
       r[n + 1] = r[n]
       ), (
       l[n + 1] = l[n];
       r[n + 1] = b[n]
       )
      ];
     n++;
     ];
    Print[
     TableForm[
      Table[{a[i], b[i], fa[i], fb[i], 
        Interval[{l[i + 1], r[i + 1]}]}, {i, 1, n - 1}], 
      TableHeadings -> {Range[n - 1], {"a", "b", "f(a)", "f(b)", 
         "Next Interval"} }]];
    Return[{l[n], r[n]}];
    )];

总压缩比: 0.618, 经过步压缩之后，极小点所在区间长度将压缩到初始区间长度的

Fibonacci 数列法

要求目标函数是单峰的.

仍然要求每次压缩区间能利用之前的取值, 希望允许每次迭代的压缩比改变, 使得固定步数的总压缩比最小, 则应使用 Fibonacci 数列的形式设置每步的压缩比.

满足下式时能利用之前的取值:

即

总压缩比:

视作有约束优化问题求解, 得到

注: . 总压缩比:

注意最后一次迭代 , 为了保证能产生两个不同的新点以便后续处理, 可取 , 总压缩比变为

fibonacciSearch[fun_, var_, l0_, r0_, delta_] := 
  Module[{f, a, b, fa, fb, l, r, \[Rho], \[Epsilon], n, i}, (
    f[x_] = N[fun /. var -> x, precision];
    \[Epsilon] = delta/10;
    n = 0;
    While[(1 + 2 \[Epsilon])/Fibonacci[n + 2] > delta/(r0 - l0), n++];
    l[1] = l0;
    r[1] = r0;
    \[Rho][i_] = 
     If[i == n, 1/2 - \[Epsilon], 
      1 - Fibonacci[n + 2 - i]/Fibonacci[n + 3 - i]];
    a[i_] = l[i] + \[Rho][i] (r[i] - l[i]);
    b[i_] = l[i] + (1 - \[Rho][i]) (r[i] - l[i]);
    fa[i_] = f[a[i]];
    fb[i_] = f[b[i]];
    Do[
     If[fa[i] > fb[i], (
       l[i + 1] = a[i];
       r[i + 1] = r[i]
       ), (
       l[i + 1] = l[i];
       r[i + 1] = b[i]
       )
      ],
     {i, n}
     ];
    
    Print[
     TableForm[
      Table[{\[Rho][i], a[i], b[i], fa[i], fb[i], 
        Interval[{l[i + 1], r[i + 1]}]}, {i, 1, n}], 
      TableHeadings -> {Range[n], {"\[Rho]", "a", "b", "f(a)", "f(b)",
          "Next Interval"} }]];
    Return[{l[n + 1], r[n + 1]}];
    )];