1
$\begingroup$

Recently I have a conjecture on decomposing a linear program into smaller ones. I have tested it in Mathmatica by a lot of examples. However, I cannot prove it. I will appreciate if someone can give some ideas.

Let $f_1,\dotsc,f_r \in \mathbb{R}[x_1,...,x_n]$ ($r>n+1$) be linear functions. Then $\{f_i \ge 0|\ 1 \le i \le r \}$ has a solution if and only if $\{f_i \ge 0|\ 1 \le i \le r, i \ne j\}$ has a solution for each $j=1,\dotsc,r$.

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ When $n=2,r=3$, it is easy to write three half-planes who have no intersection, but every two of them have non-empty intersection. $\endgroup$
    – Cooler Panda
    Commented Mar 1, 2018 at 8:49
  • $\begingroup$ You r = n + 1, so the gray box statement is not contradicted. $\endgroup$
    – Mark L. Stone
    Commented Mar 4, 2018 at 3:43

1 Answer 1

Reset to default
5
$\begingroup$

The statement in the gray box is an immediate consequence of Helly's theorem: for each $i$, the set $\{ v\in\mathbb{R}^n\colon\ f_i(v)\geq 0\}$ is convex, and because of $r>n+1$, the condition given on the right-hand side of the equivalence implies that the intersection of any $n+1$ of these sets is inhabited, hence by Helly's theorem, the intersection of all the sets is inhabited too.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .