遇到了一个问题,证明中需要一个论据:判断一个离散多元函数的最大和最小值在什么时候出现?想了好久,因为数学不好,所以上来请教下(┬_┬)。
我把问题简化如下: 函数 f(x1, x2, ..., xm)=x1*(x1-1) + x2*(x2-1) + ... + xm*(xm-1),其中 x1,x2, ...xm 均属于[1, n),在 x1+x2+...+xm=n 的约束条件下,什么时候函数 f 分别取得最大值和最小值?
在连续函数中可以用拉格朗日乘数法求极值,但是在离散函数中要怎么办?
1
MinQ 2020-05-03 12:22:23 +08:00 via Android
这里的 xm-1 是 xm 的上一个数字还是 xm 减 1 ?
|
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 ?
|
4
seasona 2020-05-03 12:36:17 +08:00
连续有拉格朗日乘数法,离散情况感觉应该不是很难,不过可能得去读论文了,可以看看这篇: https://link.springer.com/chapter/10.1007/978-3-540-48085-3_3
|
6
MinQ 2020-05-03 12:40:51 +08:00
@wssy 通过评估上下边界大致上就能找出来最大值最小值点吧?比如最小值应该是 x1 到 xm 都为 n/m 的情况吧?最大值应该是任意一个数为 n-m+1,剩下的都是 1 吧?
|
7
wssy OP @seasona 有点难。。。我去看看。
我猜测是这样:当 x1, x2, ..., xm 尽可能均匀时( n/m,保留整数或者向上取整),达到最小;当 x1, x2, ..., xm 尽可能集中时(某一个 x 达到 n-m+1,其余 x 均为 1 )达到最大(⊙_⊙)? |
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,证毕
|
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 为奇数的情况类似。 |
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 为奇数的情况类似。 数学不及格,乱猜的 |
13
crella 2020-05-03 13:40:01 +08:00 via Android
写错了,不好意思
|
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])取得最大值。 仅属猜想。 |
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 |
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)的数组,而且数组内总是递增的。但是我不知道这样生成离散数列是否满足暴力求解的前提。 |
19
wssy OP @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 |