Timeline for Minimizing $x_1^2+x_2^2+x_3^2+x_1x_2+x_2x_3+x_3x_1$
Current License: CC BY-SA 3.0
20 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 24, 2016 at 10:24 | comment | added | Kurisuto Asutora | PS: One more thing I understood. Assume for example $p=9$, and $n=100$. Then for $x_1 = \dots = x_{100} = 1$ the quadratic form has value 1000. However, for the choice $x_1 = x_{11} = x_{21} = x_{31} = \dots =x_{91} = 10$ and all other $x_n$ being zero, the quadratic form also gives 1000. So the situation is not as simple as I thought. These things must also be reflected in the eigenvalues, somehow. | |
| Nov 24, 2016 at 9:02 | comment | added | Kurisuto Asutora | Also, I just realized that the eigenvectors do not depend on the matrix at all. This gives me more freedom, since I can "average" over different values of $p$. (In the last coordinate in your eigenvector there is a typo, this sould probably be $\omega^{(n-1)}$ instead of $\omega^{k(n-1)}$.) | |
| Nov 24, 2016 at 8:44 | comment | added | Kurisuto Asutora | If I did not make a mistake, then for $n \gg p$ the minimal eigenvalue has index $k \approx 3n/(2(2p+1))$, and for the eigenvalue you get roughly $1/2-1/2(\sin(3\pi/(2(2p+1))) \approx 1/2 - 3 \pi /(2(2p+1))$. For large $p$ this is roughly $-2/(3 \pi) p \approx - 0.21 p$. | |
| Nov 24, 2016 at 8:15 | comment | added | Ivan Izmestiev | @KurisutoAsutora Yes, some interesting questions still remain. Your observation about $\frac{p}4$ is interesting. | |
| Nov 24, 2016 at 8:11 | comment | added | Kurisuto Asutora | On the other hand, negative eigenvalues correspond to eigenvectors whose index $k$ is close to $0$ or $n$. If $p$ remains fixed, then these indices move closer and closer to 0. I will have to think about what this means for my numbers $x_1, \dots, x_n$. | |
| Nov 24, 2016 at 8:09 | comment | added | Kurisuto Asutora | @Ivan: okay, thanks. I will have to think about this a bit. In my application, $n$ will be much larger than $p$, so plotting $\lambda_k$ actually looks roughly like a continuous function in $k/n$. To keep this positive one will not need $p$ on the diagonal, but only $p/4$ or so, but this is still by far too much for me. | |
| Nov 23, 2016 at 18:50 | comment | added | Ivan Izmestiev | @KurisutoAsutora As for your next comment, if you put $p$ on the diagonal, you will get a positive definite matrix (it is "diagonally dominated", the corresponding quadratic form can be written explicitly as a sum of squares). I'm afraid that if the diagonal entries are smaller than $p$, the form remains negative definite (for some $n$ and $p$). | |
| Nov 23, 2016 at 18:48 | comment | added | Ivan Izmestiev | @KurisutoAsutora The point $(1, \ldots, 1)$ is a critical point of the function restricted to $\sum_i x_i = \mathrm{const}$, because the gradient at this point is proportional to $(1, \ldots, 1)$. Detecting if this critical point is a local (and then the global) minimum is done by the signature of the Hessian. (And $(1, \ldots, 1)$ is a positive direction anyway.) I think this is also more or less what you mean... | |
| Nov 23, 2016 at 18:24 | comment | added | Kurisuto Asutora | PS: If I understand these things correctly now, I can force all eigenvalues to be positive if I increase the coefficients in the main diagonal a bit (from 1 to 2, say). This might be sufficient for the application I have in mind. | |
| Nov 23, 2016 at 18:16 | comment | added | Kurisuto Asutora | @Ivan: thanks a lot, this is helping greatly. Still, I seem to be missing something. How does the positivity of all eigenvalues imply the desired bound? Is this, roughly speaking, because the eigenvectors are orthogonal? Then the eigenvectors form an orthogonal basis, and we can write every vector as a linear combination. This would mean that the coefficient for the eigenvector (1,...,1) has to be 1, because we assume that $x_1+\dots+x_n=n$, and non-zero coefficients for other basis vectors would give non-negative contribution (since eigenvalues are non-negative) - is this how it works? | |
| Nov 23, 2016 at 17:24 | comment | added | Fedor Petrov | @IvanIzmestiev ah, it splits. I see now | |
| Nov 23, 2016 at 17:15 | comment | added | Ivan Izmestiev | @FedorPetrov sorry, I misunderstood. But I am putting 1 on the diagonal. Later, in the first displayed formula this 1 gets split into $\frac12$ and $\frac12 \omega^0$. | |
| Nov 23, 2016 at 16:56 | comment | added | Fedor Petrov | @IvanIzmestiev this is about non-diagonal entries, but $x_1^2$ corresponds to 1 on the diagonal, does not it? | |
| Nov 23, 2016 at 15:59 | comment | added | Ivan Izmestiev | @Kurisuto Asutora : From the calculus viewpoint we are computing the signature of the matrix of the second derivatives (which happens to be twice the same circular matrix). Minimum corresponds to positive definiteness corresponds to positive eigenvalues. From the linear algebra viewpoint we are finding the principal axes and determining the signature of a quadratic form. Only if all eigenvalues are positive, the level set $Q(x,x) = \mathrm{const}$ will be an ellipsoid, so its tangent hyperplane of the form $\sum_i x_i = \mathrm{const}$ will lie "on the right side" from it. | |
| Nov 23, 2016 at 15:51 | comment | added | Ivan Izmestiev | @Fedor Petrov : because $x_1x_2$ also occurs as $x_2x_1$. | |
| Nov 23, 2016 at 15:36 | comment | added | Kurisuto Asutora | PS: I don't understand the remark on the negative eigenvalues - I am not familiar with these things. Can I deduce from the eigenvalues a lower bound for the minimal value of the quadratic form? Obviously for all variables equal to one gets $n(p+1)$ - which role do the negative eigenvalues play here, and how far below $n(p+1)$ can it go? | |
| Nov 23, 2016 at 15:25 | comment | added | Kurisuto Asutora | Thanks, this is brilliant - I suppose I would have needed a few years to figure that our myself. | |
| Nov 23, 2016 at 15:19 | comment | added | Fedor Petrov | Why $1/2$ on the diagonal, not 1? | |
| Nov 23, 2016 at 15:17 | vote | accept | Kurisuto Asutora | ||
| Nov 23, 2016 at 14:04 | history | answered | Ivan Izmestiev | CC BY-SA 3.0 |