Solving a linear program, but over the unit sphere

Question

I want to solve a linear program but with a subset of the variables taken from a unit sphere. That is, given fixed $\textbf{c} \in \mathbb{R}^{n}$, $\textbf{A} \in \mathbb{R}^{m \times (n+k)}$, I want to find variables $\left[ \begin{array}{c} \textbf{x} \\ \textbf{y} \end{array} \right]$ with $\textbf{x} \in \mathbb{R}^k$ and $\textbf{y} \in \mathbb{R}^n$ so that

$\min~~\textbf{c}^T \textbf{y}$

$s.t.~~\textbf{A} \left[ \begin{array}{c} \textbf{x} \\ \textbf{y} \end{array} \right] \geq 0$

$and~~~~\|\textbf{x}\|_2 = 1$.

Introducing the equality constraint on the norm of $\textbf{x}$ makes the problem a (non-convex) quadratically-constrained linear program. My understanding is that problems with non-convex constraints are not easy to solve in the general case (e.g., solving a general QCQP is an NP-hard problem).

That said, this problem has some structure to it --- the objective function is linear, and in particular the only quadratically constrained variables $\textbf{x}$ do not (explicitly) appear in the objective function.

With that in mind, I have two questions:

(1) Is this problem type a well-studied sub-problem of some sort? It seems like the unit-vector constraint is common enough that the problem type might be studied in its own right (e.g. linear program, over a unit sphere). Can this be converted to a well-studied problem type (e.g. a semidefinite program) that has an efficient solution?

(2) Regardless of the answer to (1), is there a good approach to solving this optimization problem? An efficient means of solving it or obtaining a good approximation?

I'd be grateful for any insight. Thank you!

Answer 1

Going by the first comment, the optimal solution to the convex problem (= replaced by $\leq$) must give a solution on the unit sphere. Firstly, Since $\{0,0\}$ is a feasible point, the optimal value cannot be positive. It can either be $0$ or negative. If its zero, an optimal solution can be scaled to lie on the unit sphere. So it suffices to check for negative case.

Now suppose $||x^*||=\delta<1$ for an optimal solution $\{x^*, y^*\}$. One can then choose the feasible point $\{\frac{1}{\delta}x^*,\frac{1}{\delta}y^*\}$, which has a smaller cost. This is a contradiction to the assumption of optimality.