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.