Intersecting a convex polytope with the unit sphere I have a list of $m$ affine inequalities in $n$ variables of the following form 
$$a_1 x_1 + \cdots + a_n x_n \leq c_n$$
I would like to know whether there is any point on the unit sphere in $\mathbb R^n$ that satisfies all of them.  Is there any easy way to check whether this is the case?
(Based on randomly choosing points, it seems like there are no solutions, but I'd like an algorithm that's up to journal standards of proof.)
 A: It was proved by Freund and Orlin that the problem of checking whether a polytope specified by linear inequalities is not entirely contained in a ball specified by its centre and radius is NP-complete. 
And it is obvious that one can assume that the ball is a unit ball, for the corresponding transformation (shift+scaling) can be carried out in polynomial time.
Thus there is little hope for an efficient algorithm for the problem at hand.
A: Given a matrix $\mathrm A \in \mathbb R^{m \times n}$ and a vector $\mathrm b \in \mathbb R^m$, we define the (convex) polytope
$$\mathcal P := \{ \mathrm x \in \mathbb R^n \mid \mathrm A \mathrm x \leq \mathrm b \}$$
We can determine whether $\mathcal P$ is empty using linear programming. Let the unit Euclidean sphere be
$$\mathcal S := \{ \mathrm x \in \mathbb R^n \mid \| \mathrm x \|_2 = 1 \}$$
We would like to determine whether the intersection $\mathcal P \cap \mathcal S$ is empty or not.
Since $\mathcal S$ is non-convex, we relax the equality constraint $\| \mathrm x \|_2 = 1$ and consider the unit Euclidean ball instead
$$\mathcal B := \{ \mathrm x \in \mathbb R^n \mid \| \mathrm x \|_2 \leq 1 \}$$
which is convex. Using the Schur complement test for positive semidefiniteness, the unit ball $\mathcal B$ can be represented by the following linear matrix inequality (LMI) [0]
$$\begin{bmatrix} \mathrm I_n & \mathrm x\\ \mathrm x^{\top} & 1\end{bmatrix} \succeq \mathrm O$$
Polytope $\mathcal P$ can also be represented by an LMI, namely,
$$\mbox{diag} \, (\mathrm b - \mathrm A \mathrm x) \succeq \mathrm O$$
The conjunction of these two LMIs produces the following LMI [0]
$$\begin{bmatrix} \mbox{diag} \, (\mathrm b - \mathrm A \mathrm x) & \mathrm O & \mathrm O\\ \mathrm O & \mathrm I_n & \mathrm x\\ \mathrm O & \mathrm x^{\top} & 1\end{bmatrix} \succeq \mathrm O$$
Picking an arbitrary nonzero linear objective function, we have the semidefinite program (SDP)
$$\begin{array}{ll} \text{minimize} & \mathrm c^{\top} \mathrm x\\ \text{subject to} & \begin{bmatrix} \mbox{diag} \, (\mathrm b - \mathrm A \mathrm x) & \mathrm O & \mathrm O\\ \mathrm O & \mathrm I_n & \mathrm x\\ \mathrm O & \mathrm x^{\top} & 1\end{bmatrix} \succeq \mathrm O\end{array}$$
If this SDP is infeasible, then $\mathcal P \cap \mathcal B = \emptyset$, which implies that $\mathcal P \cap \mathcal S = \emptyset$.
If this SDP is feasible, let $\mathrm x^*$ be the optimal solution produced by the SDP solver.


*

*If $\|\mathrm x^*\|_2 = 1$, we conclude that $\mathcal P \cap \mathcal S \neq \emptyset$.

*If $\|\mathrm x^*\|_2 \neq 1$, we cannot conclude anything. We can solve the SDP for various values of randomly chosen $\mathrm c \in \mathbb R^n$ and hope that the solver will produce an optimal solution on the unit Euclidean sphere. However, this trial and error approach is not very satisfying.

[0] Stephen Boyd, Laurent El Ghaoui, Eric Feron, Venkataramanan Balakrishnan, Linear Matrix Inequalities in System and Control Theory, Society for Industrial and Applied Mathematics, 1994.
