A question about polytopes related to linear programming

Question

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.

Answer 1

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.