题目: 已知 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 倍,理论上效率比三分、四分法高。 |