7
$\begingroup$

I have the following equational Linear Program: \begin{align}\max&\quad c^T x\\\text{s.t.}&\quad Ax=b\\&\quad x\ge0\end{align}

The matrix $A$ is $m\times n$, where $m\le n$, $c\in \mathbb{R}^n, x \in \mathbb{R}^n$ and $b\in\mathbb{R}^m$. Also the rank of $A$ is $m$.

Now I understand the following :

(1) The feasible region is a convex polytope formed by the intersection of hyperplanes (constraints).

(2) At least one of the vertices of the polytope will give us the optimal solution if it exists.

  • What I don't understand is why only at the corner points (basic feasible solutions) $(m)$ variables are not zero (basic) and rest $(n-m)$ variables are zero (non-basic)?

Also, let's say that we have a basic feasible solution $x_B$. Now for every $x>0 \,\,\,in\,\,\, x_B$, we build the $m \times m$ matrix $A_B$, the columns of which form linearly independent vectors. I understand that this fact allows us to calculate the inverse of $A_B$ and that is useful for calculating $x_B =A_B^{-1}b\,\,+A_B^{-1}A_Nx_N $ where $A_N$ is a $m\times(n-m)$ matrix of non-basic variables and $x_N$ is the set of non-basic variables.

  • But what is the geometric significance of linear independence that is why do the corner points show such behavior?
$\endgroup$
2
  • $\begingroup$ Is your first question asking why $n-m$ variables are zero at a corner point, or is it asking why $n-m$ variables are zero only at a corner point? $\endgroup$
    – prubin
    Apr 3, 2022 at 15:50
  • $\begingroup$ I want to know why at corner points (m) variables are non-zero and rest (n-m) are zero. So I think I mean the latter. I am under the assumption that such a behavior is only seen at corner points. Sorry for the confusion. $\endgroup$ Apr 3, 2022 at 16:04

1 Answer 1

5
$\begingroup$

Each equation constraint defines a hyperplane in $\mathbb{R}^n$, as does each lower bound ($x_i =0$). When hyperplanes intersect, the dimension of the intersection is $n$ minus the number of hyperplanes with linearly independent normal vectors. When $n=3$, the intersection of two independent planes is a line. If you intersect that with a third plane, you either get a point (if the planes have independent normals) or the same line (if the normal of the third hyperplane is a linear combination of the first two normals).

So at a corner point there are $n$ binding constraints with independent normals. Note that you have $m+n$ constraints total, not $m$, thanks to the sign restriction $x\ge 0.$ You know the equations are all binding because they are equations, which means $n-m$ of the sign restrictions are binding. So at least $n-m$ variables are 0 at the corner. The number of zeroes could actually be higher, as one or more basic variables could be zero.

The geometric significance of linear independence is that adding another hyperplane to the intersection only drops the dimension of the intersection by 1 if the normal of the new hyperplane is independent of the normals of the hyperplanes already participating in the intersection.

$\endgroup$
2
  • 1
    $\begingroup$ Just so I understand this clearly, effectively what you are saying is that any corner point of a polytope is just the intersection of $n$ hyperplanes in $\mathbb{R}^n$ which have linearly independent normal vectors. The corresponding constraints to these hyperplanes are always binding. $\endgroup$ Apr 3, 2022 at 18:39
  • 2
    $\begingroup$ Correct, with one qualification. There may be more than $n$ hyperplanes intersecting at the corner, $n$ of which will have independent normals. When there are extra hyperplanes (extra binding constraints) the corner is termed "degenerate". $\endgroup$
    – prubin
    Apr 3, 2022 at 19:08

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.