这是一个创建于 1666 天前的主题，其中的信息可能已经有所发展或是发生改变。
遇到了一个问题，证明中需要一个论据：判断一个离散多元函数的最大和最小值在什么时候出现？想了好久，因为数学不好，所以上来请教下(┬＿┬)。
我把问题简化如下： 函数 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 友
 |
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 |
Select Language