Timeline for Are there subsets L in R^n such that it is "easy to find" closest point in L to a given P in R^n ? Vague question motivated by error-correcting codes
Current License: CC BY-SA 3.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 22, 2012 at 18:53 | comment | added | Robert Israel | In general, convex programming (in this case, minimizing a convex function on a convex set) is considered "easy" these days. Non-convex programming tends to be hard. In particular, the closest point problem on a non-convex closed set may not have a unique solution, and local optima are not necessarily global optima. | |
| Jun 22, 2012 at 12:24 | comment | added | Alexander Chervov | "Easy" means -- something more clever than any of standard minimization algorithms (steepest descent or whatever) - something which will take specific properties of M into account. Well I am keeping analogy with soliton equations in mind - to find such point is to solve some equations - if there are something like "soliton" like equations for this problem than one can use specific methods to solve them, rather than general numeric schemes... this analogy is very vague... | |
| Jun 22, 2012 at 12:12 | history | edited | user24527 | CC BY-SA 3.0 |
added 211 characters in body
|
| Jun 22, 2012 at 11:51 | comment | added | Alexander Chervov | I do not quite understand. Do you mean that if the set is convex then we might find the nearest point in it to E outside it, in some simple way ? | |
| Jun 22, 2012 at 11:06 | history | answered | user24527 | CC BY-SA 3.0 |