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

$\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$ Mar 1, 2018 at 8:49
  • $\begingroup$ You r = n + 1, so the gray box statement is not contradicted. $\endgroup$ Mar 4, 2018 at 3:43

1 Answer 1

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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