Projection onto a quadratic cone?

Question

Consider a constraint of the form

$$ f(x) := x^T A x = 0 $$

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}$.

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.

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.

Thanks!

Answer 1

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$.

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})$