Timeline for Minimise $\sum_i \begin{Vmatrix}\boldsymbol{x}_i \\ \boldsymbol{y}_i\end{Vmatrix}$
Current License: CC BY-SA 4.0
19 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 3, 2019 at 11:02 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Oct 3, 2019 at 22:21 | answer | added | Federico Poloni | timeline score: 1 | |
| Oct 3, 2019 at 12:00 | history | reopened |
R.P. Federico Poloni Carlo Beenakker Mark Wildon Todd Trimble |
||
| Oct 1, 2019 at 11:40 | comment | added | Federico Poloni | Yes, I am now convinced that my comments produce a full answer: (1) reduce to $j-k=1$ as above, then (2) reformulate as $\min dist(0,z_1)+ dist(z_1,z_1+z_2) + dist(z_1+z_2,z_1+z_2+z_3) + \dots + dist(z_1+\dots+z_{n-1}, z_1+\dots+z_n)$, where the last point does not depend on the $x_i$ (3) apply triangle inequality to conclude that the points must be aligned. I can write it down in more detail if the question gets reopened (currently it has 4 votes, and I think 5 are needed). | |
| Oct 1, 2019 at 11:32 | comment | added | Federico Poloni | For the simplest case, $k=1,j=2,n=2$, there is a standard trick from math Olympiad literature which is reformulation as sum of distances: the polygonal line that connects $A = (0,0)$, $B = (x_1,y_1)$ and the fixed point $C = (x_1+x_2,y_1+y_2) = (c,y_1+y_2)$ has length equal to the objective function, and by the triangle inequality it is minimized when one chooses $x_1$ so that the three points are aligned. Maybe I am missing some crucial details, but it looks like the idea can be generalized to higher $j$ (working one dimension at a time) and $n$ (working with more than three points). | |
| Oct 1, 2019 at 9:28 | comment | added | Lincoln Hannah | Federico, thanks for adding the double bars. I was going to do that this morning. I've made two more changes. One in the heading and moving the over-bar outside the double bars for the sum of y. Feel free to change back. Yes agree $j-k=1$ makes it simpler and doesn't affect the result. | |
| Oct 1, 2019 at 9:26 | history | edited | Lincoln Hannah | CC BY-SA 4.0 |
added 4 characters in body; edited title
|
| Oct 1, 2019 at 6:43 | comment | added | Federico Poloni | A first simplification is that you can assume that $j-k=1$, by replacing $\boldsymbol{y}_i$ with the scalar $\|\boldsymbol{y}_i\|$. | |
| Oct 1, 2019 at 6:28 | history | edited | Federico Poloni | CC BY-SA 4.0 |
changed single bars to double bars, lowercased c, retagged, other smaller edits.
|
| Sep 30, 2019 at 18:36 | comment | added | Lincoln Hannah | Yes, Euclidean norm. Sorry didn't realise I needed double bars. Unfortunately it is lengths not squared lengths. | |
| Sep 30, 2019 at 17:20 | comment | added | Federico Poloni | It does help, thanks! So $|v|$ is the Euclidean norm of $v$, $(\sum_{i=1}^n |v_i|^2)^{1/2}$? This is usually denoted with double bars, $\|v\|$. In particular, do you confirm that you sum lengths, not squared lengths (which would make the question a lot easier)? | |
| Sep 30, 2019 at 14:55 | review | Reopen votes | |||
| Sep 30, 2019 at 23:32 | |||||
| Sep 30, 2019 at 14:41 | comment | added | Lincoln Hannah | Hope this helps. All straight lines are vector lengths, not component-wise absolute values. | |
| Sep 30, 2019 at 14:35 | history | edited | Lincoln Hannah | CC BY-SA 4.0 |
added 1014 characters in body
|
| Sep 30, 2019 at 13:10 | comment | added | Federico Poloni | I voted to put this on hold, but this could be a reasonable question for MO, after an edit makes the question clearer; don't be discouraged by the (temporary) closure. | |
| Sep 30, 2019 at 12:01 | history | closed |
Mark Wildon David Roberts♦ LeechLattice R.P. Federico Poloni |
Needs details or clarity | |
| Sep 30, 2019 at 11:55 | review | Close votes | |||
| Sep 30, 2019 at 12:05 | |||||
| Sep 30, 2019 at 11:10 | review | First posts | |||
| Sep 30, 2019 at 11:22 | |||||
| Sep 30, 2019 at 11:05 | history | asked | Lincoln Hannah | CC BY-SA 4.0 |