Timeline for Minimize sum of $\ell_2$ norm and linear combination, on simplex
Current License: CC BY-SA 3.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 26, 2015 at 11:30 | history | bounty ended | CommunityBot | ||
| Dec 21, 2015 at 21:19 | comment | added | fedja | @dohmatob Yeah, but the same degeneracy arises also when $|b|=1$ and the ray $a-\rho b$ intersects the interior of the simplex (I doubt you can exclude such configurations as well). So, sometimes the iterations work poorly while the bisection never fails. What I really wonder about at this moment is how complicated the projection of a line to the simplex can be. If we could show that the corresponding broken line never has too many very short segments, we could make something provably finite out of the current scheme. | |
| Dec 21, 2015 at 20:31 | comment | added | dohmatob | Yes, we all agree that the case $\|b\| \ge 1$ has tricky numerics (for example the thing above doesn't handle such cases). Also I failed to mention in the original question that the simplex doesn't contain the point $a$. Repaired. | |
| Dec 21, 2015 at 19:44 | comment | added | fedja | @dohmatob The alternating algorithm certainly makes the functional smaller at each step and you can show that when the change in one step is small, then the value is close to the optimal. However there are degenerate situations where the minimizer is not unique (say, $a$ is inside the simplex and $|b|=1$), so the position of the minimizer is, generally speaking, discontinuous in $b$, while any finite iteration procedure is certainly continuous in $b$. This shows that near such degenerate situations there is no guaranteed speed of convergence of the iterative algorithm. | |
| Dec 21, 2015 at 19:28 | comment | added | dohmatob | I don't think you'll ever be needing the bisection machinery here. An alternating algorithm: $x^{(k+1)} = \mathrm{proj}_C(a + \rho^{(k)}b)$, $\rho^{(k+1)} = \|x^{(k+1)}-a\|$ should provably work. | |
| Dec 21, 2015 at 19:13 | comment | added | dohmatob | numerical limitations induced by machine-precision are fundamentally different from limitations induced by an algorithm which is not guaranteed to produce an exact solution in finite time even on an ideal arbitrary-precision machine. These are totally different worries. | |
| Dec 21, 2015 at 18:41 | history | edited | fedja | CC BY-SA 3.0 |
added 2287 characters in body
|
| Dec 21, 2015 at 14:53 | comment | added | dohmatob | BTW, indeed numerically, the algorithm is observed to converge in finitely-many steps (typically less than $5$). This is what motivated the proof. | |
| Dec 21, 2015 at 14:49 | comment | added | dohmatob | Yes you're right, it was too good to be true. The $\gamma^{-1}$ factor next to the $b$ iwas an error (fixed). I've scaled down my claim to the statement: If $\|b\| < 1$, then Fedja's algorithm convergences Q-linearly at rate $\|b\|$. The proof should contain no gaps now. About why, I'm interested in making this rigorous, I stated in the original problem that I wanted the solution method to be exact. Since all we have at the moment is an iterative scheme, the least of things would be to show that it converges in finitely many steps (or a slightly weaker statement). Thus the proof above. | |
| Dec 21, 2015 at 4:14 | comment | added | fedja | @dohmatob Thanks. However, are you sure that it is $\gamma^{-1}b$ and not just $b$ in your scaling? It looks to me that when you change $C$ to $\gamma C$ and $a$ to $\gamma a$, you would like the whole expression, including the scalar product, to be multiplied by $\gamma$ to get the desired homogeneity. Of course, the case of small $|b|$ is very nice because the change in the distance always dominates the change in the scalar product but it would be interesting to see what happens with moderate size $|b|$ as well. I would just run the iterations and see before trying to prove anything. | |
| Dec 20, 2015 at 17:57 | comment | added | dohmatob | The introduction of the radial parameter r is brilliant, and didn't occur to me. Indeed your proposed scheme converges in essentially 1 iteration. I've augmented my question with a rigorous proof of this fact (with a slight modification of the r update). You have my upvote. I leaving the bounty open for a while to see if I can attract answers of similar quality. | |
| Dec 20, 2015 at 5:17 | history | answered | fedja | CC BY-SA 3.0 |