5
$\begingroup$

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.)

Improve this question
$\endgroup$
5
  • 3
    $\begingroup$ Do you want to show that the polytope is entirely outside the sphere or entirely inside it? For the first, you only have to exhibit a separating plane with the sphere on one side and the polytope on the other. For the second, you have to show that all the polytope vertices are inside the sphere. $\endgroup$
    – Yoav Kallus
    Commented Dec 9, 2016 at 15:46
  • $\begingroup$ Ah, when you phrase it like that it is much simpler! Thanks. (I wouldn't object if someone wants to close this question.) $\endgroup$
    – user47305
    Commented Dec 9, 2016 at 16:24
  • $\begingroup$ @YoavKallus Unfortunately, this is exponential time, in general (since the number of vertices is potentially exponential in the number of constraints. $\endgroup$
    – Igor Rivin
    Commented Dec 10, 2016 at 2:01
  • $\begingroup$ But this most probably can only be done in exponential time. The hard case seems to be able to check whether the polytope is contained in the interior of the unit ball $B$. Indeed, one can check quickly whether the intersection of the polytope and $B$ is nonempty, but this is not quite enough. $\endgroup$
    – Dima Pasechnik
    Commented Dec 10, 2016 at 9:40
  • $\begingroup$ it is indeed hard to do, see my answer below. $\endgroup$
    – Dima Pasechnik
    Commented Dec 10, 2016 at 10:38

2 Answers 2

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
2
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ No, if your polytope contains the origin $O$, i.e. $O=(0,\dots,0)$, and $b\geq 0$ and $c\geq 0$ then the minimum will be reached at $O$, and not in a point on the unit sphere. $\endgroup$
    – Dima Pasechnik
    Commented Dec 10, 2016 at 9:01
  • $\begingroup$ @DimaPasechnik I just drew several polytopes that contain the origin and the minima are not attained at the origin, but either at the boundary of the polytope or at the unit sphere, depending on the cost function. Also, do you think my answer is salvageable in any way? $\endgroup$
    – Rodrigo de Azevedo
    Commented Dec 10, 2016 at 9:15
  • $\begingroup$ Actually, your SDP checks that the intersection of the unit ball and the polytope is nonempty. Now, what can happen is that still their boundaries do not intersect (i.e. one is contained in the other), and then you are out of luck this way. $\endgroup$
    – Dima Pasechnik
    Commented Dec 10, 2016 at 9:21
  • $\begingroup$ @DimaPasechnik If the polytope is contained in the unit ball, the SDP returns a point on the boundary of the polytope. However, if the unit ball is contained in the polytope, then the SDP should return a point on the unit sphere. $\endgroup$
    – Rodrigo de Azevedo
    Commented Dec 10, 2016 at 9:34
  • $\begingroup$ indeed in the latter case you are done, but not in the former. To decide this you would need to see whether you can reach the boundary, i.e. to maximize $\|x\|^2$ on the polytope---a non-convex problem. $\endgroup$
    – Dima Pasechnik
    Commented Dec 10, 2016 at 9:50

You must log in to answer this question.