1
$\begingroup$

As part of a review of some famous proofs in Hypergraphs matching I ran into this lemma in Linear programming that I am having difficulty showing (or finding an existing proof online):

Let $P=\{\vec{x}\mid A\vec{x}\leq\vec{b}\}$ be the feasible solutions polyhedron. Let $\vec{x}_0\in P$ be a vertex of $P$. Denote $$I = \{ i \in [n] \mid \vec{a}_i\vec{x}_0= b_i \}$$ ($\vec{a}_i$ and $b_i$ are $A$'s and $\vec{b}$'s $i$-th rows accordingly). That is, $I$ is the set of indices of constraints (rows) that $\overrightarrow{x_0}$ exhuasts.

Let $\vec{c}$ be some vector. Then $\vec{x}_0$ maximizes $\vec{c}\vec{x}$ $\iff$ there exists non-negative $\alpha_i$ such that $\vec{c}=\sum_{i \in I}{\alpha_i a_i}$.

Clearly the direction $\impliedby$ is trivial. It's the other direction that's interesting.

$\endgroup$
1
$\begingroup$

I'll prove the nontrivial implication by proviing the contrapositive. Suppose $\vec c$ is not a linear combination of the $\vec a_i$'s for $i\in I$ with non-negative coefficients. By Farkas's Lemma, there is a vector $\vec z$ that has a positive inner product with $\vec c$ but non-positive inner products with the $\vec a_i$ for $i\in I$. Consider the vector $\vec y=\vec x_0+\varepsilon\vec z$ for some small, positive $\varepsilon$.

I claim that $\vec y\in P$ when $\varepsilon$ is sufficiently small. That means I need to check the inequalities $\vec a_i\vec y\leq b_i$ for all $i$, and this amounts to $$ (\vec a_i\vec x_0)+\varepsilon(\vec a_i\vec z)\leq b_i. $$ For $i\in I$, the first of the two inner products here equals $b_i$ (by definition of $I$) and the second is non-positive (by choice of $\vec z$ and positivity of $\varepsilon$), so the inequality holds. For $i\notin I$, the first inner product is $<b_i$, so the desired inequality will hold provided we pick $\varepsilon$ small enough. This completes the verification that, by a suitable choice of $\varepsilon>0$, we can get $\vec y\in P$.

But $\vec c\vec y=(\vec c\vec x_0)+\varepsilon(\vec c\vec z)>(\vec c\vec x_0)$, by our choice of $\vec z$. So $\vec x_0$ doesn't maximize $\vec c\vec x$ over all $\vec x\in P$.

$\endgroup$
  • $\begingroup$ Nice. I managed to prove it without Franka's Lemma, using similar ideas. $\endgroup$ – eladidan Jun 21 '13 at 13:17

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.