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

求解离散多元函数的最大和最小值

  •  1
     
  •   wssy ·
    pooolman · 2020-05-03 12:00:01 +08:00 · 2692 次点击
    这是一个创建于 1425 天前的主题,其中的信息可能已经有所发展或是发生改变。

    遇到了一个问题,证明中需要一个论据:判断一个离散多元函数的最大和最小值在什么时候出现?想了好久,因为数学不好,所以上来请教下(┬_┬)。

    我把问题简化如下: 函数 f(x1, x2, ..., xm)=x1*(x1-1) + x2*(x2-1) + ... + xm*(xm-1),其中 x1,x2, ...xm 均属于[1, n),在 x1+x2+...+xm=n 的约束条件下,什么时候函数 f 分别取得最大值和最小值?

    在连续函数中可以用拉格朗日乘数法求极值,但是在离散函数中要怎么办?

    第 1 条附言  ·  2020-05-03 14:28:40 +08:00
    实际上我只需要一个紧确的下界即可,不过我对最大值也挺感兴趣╮(╯▽╰)╭。谢谢 v 友
    19 条回复    2020-05-05 12:16:29 +08:00
    MinQ
        1
    MinQ  
       2020-05-03 12:22:23 +08:00 via Android
    这里的 xm-1 是 xm 的上一个数字还是 xm 减 1 ?
    wssy
        2
    wssy  
    OP
       2020-05-03 12:24:33 +08:00
    @MinQ xm 减一。
    可能是没表述清楚,这里表示从 1 到 m 共有 m 个不同的 x 而已
    MinQ
        3
    MinQ  
       2020-05-03 12:30:34 +08:00 via Android
    那你这展开后应该是 x1^2+x2^2+.....+xm^2-(x1+x2+.....+xm)吧?就变成了 x1^2+x2^2+....xm^2-n,然后前面的平方数之和应该能算出来个上下界?我忙猜大于等于(n/m)^2*m,小于 n^2 ?
    seasona
        4
    seasona  
       2020-05-03 12:36:17 +08:00
    连续有拉格朗日乘数法,离散情况感觉应该不是很难,不过可能得去读论文了,可以看看这篇: https://link.springer.com/chapter/10.1007/978-3-540-48085-3_3
    wssy
        5
    wssy  
    OP
       2020-05-03 12:37:21 +08:00
    @MinQ 不是评估上下渐进边界,我想求出最大值点和最小值点来着
    MinQ
        6
    MinQ  
       2020-05-03 12:40:51 +08:00
    @wssy 通过评估上下边界大致上就能找出来最大值最小值点吧?比如最小值应该是 x1 到 xm 都为 n/m 的情况吧?最大值应该是任意一个数为 n-m+1,剩下的都是 1 吧?
    wssy
        7
    wssy  
    OP
       2020-05-03 12:45:13 +08:00
    @seasona 有点难。。。我去看看。
    我猜测是这样:当 x1, x2, ..., xm 尽可能均匀时( n/m,保留整数或者向上取整),达到最小;当 x1, x2, ..., xm 尽可能集中时(某一个 x 达到 n-m+1,其余 x 均为 1 )达到最大(⊙_⊙)?
    wssy
        8
    wssy  
    OP
       2020-05-03 12:46:08 +08:00
    @MinQ 是这样猜测的 o(∩_∩)o 哈哈
    MinQ
        9
    MinQ  
       2020-05-03 13:00:10 +08:00   ❤️ 1
    @wssy 最小值的证明用的是柯西不等式,可以证明小于等于(n/m)^2*m,又当 x1=x2=......=xm=n/m 时,x1^2+x2^2+.....+xm^2=(n/m)^2*m,证毕
    MinQ
        10
    MinQ  
       2020-05-03 13:00:39 +08:00
    @MinQ 可以证明大于等于(n/m)^2*m……
    crella
        11
    crella  
       2020-05-03 13:21:07 +08:00 via Android
    y=x(x-1)是凹函数。对于任意 a<i<j<b,恒有 f(a)+f(b)>f(i)+f(j),则当 m 为偶数时,{x}有 m/2 个 1 和(2n/m)时,f(x)取得最大值;当{x}等于 m 个(n/m)时,f(x)取得最小值。
    m 为奇数的情况类似。
    crella
        12
    crella  
       2020-05-03 13:22:12 +08:00 via Android
    修改:

    y=x(x-1)是凹函数。对于任意 a<i<j<b,恒有 f(a)+f(b)>f(i)+f(j),则当 m 为偶数时,{x}有 m/2 个 1 和(2n/m-1)时,f(x)取得最大值;当{x}等于 m 个(n/m)时,f(x)取得最小值。
    m 为奇数的情况类似。

    数学不及格,乱猜的
    crella
        13
    crella  
       2020-05-03 13:40:01 +08:00 via Android
    写错了,不好意思
    wssy
        14
    wssy  
    OP
       2020-05-03 14:12:14 +08:00
    @MinQ 非常感谢提点!这足够我完成证明了└(^o^)┘
    wssy
        15
    wssy  
    OP
       2020-05-03 14:51:00 +08:00
    @crella 没太理解,能把思路展开下吗?
    crella
        16
    crella  
       2020-05-03 15:10:43 +08:00 via Android
    @wssy 纠正一下:对于凹函数,任意 a<i<j<b 满足 a+b=i+j,恒有 f(a)+f(b)>f(i)+f(j)。
    因为 i-a=b-j,所以 f(b)-f(j)=λ(b-j)=λ(i-a)>μ(i-a)=f(i)-f(a),用中值定理,其中μ<i<j<λ,

    所以对于 f(x)=x(x-1),当每两个 x[i]的差异越大时,∑f(x[i])取得最大值。

    仅属猜想。
    Vinty
        17
    Vinty  
       2020-05-03 16:16:37 +08:00
    最大值是当 x 取[n-m+1, 1,...,1]的时候
    因为(a+1)^2+(b+1)^2+(c+1)^2<=(a+b+1)^2+(c+1)^2+1 <= (a+b+c+1)^2+2
    crella
        18
    crella  
       2020-05-03 16:25:16 +08:00
    感觉凹凸函数的区分与柯西不等式有一些关系。顺便问一下楼主,怎样生成在给定区间内的和为定值的定长离散数列?

    我是这样想的:伪代码:
    i=数组长度-1
    while (i>=1)
    a=(数组[i]-数组[i-1])*0.05
    数组[i] -= a; 数组[i-1] += a
    i -= 1
    end

    这样会把数组(1,1,...,m)变成趋近于 m 个(n/m)的数组,而且数组内总是递增的。但是我不知道这样生成离散数列是否满足暴力求解的前提。
    wssy
        19
    wssy  
    OP
       2020-05-05 12:16:29 +08:00
    @crella
    #16
    没看懂诶,
    1.“凹函数”+“任意 a<i<j<b 满足 a+b=i+j” ==> “恒有 f(a)+f(b)>f(i)+f(j)”
    这是怎么推导的?凹函数的定义似乎和这个不搭边。。。
    2.“所以对于 f(x)=x(x-1),当每两个 x[i]的差异越大时,∑f(x[i])取得最大值。”
    似乎你的猜测是:给定一个集合 S={x1,x2,...,xm}为{n-m+1,1,1...,1},其余所有可能的集合{x1',x2',...,xm'}中的元素只能在 S 中最大和最小元素范围之间,所以基于 1,拓展成 f(x1)+f(x2)+...+f(xm)>f(x1')+f(x2')+...f(xm')?
    3.“因为 i-a=b-j,所以 f(b)-f(j)=λ(b-j)=λ(i-a)>μ(i-a)=f(i)-f(a),用中值定理,其中μ<i<j<λ”
    如果上面推测正确的话,似乎这一点在证明中没有作用?

    #18
    如果你是说想通过遍历所有可能的离散数列来找出最大值的话,给出的伪码是不行的。我找到一个答案,可以生成所有符合条件的离散数列,看上去是正确的,但我没有证明: https://stackoverflow.com/questions/13988197/how-to-iterate-through-array-combinations-with-constant-sum-efficiently
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   2091 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 29ms · UTC 16:14 · PVG 00:14 · LAX 09:14 · JFK 12:14
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.