3
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – James Propp Apr 26 '19 at 19:02
  • 2
    $\begingroup$ 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. $\endgroup$ – Sam Hopkins Apr 26 '19 at 19:03
  • 3
    $\begingroup$ 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). $\endgroup$ – Andreas Blass Apr 26 '19 at 23:41
  • $\begingroup$ I won’t have to re-ask the question after all. Sam’s comments have answered the question I meant to ask. $\endgroup$ – James Propp Apr 28 '19 at 12:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.