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

[wssy]

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

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

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

[MinQ]

这里的 xm-1 是 xm 的上一个数字还是 xm 减 1 ？

[wssy]

@MinQ xm 减一。
可能是没表述清楚，这里表示从 1 到 m 共有 m 个不同的 x 而已

[MinQ]

那你这展开后应该是 x1^2+x2^2+.....+xm^2-(x1+x2+.....+xm)吧？就变成了 x1^2+x2^2+....xm^2-n，然后前面的平方数之和应该能算出来个上下界？我忙猜大于等于(n/m)^2*m，小于 n^2 ？

[seasona]

连续有拉格朗日乘数法，离散情况感觉应该不是很难，不过可能得去读论文了，可以看看这篇： https://link.springer.com/chapter/10.1007/978-3-540-48085-3_3

[wssy]

@MinQ 不是评估上下渐进边界，我想求出最大值点和最小值点来着

[MinQ]

@wssy 通过评估上下边界大致上就能找出来最大值最小值点吧？比如最小值应该是 x1 到 xm 都为 n/m 的情况吧？最大值应该是任意一个数为 n-m+1，剩下的都是 1 吧？

[wssy]

@seasona 有点难。。。我去看看。
我猜测是这样：当 x1, x2, ..., xm 尽可能均匀时（ n/m，保留整数或者向上取整），达到最小；当 x1, x2, ..., xm 尽可能集中时（某一个 x 达到 n-m+1，其余 x 均为 1 ）达到最大(⊙_⊙)?

[wssy]

@MinQ 是这样猜测的 o(∩_∩)o 哈哈

[MinQ]

@wssy 最小值的证明用的是柯西不等式，可以证明小于等于(n/m)^2*m，又当 x1=x2=......=xm=n/m 时，x1^2+x2^2+.....+xm^2=(n/m)^2*m，证毕

[MinQ]

@MinQ 可以证明大于等于(n/m)^2*m……

[crella]

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]

修改：

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]

写错了，不好意思

[wssy]

@MinQ 非常感谢提点！这足够我完成证明了└(^o^)┘

[wssy]

@crella 没太理解，能把思路展开下吗？

[crella]

@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]

最大值是当 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]

感觉凹凸函数的区分与柯西不等式有一些关系。顺便问一下楼主，怎样生成在给定区间内的和为定值的定长离散数列？

我是这样想的：伪代码：
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]

@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