Take the 2-minute tour ×  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.
share|improve this question Do I correctly understand that the
computational time shouldn't depend on point