8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Looking at K=2, I see the maximizing strategy to be distributing the first $\lfloor N/2 \rfloor$ $x_i$'s at $0$, and remaining at $1$. So a wild conjecture is that one should equally distribute the $x_i$'s at $j/(K-1)$, for $j=0, \ldots, K-1$, since when $N=k$ the latter gives the maximal vandermonde product. $\endgroup$ – John Jiang Aug 17 '14 at 7:48
  • $\begingroup$ Thanks John for your help in editing my question and your answer. Yes you are right regarding the case when $K = 2$. However, your wild conjecture is incorrect. When $N = K$, equally distributing all $x_i$ at $j/(K-1)$ for $j = 0, ...,K-1$ doesnot maximize the vandermonde product. This can be verified by considering $N = K = 4$. In this case, the $x_i$ values $\{0, 0.275, 0.725, 1\}$ lead to a higher vandermonde product than $\{0, 0.33, 0.66, 1\}$ $\endgroup$ – peng Aug 17 '14 at 7:56
  • $\begingroup$ Actually, my conjecture is that for general $N$ and $K$, the optimal values of $x_i$ should take only $K$ different values, and the numbers of $x_i$ taking the same value should be approximately the same. For example, when $N = 8$ and $K = 4$, the numerical solution I obtained is $x_1 = x_2 = 0$, $x_3 = x_4 = 0.275$, $x_5 = x_6 = 0.725$ and $x_7 = x_8 = 1$. My first difficulty now is to prove this conjecture. $\endgroup$ – peng Aug 17 '14 at 8:02
  • $\begingroup$ Ah I didn't know equal spacing doesn't give max vandermonde, what's the maximizing $x_i$'s in the $N=K$ case? Now it's clear that if the maximizing solution has $L$ distinct values, you want to equally distribute $x_i$'s among those $L$ values. And those $L$ values should be maximizing ones when $N=L$. It remains to show that indeed one should take $L=K$. $\endgroup$ – John Jiang Aug 17 '14 at 8:19
  • 2
    $\begingroup$ For the Vandermonde determinant itself, the points which maximize it might be called logarithmic Fekete points. I haven't found a description of them directly for the interval, but they might be related to the roots of some orthogonal polynomials. $\endgroup$ – Douglas Zare Aug 17 '14 at 20:03
2
$\begingroup$

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$).

$\endgroup$
  • $\begingroup$ Sorry for my late response and thank you very much for your answer! It looks correct, but in your answer you mentioned the paper of Bos, Taylor and Wingate. Could you please tell me the paper title and where I can find this paper? $\endgroup$ – peng Sep 3 '14 at 7:34
  • $\begingroup$ It's here (already cited in another comment): 130.44.194.100/mcom/2001-70-236/S0025-5718-00-01262-X/… . Since it contains a raw internet address it's not allowed to use this as a link in an answer. $\endgroup$ – jjcale Sep 3 '14 at 17:47
1
$\begingroup$

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$.

N=2

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()

N=3

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.

$\endgroup$
  • $\begingroup$ Thanks Moritz Firsching for providing the answer. I have the following concerns about this answer. $\endgroup$ – peng Aug 21 '14 at 7:16
  • $\begingroup$ The first one is about the matrix $Q$ in the case of $K = 2$. I think the digaonal entries of $Q$ should be $N-1$, instead of $1$. $\endgroup$ – peng Aug 21 '14 at 7:28
  • $\begingroup$ The second is about the table, in which the function value for $N = 3$ and $K = 2$ should be $2$, instead of $3$ $\endgroup$ – peng Aug 21 '14 at 7:29
  • $\begingroup$ Actually, I think this answer expresses the same conjecture as mine - that for general $N$ and $K$ , the optimal values of $x_i$ should take only $K$ different values, and the numbers of $x_i$ taking the same value should be approximately the same. My difficulty is indeed to prove this conjecture. Therefore, this answer doesnot EXACTLY answer my question. Can you provide me a rigious proof for this conjecture? Thanks a lot! $\endgroup$ – peng Aug 21 '14 at 7:32
  • $\begingroup$ @peng you are right about $Q$ and the case $N=3$, $K=2$. I corrected it. $\endgroup$ – Moritz Firsching Aug 21 '14 at 14:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.