V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
cheitu
V2EX  ›  编程

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

  •  
  •   cheitu · 2022-04-25 17:15:13 +08:00 · 2599 次点击
    这是一个创建于 951 天前的主题,其中的信息可能已经有所发展或是发生改变。

    题目: 已知 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 ,我会及时加你。

    11 条回复    2022-04-27 08:29:25 +08:00
    xiangyuecn
        1
    xiangyuecn  
       2022-04-25 17:21:07 +08:00
    只要 y 值是连续的,应该可以简单的用曲线去拟合吧,x 值 按 2 个点、8 个点、16 个点... 一步步画曲线,找到 y 最大值时的 x 范围,只要区间足够小了,开始暴力求解,目测 1 秒得到结果

    y 值不连续?那就不懂了,下一位
    ras014
        2
    ras014  
       2022-04-25 17:27:42 +08:00
    模拟退火
    shyrock
        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)不存在。
    stein42
        4
    stein42  
       2022-04-25 18:09:44 +08:00
    BFGS 算法是求多元函数极值的。
    牛顿法需要二阶导数。
    这个可以直接用黄金分割法,也就是 0.618 法,不断缩小区间,收敛速度是指数级的。
    zhailw
        5
    zhailw  
       2022-04-25 18:41:55 +08:00 via Android
    楼主三分法怎么实现的啊?我大概算了一下,230 步左右就可以求出来了啊?这样都满足不了要求么?
    而且如果曲线没有其他性质的话,n 分法就是最优解了啊
    cheitu
        6
    cheitu  
    OP
       2022-04-25 19:10:48 +08:00
    @zhailw @stein42 目前用的优化后的四分法是只需要求 52 次 y 值就能取得有效精度下的结果,比黄金分割少 10 次。我理想情况下是计算 20 次以内得到结果。我试过牛顿迭代法求 y 为 0 的值,一阶导用中心差分近似替代,只需要迭代 5 次就能准确得到结果,因为 bfgs 只需要用一阶导,所以我感觉 bfgs 应该可以解决我的问题。
    JeffersonQin
        7
    JeffersonQin  
       2022-04-26 09:19:50 +08:00 via Android
    提问:
    1. x 是离散的还是连续的?
    2. 按照题意,应该是一个严格的单峰映射?
    方案:
    1. 随机化方法:模拟退火
    2. 三分
    3. 牛顿法
    cheitu
        8
    cheitu  
    OP
       2022-04-26 09:37:20 +08:00
    @JeffersonQin 1 、连续 2 、单峰。 牛顿法需要用到二次导数,我试了用中心差分法求一次和二次导数,可能二次导数误差太大,迭代不出结果,所以现在想用拟牛顿 BFGS 算法。
    LonaBongo
        9
    LonaBongo  
       2022-04-26 09:39:38 +08:00
    @cheitu 在数值分析里,bfgs 一般是找函数在某一个邻域里的最值,在作用域内,极值是可以有多个的, 对任意取出的 x0 bfgs 只能收敛到邻域内的极值点,按照 lz 对 y=f(x)的第二个描述,直觉上是符合的
    JeffersonQin
        10
    JeffersonQin  
       2022-04-26 10:09:42 +08:00 via Android
    @cheitu 那最靠谱的其实还是三分
    stein42
        11
    stein42  
       2022-04-27 08:29:25 +08:00
    可以试试牛顿法,用一阶二阶差分代替微分,一定条件下收敛。
    或者每次迭代从一点及附近两点作一条二次曲线(抛物线),直接移动的极值点。
    BFGS 是用一系列点的梯度得到类海森矩阵的逆,可以尝试退化到一元函数的情况。
    另外黄金分割法每计算一个点区间缩小 0.618 倍,理论上效率比三分、四分法高。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2803 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 11:41 · PVG 19:41 · LAX 03:41 · JFK 06:41
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.