How to solve such an optimization problem

Question

I encounter the following optimization problem, but I can't solve it.

Given $N$ variables satisfying $0 \leq x_1 \leq x_2 \leq x_3 \leq ... \leq x_N \leq 1$ and an integer $K$ no large than $N$, find the values of $\{x_i\}$ that maximize the following function.

$$\sum_{S \subset \{1,2,..., N\},\\ |S| = K} \prod_{i<j,\\ i,j \in S} (x_j - x_i)^2.$$

This problem is somehow related to Vandermonde matrix. Each additional term in the above target function is just the square of the determinate of Vandermonde matrix generated by the $K$ selected variables belonging set $S$.

---

Many thanks for all who gave valuable comments and potential answers to this question. Based on all these responses, I'd like to summarize the current progress as follows.

The solution to this question may involve the following five steps.

Step 1. Prove that for general $N$ and $K$, the optimal values of all the $N$ $\{x_i\}$ can only take $K$ different numbers, i.e., they are divided into $K$ groups, and all the $\{x_i\}$ in the same group take the same value.

Status: Not proved

Step 2. Prove that the $K$ optimal values of $\{x_i\}$ are independent of the value of $N$.

Status: Can be proved if Step 1 is proved.

Step 3: Prove that the numbers $\{x_i\}$ in each group in Step 1 are almost the same, i.e., they differ by at most 1.

Status: Can be proved if Steps 1&2 are proved.

Step 4: Prove that the original question in the special case of $N = K$ has a unique solution.

Status: Can be proved.

Step 5: Find the closed-form expressions of these $K$ values.

Status: It has been known that these $K$ values are just the Fekete points. However, I still have not find the correct reference showing these closed-form expressions and the corresponding proof.

In summary, the remaining difficulties are Step 1 and Step 5. Step 1 requires more intelligent input, and Step 5 relies on finding the correct reference.

Thanks a lot for all your attention~! I will be greatly appreciated if someone can help me with Steps 1 and 5.

Answer 1

Here my answer for the case where $K$ divides $N$ :

I consider the intervall $[-1,1]$ instead of $[0,1]$ .

Let $A$ be the $N\times K$ matrix with elements $x_i^{j-1}, 1 \leq i \leq N, 1 \leq j \leq K$

By the Cauchy-Binet theorem the function we want to maximize equals $det(A^T A)$ .

