most recent 30 from http://mathoverflow.net 2013-05-21T10:43:12Z http://mathoverflow.net/feeds/question/92233 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/92233/projection-onto-a-quadratic-cone fuzzytron 2012-03-26T06:55:13Z 2012-04-10T23:22:01Z

<p>Consider a constraint of the form</p> <p>$$ f(x) := x^T A x = 0 $$</p> <p>where $A \in \mathbb{R}^n$ is symmetric but may be singular and indefinite. The constraint set $C$ is a (nonconvex) cone, since for any $x \in C$ we also have $ux \in C$ for all $u \in \mathbb{R}$.</p> <p>Given a point $x_0$ not necessarily in $C$, I am seeking a cheap computational procedure for finding a nearby (in the Euclidean sense) point $x \in C$. "Nearby" means something like the distance between $x$ and the closest point $x^* \in C$ can be bounded in terms of the distance between $x_0$ and $C$. "Cheap" means something like $O(n \log n)$ or some (very) small polynomial at worst.</p> <p>Performing exact line search along the constraint gradient $-2Ax$ is one idea, yielding a single scalar quadratic equation for the shortest time t: $\min_t f(x_0 - 2tAx_0)$. Unfortunately, the roots of this equation are not always real.</p> <p>Thanks!</p>

http://mathoverflow.net/questions/92233/projection-onto-a-quadratic-cone/92418#92418 Arthur B 2012-03-27T22:22:05Z 2012-03-27T22:42:23Z

<p>If you write the problem of finding the closest point to $x_0$ on the cone with a Lagrange multiplier, the solution must have the form $x = (\lambda A + I )^{-1}x_0$.</p> <p>If you start by diagonalizing $A$, the inverse can be computed efficiently and you can search for $\lambda$ by dichotomy. The algorithm will run in $O(n^2 \log{1/\epsilon})$</p>