(Ref. page 9 of the following notes)

The problem is to prove that if $U \in \mathbb{R}^n$ is the feasible region of a linear program, then $x \in U$ is a basic feasible solution iff it's a vertex. Initial steps in the proof:

Suppose $x$ is a basic feasible solution and also that $x$ is a convex combination of $y$ and $z$, both in $U$. Let $C$ be a matrix whose rows are $n$ linearly independent active constraints at $x$, and $c$ be the vector of corresponding constraint values. Because $C$ has linearly independent rows, it has full rank and is invertible. Also $Cy \leq c, Cz \leq c$ and $Cx = c$ ...

$Cx = c$ is obviously correct by definition, but why are the other two inequalities valid: $Cy \leq c, Cz \leq c$ ? How is $C$ related in any way to $U$? If the feasible region is characterized by a polyhedron $\mathcal{P} = \{x \in \mathbb{R}^n\ |\ Ax \leq b\}$, then it's understandable to say that $Ay \leq b, Az \leq b$, since $y,z \in U$.

$C$ is solely defined as the matrix of linearly independent constraints active at $x$ and I don't see why it has anything to do with the feasible region.

  • $\begingroup$ Since $y$ is in the feasible region, $Ay \leq b$. Then the inequality $Cy \leq c$ follows since $C$ and $c$ are defined by just selecting a subset of the rows from $A$ and $b$. $\endgroup$ – Joppy Mar 27 '18 at 13:07
  • $\begingroup$ @Joppy: But by definition, $C$ necessarily has $n$ independent rows. And $A$ might have $m \leq n$ rows (in case there are $m \leq n$ constraints). Or probably I'm misunderstanding. $\endgroup$ – Shirish Kulhari Mar 27 '18 at 13:16
  • 1
    $\begingroup$ It shouldn't matter whether the rows are independent or not, the fact is that you're just selecting a subset of the rows out of the inequality $Ay \leq b$. Also note that if $x$ is a basic feasible solution, then by definition of basic there are $n$ independent constraints which are tight at $x$, and so the matrix $A$ must have at least $n$ rows. $\endgroup$ – Joppy Mar 27 '18 at 13:24
  • $\begingroup$ @Joppy: In other words, if there are $m < n$ constraints on the linear program, i.e. $m$ rows in $A$, no basic feasible solution exists? $\endgroup$ – Shirish Kulhari Mar 27 '18 at 13:29
  • $\begingroup$ Think about the space $\mathbb{R^3}$, and impose two linear constraints. There are no vertices of this polytope. $\endgroup$ – Joppy Mar 27 '18 at 13:32

Let $I := \lbrace i \vert A_{i \cdot} x = b_i \rbrace$ be the set of indices corresponding to the active constraints at $x$. Then $C$ is can be defined by $C := A_{I \cdot}$ and $c = b_I$ . Since $y$ is feasible we have $Cy = A_{I \cdot}y \leq b_I = c$ and similarly for $z$.

In your case the rows should be linearly independent and this is done by selecting an appropriate subset of $I$. In any case the constraints in $C$ are chosen from the constraints in $A$ and the above still holds.


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.