Next I use the result of Fejer 1932 (see http://www.math.technion.ac.il/hat/fpapers/fejerpisa.pdf) :

Let $y_i , 1 \leq i \leq K$ be the zeros of the polynomial $(1-x^2)P'_{K-1}(x)$ where $P_k$ is the $k$-th Legendre polynomial, and let $l_i(x)$ be the fundamental Lagrange interpolating polynomials associated to these points.

Then it holds :

$$ \sum_{i=1}^K l_i(x)^2 \leq 1 $$ for $-1 \leq x \leq 1$ .

Now I follow the paper of Bos, Taylor and Wingate cited in a comment :

Since $$x_i^{j-1} = \sum_{k=1}^K y_k^{j-1} l_k(x_i)$$, we can write $A = B C$, where $B$ has the matrix elements $l_k(x_i), 1 \leq i \leq N, 1 \leq k \leq K$ and $C$ has the matrix elements $y_k^{j-1} , 1 \leq k \leq K, 1 \leq j \leq K$ .

Therefore $$det(A^T A) = det(B^T B) \prod_{1 \leq i < j \leq K} (y_i - y_j)^2$$ .

Now I use Hadamard's inequality, the fact that the geometric mean is less or equal the arithmetic mean and Fejer's inequality and obtain :

$$det(B^T B) \leq \prod_{1 \leq k \leq K} \sum_{i=1}^N l_k(x_i)^2 \leq (\dfrac{1}{K} \sum_{k=1}^K \sum_{i=1}^N l_k(x_i)^2)^K \leq (\dfrac{N}{K})^K$$

Here equality holds iff the square of the euclidean norm of each column vector of $B$ equals $N/K$ and iff they are pairwise orthogonal and this is the case iff $\lbrace x_i : 1 \leq i \leq N\rbrace = \lbrace y_j : 1 \leq j \leq K\rbrace$ and $\vert \lbrace i : x_i = y_j\rbrace\vert = N/K$ for each $j$ (note that equality in Fejer's inequality holds iff $x = y_j$ for a $j$).

Answer 2

First, I would suggest that the strict inequalities in $0\leq x_1<x_2<\dots<x_N\leq1$ are changed into weak inequalities:$0\leq x_1\leq x_2\leq\dots\leq x_N\leq1$, such that we optimize over a closed set. (Then it is also clear that we can just optimize over the whole cube $[0,1]^N$: the vertices will we ordered in some way.)

Lets call the function we are trying to be optimized $f$. $$f=\sum_{S\in\binom{N}{K}} \prod_{i<j i,j \in S} (x_j - x_i)^2.$$

Maybe it is useful to note that we can assume $x_1=0$ and $x_N=1$, since otherwise we can just stretch the points to fit the unit interval, making $f$ larger.

I will give an answer for $N$ and $K$ small.

For $K=2$, the problem becomes a quadratic programming problem with $$f=x^TQx$$ for $$Q=\pmatrix{N-1&-1&-1&\dots&-1\\-1&N-1&-1&\dots &-1\\\dots&&&&\\-1&-1&-1&\dots&N-1}$$ Optimizing over the cube $[0,1]^N$ gives as solution, as mentioned in the comments, $$x_i\begin{cases}0 \text{ if }i\leq \left\lfloor\frac{N}{2}\right\rfloor\\1 \text{ otherwise }\end{cases}$$ The maximum attained is $$f=\left\lfloor\frac{N}{2}\right\rfloor\left\lceil\frac{N}{2}\right\rceil$$

Here are some pictures for $N=2$ and $N=3$.

The next image was made with sage by invoking the following command, which gives you also an animated 3d model

sum(implicit_plot3d((x-y)^2+(x-z)^2+(z-y)^2==.02+i*.3,(0,1),(0,1),(0,1),color=rainbow(4*7)[k-1-i]) for i in range(7)).show()

For $N=3$ the image shows level sets of $f$; they are cylinders arount the diagonal $\{(c,\dots,c) : c\in \mathbb{R}\}$. From that pictures it becomes clear that the optimizer must be the vertices of the cube that have the largest distance to the diagonal.

Here is a partially completed table of optimal solutions (value of $f$) for small $N$ and $K$ obtained with the help of global optimization tools:

$$\begin{array}{lccccccc}K\backslash N&\bf2&\bf3&\bf4&\bf5&\bf6&\bf7&\bf8\\2&1&2&4&6&9&12&16\\3&-&\frac{1}{16}&\frac{1}{4}&\frac{1}{4}&\frac{1}{2}&\\4&-&-&\frac{1}{3125}&&&&\geq\frac{16}{3125}\end{array}$$

Let me list the optimal configuration of points. I omit $x_1=0$ and $x_N=1$. (Notice all values given are exact and not meant to be approximations)

$K=3$:

• $N=3$: $x_2=\frac{1}{2}$
• $N=4$: $x_2=x_3=\frac{1}{2}$
• $N=5$: $x_2=x_3=\frac{1}{2}$, $x_4=1$
• $N=6$: $x_2=0$, $x_3=x_4=\frac{1}{2}$, $x_5=1$

$K=4$:

• $N=4$: $x_2=\frac{1}{2}-\frac{\sqrt{5}}{10}$, $x_3=\frac{1}{2}+\frac{\sqrt{5}}{10}$
• $N=8$ If we assume that the vertices come in pairs, as mentioned in the comments the points will be the same as in the case $N=4$. (Notice that the putatively optimal results mentioned in the comments $x_3=x_4=.275$ and $x_5=x_6=.725$ are almost but not quite optimal; better values would be $x_3=x_4=.276$ and $x_5=x_6=.724$ or even better $$x_3=x_4=0.27639320225002103035908263312687237645593816403885 \\x_5=x_6=0.72360679774997896964091736687312762354406183596115 $$

In all of these cases the points where values of $x_i$ lie are independent of $N$. Hence with the fact that they are the Fekete points for $N=K$, one could conjecture that they will also be the the Fekete points for other $N$ and search an optimum only among those.

Answer 3

I would try geometric programming.

https://web.stanford.edu/~boyd/papers/pdf/gp_tutorial.pdf

Maximize $$\sum_{S \subset \{1,2,..., N\},\\ |S| = K} \prod_{i<j,\\ i,j \in S} (x_j - x_i)^2.$$

such that $N \in$ non-negative numbers, decision variables $x_{i}$ such that $0 \leq x_1 \leq x_2 \leq x_3 \leq ... \leq x_N \leq 1$, and integer $K \leq N$.

Since there are no other constraints, you can use traditional solutions to solve optimization problems for unconstrained geometric programming.

See $\S8.3.1$ titled, "Solution Techniques for Unconstrained Posynomial Geometric Programming Problems," from the book, H. A. Eiselt and Carl-Louis Sandblom, "Nonlinear Optimization: Methods and Applications," in International Series in Operations Research & Management Science, Springer Nature Switzerland AG, Cham, Switzerland, 2019.