# A question about polytopes related to linear programming

Given linear functions $$f_1({\bf x}),\dots,f_n({\bf x})$$ on $${\bf R}^m$$, let $$K = \{(a_1,\dots,a_n) \in {\bf R}^n:$$ the $$n$$ halfspaces $$\{{\bf x}: f_i({\bf x}) \leq a_i\}$$ have nonempty intersection$$\}$$. If $$K$$ is compact, must it be a polytope?

(It's not hard to show that $$K$$ is convex. I imposed compactness to avoid questions about what I mean by a noncompact polytope.)

This question has probably arisen in linear programming, since it is natural to consider parametrized sets of linear programs, and to ask whether the set of parameter-values giving rise to feasible linear programs is itself characterized by linear inequalities.

By Farkas' Lemma (https://en.wikipedia.org/wiki/Farkas%27_lemma),

• $$\mathbf{A}{x}\leq \mathbf{b}$$ has a solution $$\mathbf{x}\in\mathbb{R}^n$$ if and only if for all $$\mathbf{y}\geq 0$$ with $$\mathbf{A}^T\mathbf{y}=0$$, we have $$\mathbf{b}^T\mathbf{y} \geq 0$$.

Now the set $$\{\mathbf{y} \textrm{ such that } \mathbf{y}\geq 0 \textrm{ and } \mathbf{A}^T\mathbf{y}=0\}$$ is evidently a polyhedral cone (i.e., intersection of a finite number of half-spaces of the form $$f(\mathbf{y})\geq 0$$), and thus the set $$\{\mathbf{b} \textrm{ such that }\mathbf{b}^T\mathbf{y} \geq 0\ \textrm{for all such } \mathbf{y}\}$$ (which is the set $$K$$ in your notation) is the dual cone of this polyhedral cone. In particular it is itself a polyhedral cone.

But insofar as we can scale the $$\mathbf{b}$$ by elements of $$\mathbb{R}_{\geq0}$$, this set is never compact.

I believe this answers your question as best as it can be answered.

EDIT:

To address a comment, I remark that it is not actually possible for the set $$K$$ to be empty or to consist only of $$\{0\}$$ (unless $$n=0$$). This is because it must contain at least $$\{(a_1,\ldots,a_n)\colon a_i\geq 0\}$$ in it, since for such $$a_i$$, the vector $$\mathbf{x}=(0,\ldots,0) \in \mathbb{R}^m$$ is a solution.

• You're right! I took the coward's way and now I'm paying the price. :-) I'll look at the literature to see which definition of noncompact polytopes is the right one to use and I'll re-ask the question. – James Propp Apr 26 '19 at 19:02
• If you put an additional constraint like $\sum a_i =1$, then you get the intersection of a polyhedral cone with an affine subspace, which will be a polytope. – Sam Hopkins Apr 26 '19 at 19:03
• A quicker (though ultimately equivalent) explanation for why $K$ can't be compact (unless it's $\varnothing$ or $\{0\}$) is that it's closed under multiplication by positive scalars (since you can also multiply the vectors $\mathbf x$ by scalars). – Andreas Blass Apr 26 '19 at 23:41
• I won’t have to re-ask the question after all. Sam’s comments have answered the question I meant to ask. – James Propp Apr 28 '19 at 12:13