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.

12more comments