这是一个创建于 976 天前的主题，其中的信息可能已经有所发展或是发生改变。
题目： 已知 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 ，我会及时加你。
 |
1
xiangyuecn 2022-04-25 17:21:07 +08:00
只要 y 值是连续的，应该可以简单的用曲线去拟合吧，x 值 按 2 个点、8 个点、16 个点... 一步步画曲线，找到 y 最大值时的 x 范围，只要区间足够小了，开始暴力求解，目测 1 秒得到结果
y 值不连续？那就不懂了，下一位 |
 |
2
ras014 2022-04-25 17:27:42 +08:00
模拟退火
|
 |
3
shyrock 2022-04-25 18:01:02 +08:00
这样是否可行：
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)不存在。 |
 |
4
stein42 2022-04-25 18:09:44 +08:00
BFGS 算法是求多元函数极值的。
牛顿法需要二阶导数。 这个可以直接用黄金分割法，也就是 0.618 法，不断缩小区间，收敛速度是指数级的。 |
 |
5
zhailw 2022-04-25 18:41:55 +08:00 via Android
楼主三分法怎么实现的啊？我大概算了一下，230 步左右就可以求出来了啊？这样都满足不了要求么？
而且如果曲线没有其他性质的话，n 分法就是最优解了啊 |
 |
6
cheitu OP |
 |
7
JeffersonQin 2022-04-26 09:19:50 +08:00 via Android
提问：
1. x 是离散的还是连续的？ 2. 按照题意，应该是一个严格的单峰映射？ 方案： 1. 随机化方法：模拟退火 2. 三分 3. 牛顿法 |
|
8
cheitu OP @JeffersonQin 1 、连续 2 、单峰。 牛顿法需要用到二次导数，我试了用中心差分法求一次和二次导数，可能二次导数误差太大，迭代不出结果，所以现在想用拟牛顿 BFGS 算法。
|
 |
9
LonaBongo 2022-04-26 09:39:38 +08:00
@cheitu 在数值分析里，bfgs 一般是找函数在某一个邻域里的最值，在作用域内，极值是可以有多个的， 对任意取出的 x0 bfgs 只能收敛到邻域内的极值点，按照 lz 对 y=f(x)的第二个描述，直觉上是符合的
|
|
10
JeffersonQin 2022-04-26 10:09:42 +08:00 via Android
@cheitu 那最靠谱的其实还是三分
|
|
11
stein42 2022-04-27 08:29:25 +08:00
可以试试牛顿法，用一阶二阶差分代替微分，一定条件下收敛。
或者每次迭代从一点及附近两点作一条二次曲线（抛物线），直接移动的极值点。 BFGS 是用一系列点的梯度得到类海森矩阵的逆，可以尝试退化到一元函数的情况。 另外黄金分割法每计算一个点区间缩小 0.618 倍，理论上效率比三分、四分法高。 |
Select Language