# Solving a linear program, but over the unit sphere

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!

• If you replace $\|\mathbf{x}\|_2 = 1$ with $\|\mathbf{x}\|_2 \leq 1$, you can rewrite as a (convex) semidefinite program. – Rodrigo de Azevedo Jul 29 '19 at 8:30
• I had known about this technique but didn't mention it because for my specific problem, the optimum over the unit-ball does not lie on the unit sphere, and I specifically need $\textbf{x}$ on the sphere itself. Is there a way to use this relaxation to find optima on the sphere itself? Perhaps by modifying the cost function to penalize smaller $\|\textbf{x}\|$ ? Something like $\textbf{c}^T \textbf{y} - \gamma \| \textbf{x} \|_2$ for some $\gamma$ ? – kklosteer Jul 29 '19 at 21:25
• Seems related: google.com/url?sa=t&source=web&rct=j&url=http://… – user35593 Apr 19 '20 at 10:48

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.

• Nice! Great solution, thank you. – kklosteer Apr 19 '20 at 22:50