3000 人民币预算有偿求助解决一个求极大值问题

[cheitu]

题目： 已知 y 与 x 相关，没有明确的 y 与 x 的表达式。已知 x 的情况，带入即可求得对于 y 的值。现需要求得 y 关于 x 的极大值。 另外，已知相关性条件如下： 1 、x 的范围是 0 至 40000000000000000000000 ，在此函数作用域内，求 y 的极大值； 2 、x 越大，y 的趋势为先增加后减少，且 y 最大值必定会大于 0 ；

附： 1 、目前探索结论：因为 y 与 x 没有明确的表达式，故不能直接通过极值表达式求得极大值，思路为通过迭代法，求得极大值。现已实现通过三分法迭代求得 y 的极大值，可是三分法效率不高，需要迭代次数更少的算法。 2 、探索方向：通过拟牛顿迭代 bfgs 算法，可快速收敛求得极大值；目前只知思路，但不懂 bfgs 的算法原理，不知如何实现。

需求：用 python 或者 go 实现一个高效迭代方法，求极值。不可以使用计算库。我这边期望是 bfgs 算法，如果你认为有更优的算法可以再讨论。

x 与 y 的计算程序我会额外提供，有兴趣可以联系留下微信或者 tg ，我会及时加你。

[xiangyuecn]

只要 y 值是连续的，应该可以简单的用曲线去拟合吧，x 值 按 2 个点、8 个点、16 个点... 一步步画曲线，找到 y 最大值时的 x 范围，只要区间足够小了，开始暴力求解，目测 1 秒得到结果

y 值不连续？那就不懂了，下一位

[ras014]

模拟退火

[shyrock]

这样是否可行：
1.取考察区间正中间的三个点 n-1 ，n ，n+1 ，分别求 f(n-1),f(n)和 f(n+1);
2.如果 f(n-1)>f(n)>f(n+1)，在[0,n-1]区间重复第 1 步；
如果 f(n-1)<f(n)<f(n+1),在[n+1,max]区间重复第 1 步；
如果 f(n-1)<f(n)>f(n+1),则 f(n)是极大值；
由题意，f(n-1)>f(n)<f(n+1)不存在。

[stein42]

BFGS 算法是求多元函数极值的。
牛顿法需要二阶导数。
这个可以直接用黄金分割法，也就是 0.618 法，不断缩小区间，收敛速度是指数级的。

[zhailw]

楼主三分法怎么实现的啊？我大概算了一下，230 步左右就可以求出来了啊？这样都满足不了要求么？
而且如果曲线没有其他性质的话，n 分法就是最优解了啊

[cheitu]

@zhailw @stein42 目前用的优化后的四分法是只需要求 52 次 y 值就能取得有效精度下的结果，比黄金分割少 10 次。我理想情况下是计算 20 次以内得到结果。我试过牛顿迭代法求 y 为 0 的值，一阶导用中心差分近似替代，只需要迭代 5 次就能准确得到结果，因为 bfgs 只需要用一阶导，所以我感觉 bfgs 应该可以解决我的问题。

[JeffersonQin]

提问：
1. x 是离散的还是连续的？
2. 按照题意，应该是一个严格的单峰映射？
方案：
1. 随机化方法：模拟退火
2. 三分
3. 牛顿法

[cheitu]

@JeffersonQin 1 、连续 2 、单峰。 牛顿法需要用到二次导数，我试了用中心差分法求一次和二次导数，可能二次导数误差太大，迭代不出结果，所以现在想用拟牛顿 BFGS 算法。

[LonaBongo]

@cheitu 在数值分析里，bfgs 一般是找函数在某一个邻域里的最值，在作用域内，极值是可以有多个的， 对任意取出的 x0 bfgs 只能收敛到邻域内的极值点，按照 lz 对 y=f(x)的第二个描述，直觉上是符合的

[JeffersonQin]

@cheitu 那最靠谱的其实还是三分

[stein42]

可以试试牛顿法，用一阶二阶差分代替微分，一定条件下收敛。
或者每次迭代从一点及附近两点作一条二次曲线（抛物线），直接移动的极值点。
BFGS 是用一系列点的梯度得到类海森矩阵的逆，可以尝试退化到一元函数的情况。
另外黄金分割法每计算一个点区间缩小 0.618 倍，理论上效率比三分、四分法高。