A problem of optimization

Question

Determine the maximum of $f(x_1,x_2,x_3,\dots,x_n)=\displaystyle\prod_{i \ne j}|x_i-x_{j}|$ for $0\le x_1<x_2<x_3< \dots<x_n<1 $.

It seems that you can always translate $x_i$'s such that $x_n \to 1$. At the same time one always maximizes the value of $f$ when stretching on the right $x_i$'s, ie when $x_1=0$ So we just need to consider $n-2$ values. Using dumb calculations (derivatives...), we get that:

for $n=2$, $\max=1$

for $n=3$, $\max=\frac 1 4$

for $n=4$, $\max=\frac{\sqrt{5}}{125}$...

Is there a way to find it in general ?

Answer 1

Using Arithmetic Mean as an upper bound, using a simpler case

Using $x_i$'s with $$0\le x_1<x_2<x_3< \dots<x_n\leq1$$ let's look instead at the max value of a simpler product $$g(x_1,x_2,x_3,\dots,x_n) = \prod (x_{i+1} - x_i)$$ We can see that $g$ is the product of the lengths of the line segments formed between all the $x_i$'s: $$\prod (x_{i+1} - x_i) = (x_n - x_{n-1})(x_{n-1} - x_{n-2})\dots(x_2 - x_1)$$ Furthermore, because $x_i < x_{i+1}$, we know each term is positive.

To simplify things, let's call each of these terms $a_i$ where

$$a_i = x_{i+1} - x_i$$

We want to know the max value of $$a_1a_2\dots a_{n-1}$$

For positive numbers we know that the Geometric Mean (GM) is less than or equal to the Arithmetic Mean (AM).

Looking at the line we can see that, as long as we keep $x_1 = 0$, $x_n = 1$, and obey the general other constraints, the sum of all the segment lengths will remain maxed out at $1$, regardless of our placement of the interior $x_i$'s.

$$AM = \frac{\sum a_i}{n-1} = \frac {1}{n-1}$$

Moving around the $x_i$'s (aka increasing and decreasing the interior segment lengths) will change the value of the product of all the $a_i$'s, and consequently will increase or decrease the value of the GM.

GM will reach its maximum value when it's equal to the AM.

This occurs when

$$GM = \sqrt[n-1]{\prod a_i} = \frac {1}{n-1}$$ $$\prod a_i = \frac {1}{(n-1)^{n-1}}$$

$$g_{\max} = \frac {1}{(n-1)^{n-1}}$$

You can see that this happens when the $x_i$'s are evenly spaced and the intervals all have length $\frac {1}{n-1}$.

More complicated product

I don't know if this approach might be helpful with the nastier product $\prod_{i \ne j}|x_i-x_{j}|$, but it might be worth looking into. If the sum of the lengths of all the intervals in this product is similarly constant regardless of moving around interior $x_i$'s, you might be able to do the same trick.

I'm sorry if this isn't helpful!

Answer 2

For now, I'm not convinced that there is a "nice" algebraic solution to this problem, but one can transform it into a convex program which can be solved efficiently. The objective is equal to $$f(x) = \prod_{i>j} (x_i-x_j)^2,$$ subject to the constraint $0 < x_1 < \ldots < x_n < 1$. Now, let $y_i = x_{i+1} - x_i, i=1,\ldots,n-1$, then $x_{i}-x_{j} = \sum_{k=j}^i y_k$ for $j > i$, and the optimization problem can equivalently be reformulated as: $$ \begin{split} \max_y &\left\{f(y)=\prod_{i=1}^{n-1}\prod_{j=i+1}^{n-1}\sum_{k=i}^jy_k\right\} \\ &s.t.\\ &\mathbf{1}^\top y=1,\\ &y\succ 0. \end{split} $$

One can solve this by solving the equivalent convex program $$\begin{split} \max_y & \left\{ g(y) =\sum_{j>i}\log\left(\sum_{k=i}^j y_k\right)\right\}\\ &s.t.\\ &\mathbf{1}^\top y=1,\\ &y\succ 0, \end{split} $$ where the solution to the original problem is recovered from $\exp(2g(y^*))$, with $y^*$ the maximizer of the above program. Maybe we can get close to a solution by examining the Lagrangian $$ L(y,\lambda) = \sum_{j>i}\log\left(\sum_{k=i}^j y_k\right) + \lambda(1 - \mathbf{1}^\top y), $$ and finding $y^*$ s.t. $\nabla_y L(y,\lambda) = 0$ with $y\succ 0$.

Hope this is helpful, I will try to do something more later.