Timeline for How to solve such an optimization problem
Current License: CC BY-SA 3.0
32 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 14, 2023 at 20:55 | answer | added | Giovanni | timeline score: -1 | |
| Sep 13, 2014 at 16:26 | history | edited | Moritz Firsching | CC BY-SA 3.0 |
improved tagging
|
| Aug 31, 2014 at 12:19 | answer | added | jjcale | timeline score: 2 | |
| Aug 25, 2014 at 2:10 | comment | added | peng | @MoritzFirsching: Thanks! That sounds intersting. But I'm afraid that expanding the target function into polynomial doesnot yield an elementary symmetric polynomial. Maybe I didn't get it. Could you please elaborate more? | |
| Aug 25, 2014 at 2:07 | comment | added | peng | @jjcale: Thanks, I also found this paper written by Fejer, but it is in Germany. I cound not understand it... | |
| Aug 25, 2014 at 1:16 | history | edited | peng | CC BY-SA 3.0 |
added 12 characters in body
|
| Aug 25, 2014 at 0:56 | history | edited | peng | CC BY-SA 3.0 |
added 12 characters in body
|
| Aug 24, 2014 at 18:11 | comment | added | Moritz Firsching | Maybe writing the function to be maximized in terms of elementary symmetric polynomials would help? | |
| Aug 24, 2014 at 10:03 | comment | added | jjcale | Here a link to the paper of Fejer : math.technion.ac.il/hat/fpapers/fejerpisa.pdf | |
| Aug 21, 2014 at 7:45 | history | edited | peng | CC BY-SA 3.0 |
added 4 characters in body
|
| Aug 21, 2014 at 7:42 | comment | added | peng | Many thanks to Douglas Zare~! Sorry I didn't acknowledge your comments timely as I'm recently reading some papers related to Fekete problem and Gauss-Lobatto points. Unfortunately, I still have not understood how the claim that the Gauss-Lobatto points maximize the Vandermonde determinant on [−1,1] is proved. Nor have I found the closed-form expressions of the Gauss-Lobatto points for a given $N$ (or $K$). I will be greatly appreciated if you could talk more about the proof and the closed-form expressions. | |
| Aug 20, 2014 at 15:30 | answer | added | Moritz Firsching | timeline score: 1 | |
| Aug 18, 2014 at 2:45 | comment | added | Douglas Zare | 130.44.194.100/mcom/2001-70-236/S0025-5718-00-01262-X/… mentions that the Gauss-Lobatto points maximize the Vandermonde determinant on $[-1,1]$, citing another paper: Fej´er, L., Bestimmung derjenigen Abszissen eines Intervalles f¨ur welche die Quadratsumme der Grundfunktionen der Lagrangeschen Interpolation im Intervalle [−1, 1] ein m¨oglichst kleines Maximum besitzt, Ann. Scuola Norm. Sup. Pisa Sci. Fis. Mt. Ser. II, 1, 263–276, 1932. | |
| Aug 18, 2014 at 0:56 | comment | added | peng | Sorry for my carelessness. The title of that paper was given at bottom of that link, but the original paper is not in English. Do you know where I can fint its English version, or another English paper providing the solution? | |
| Aug 18, 2014 at 0:45 | comment | added | peng | Thanks Douglas Zare! Yes, my problem when $N = K$ is just the one-dimensional logarithmic Fekete points problem. By the linke en.wikipedia.org/wiki/Fekete_problem I found that "The problem originated in the paper by Michael Fekete (1923) who considered the one-dimensional, s = 0 case, answering a question of Issai Schur." However, it is not mentioned which paper it is. Do you know the title of this paper? or can you tell me where I can find this paper? | |
| Aug 17, 2014 at 20:03 | comment | added | Douglas Zare | 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. | |
| Aug 17, 2014 at 10:46 | comment | added | Douglas Zare | If you use the range $[-1,1]$, then for $N=K=6$, the optimum seems to occur at the roots of $21x^6-35x^4+15x^2-1.$ | |
| Aug 17, 2014 at 8:49 | comment | added | John Jiang | Take $N=K(K+1)$ for simplicity. One should be able to show $L=K+1$ is worse than $L=K$. Maximizing $x_i$'s for the case $N=K$ seem pretty hairy. | |
| Aug 17, 2014 at 8:26 | comment | added | peng | As for my problem in the special case of $N = K$, I have proved that the problem is quasi-convex and thus can be numerically solved, but analytically solving it to arrive at a closed-form expression of $\{x_i\}$ are yet to be obtained, which is also my second difficulty. | |
| Aug 17, 2014 at 8:24 | comment | added | peng | Thanks John for your prompt reply. Yes you are right, but I havn't prove my first conjecture after tring many approaches. Do you have any ideas? | |
| Aug 17, 2014 at 8:19 | comment | added | John Jiang | 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$. | |
| Aug 17, 2014 at 8:08 | history | edited | peng | CC BY-SA 3.0 |
added 6 characters in body
|
| Aug 17, 2014 at 8:02 | comment | added | peng | 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. | |
| Aug 17, 2014 at 7:57 | history | edited | peng | CC BY-SA 3.0 |
added 2 characters in body
|
| Aug 17, 2014 at 7:56 | comment | added | peng | 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\}$ | |
| Aug 17, 2014 at 7:48 | history | edited | peng | CC BY-SA 3.0 |
added 2 characters in body
|
| Aug 17, 2014 at 7:48 | comment | added | John Jiang | 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. | |
| S Aug 17, 2014 at 7:43 | history | suggested | John Jiang | CC BY-SA 3.0 |
correct typo
|
| Aug 17, 2014 at 7:39 | review | Suggested edits | |||
| S Aug 17, 2014 at 7:43 | |||||
| Aug 17, 2014 at 7:29 | history | edited | peng | CC BY-SA 3.0 |
added 25 characters in body
|
| Aug 17, 2014 at 7:27 | review | First posts | |||
| Aug 17, 2014 at 7:57 | |||||
| Aug 17, 2014 at 7:22 | history | asked | peng | CC BY-SA 3.0 |