优化单变量函数

• 下载源代码 - 3.21 KB

引言

本文介绍了一种优化单变量函数的算法，该算法不需要导数函数。需要导数的算法通常速度快但不稳定。不需要导数的算法通常稳定但速度慢。但是，此处实现的算法既稳定又有效。它最初由 Richard Brent 在他的书“Algorithms for Minimization Without Derivatives”中发表。

给定一个函数 f(x) 和一个区间 [a, b]，该方法找到 f(x) 在 [a, b] 上的最小值。该方法也可用于最大化函数。要找到函数的最大值，请传入原始函数的负数。也就是说，f(x) 的最大值出现在 -f(x) 的最小值处。

Brent 的方法比牛顿更熟悉的方法更稳健。当牛顿的方法有效时，它非常快。但是当它不起作用时，它可能会严重出错，每次迭代都会产生更糟糕的答案。牛顿的方法就像童谣中的女孩

当她表现好的时候，她非常好。
但是当她表现不好的时候，她非常糟糕。

Brent 的方法也比牛顿的方法更容易使用，因为它不需要用户提供导数函数。该方法牺牲了一些效率来换取稳健性，但它比其他稳健的方法（例如黄金分割法）更有效。

Using the Code

此处给出的代码是一个单独的 C++ 函数和一个用于演示如何使用它的演示项目。要在您自己的项目中使用该函数，只需 #include 头文件 Brent.h。

最小化函数的主要输入是一个模板参数，一个实现要最小化的目标函数的函数对象。目标函数必须实现一个具有签名 double operator()(double x) 的 public 方法。例如，这是一个用于计算函数 f(x) = -x exp(-x) 的函数对象的类。

class foo
{
public:
    double operator()(double x) {return -x*exp(-x);}
};

我们的代码需要函数对象而不是简单函数的主要原因是，应用程序中需要优化的函数通常依赖于除了函数参数之外的参数。函数对象可能具有十几个参数，这些参数在找到结果单变量函数的最小值之前是固定的。

其他参数是要最小化函数的区间的端点、停止容差以及用于返回最小值位置的输出参数。最小化函数的返回值是目标函数在其最小值处的值。

我们的最小化函数的签名如下。

template <class TFunction>
double Minimize
(
    TFunction& f,    // [in] objective function to minimize
    double leftEnd,  // [in] smaller value of bracketing interval
    double rightEnd, // [in] larger value of bracketing interval
    double epsilon,  // [in] stopping tolerance
    double& minLoc   // [out] location of minimum, where the minimum occurs
)

假设我们要找到由上面类 foo 表示的函数 -x exp(x) 的最小值。下图是此函数的图。

我们两次找到此函数的最小值。首先，我们找到区间 [-1, 2] 上的最小值，以说明在区间的中间找到最小值。然后，我们找到区间 [2, 3] 上的最小值，以说明最小值出现在区间端点之一的情况。

foo f;
double minloc; // location of the minimum
double minval; // value at the minimum

std::cout << std::setprecision(7); // display seven decimal places in output

// First minimize over [-1, 2]
minval = Minimize<foo>(f, -1, 2, 1e-6, minloc);
std::cout << "Computed minimum location: " << minloc << "\n"
          << "Exact value:               " << 1.0    << "\n"
          << "Computed minimum value:    " << minval << "\n"
          << "Exact minimum value:       " << f(1.0) << "\n\n";
          
// Now minimize over [2, 3]
minval = Minimize<foo>(f, 2, 3, 1e-6, minloc);
std::cout << "Computed minimum location: " << minloc << "\n"
          << "Exact value:               " << 2.0    << "\n"
          << "Computed minimum value:    " << minval << "\n"
          << "Exact minimum value:       " << f(2.0) << "\n\n";

在第一种情况下，在 [-1, 2] 上进行最小化，精确的最小值出现在 1 处。这是函数的全局最小值。在第二种情况下，在 [2, 3] 上进行最小化，该函数在此区间上递增，因此最小值出现在左端点。输出表明结果在指定的 10^-6 容差范围内是正确的。

Computed minimum location: 1
Exact value:               1
Computed minimum value:    -0.3678794
Exact minimum value:       -0.3678794

Computed minimum location: 2.000001
Exact value:               2
Computed minimum value:    -0.2706704
Exact minimum value:       -0.2706706

评论

Brent 的方法是过去被忽视的瑰宝。它是在几十年前（1972 年）开发的，现在没有太多人知道它。但是，该方法非常适合许多应用程序，因为它既稳健又有效。人们经常在没有意识到的情况下使用该方法，因为它被其他软件包（例如 Mathematica）在内部使用。