Let $P$ be a polyhedron in $[0,1]^n$ defined by the constraints $Ax \leq b$ for $A \in \mathbb{R}^{m \times n}$, $x \in \mathbb{R}^n$, and $b \in \mathbb{R}^m$.

In the solutions of an exercise, the following is mentioned:

"Since the first $n$ constraints are linearly independent, they correspond to a basic solution of the system which, a priori, may be feasible or infeasible. This solution is obtained by replacing inequalities with equalities and computing the unique solution of this linear system."

So I am quite confused about this:

1) Why does "linear independent constraints" imply that "basic solution"?

2) Is a basic solution not always feasible?

I am thankful for any answer!


1) Linearly independant constraints define linearly independant hyperplanes at equality ($Ax=b$ for the lines concerned), the intersection of which is a point (or a vector, depending on your way of looking at this).

2) You have no guarantee that this point will satisfy all the other constraints.

  • $\begingroup$ Great! Thanks a lot! $\endgroup$ – user136457 Mar 16 '17 at 14:10

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.