机器算法验证 - 找到抛物线形函数的最小值的有效算法是什么？ - 吾爱随笔录

机器算法验证优化算法极值

2022-03-27 22:54:40

我有一个以区间 (0, N) 为界的连续函数 f(x)，其中 N 是一个大的正整数 (~10,000,000)。该函数的形状像一个向上的抛物线，但是，它略微倾斜（因此不完全是抛物线）。我能够计算 f(x) 的值，但是采样的计算成本非常高。

有哪些可能的算法可以使用最少的迭代次数有效且准确地逼近这个抛物线形函数的最小值？

2个回答

通过 , ,的抛物线在 $(a,f(a))$ $(b,f(b))$ $(c,f(c))$

G (a, b, c) := \frac{1}{2} (\frac{f (a) (b^{2} - c^{2}) + f (b) (c^{2} - a^{2}) + f (c) (a^{2} - b^{2})}{f (a) (b - c) + f (b) (c - a) + f (c) (a - b)})

$G(a,b,c):=\frac{1}{2}\left( \frac{f(a)(b^2-c^2)+f(b)(c^2-a^2)+f(c)(a^2-b^2)}{f(a)(b-c)+f(b)(c-a)+f(c)(a-b)}\right)$

因此，如果您从三个合理的猜测、和开始，您可以使用进行迭代，直到获得所需的收敛, 然后在最后取的极限。 $x_0$ $x_1$ $x_2$ $x_{n+1}=G(x_{n-2}, x_{n-1}, x_n)$ $f$

三元搜索是一种简单的算法，可以在不使用任何导数信息的情况下找到单峰函数的最小值（或最大值）。它从某个间隔开始，然后递归地丢弃三分之一的间隔，直到达到某个容差。

其它你可能感兴趣的问题