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

• 資深大佬 : 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