most recent 30 from http://mathoverflow.net 2013-05-22T15:21:48Z http://mathoverflow.net/feeds/question/109547 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/109547/finding-the-nearest-extreme-point-to-a-point-inside-a-polyhedron TF 2012-10-13T17:04:19Z 2012-10-13T17:04:19Z

<p>Is there a way to find the nearest extreme point (or at least a "reasonably close" extreme point) to a given point inside a polyhedron? ("nearest" in the L1 norm sense).</p> <p>I am working in $\mathbb{R}^{145}$, with a polytope defined by 589 constraints, so enumerating all the extreme points and comparing the distances is not really an option.</p> <p>I particularly care about 48 of the 145 components. So finding an extreme point with close values for these 48 components, and "if-possible-close" values for the 97 other components, would do.</p>