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!



Solving a linear program, but over the unit sphere
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. 


