1
$\begingroup$

Can someone give a simple explanation as to why the feasible region of a set of linear program/equations is affine?

$\endgroup$

1 Answer 1

1
$\begingroup$

You can transform the feasible set of any LP into the form $Ax = b$. The solutions of this equation can be written as $x = A^{\dagger} b + y$ where $y$ solves $Ay = 0$ (i.e. $y$ is from a subspace) and $A^\dagger$ is the pseudoinverse of $A$. Thus the feasible set is given by $$S = A^\dagger b + \ker A$$ wich is obviously affine.

$\endgroup$
4
  • $\begingroup$ i am sorry, since i am new to this area, why is the last feasible set affine? or why is S affine? $\endgroup$ Aug 22, 2014 at 8:22
  • $\begingroup$ The kernel of a linear mapping ($x\mapsto Ax$) is a subspace. An affine space is a translated subspace, i.e. of the form $x = c + y$ where $c$ is a vector and $y$ is from an arbitrary subspace. $\endgroup$
    – AlexR
    Aug 22, 2014 at 11:12
  • $\begingroup$ one last question i had, I understand your argument for A,b being a matrix and row vector. What if we had a hyperplane of the form $a_i^Tx <=b$? I believe that this should also define an affine subspace, but using the same argument i cant multiply by any pseudoinverse right? So whats the argument there? $\endgroup$ Aug 22, 2014 at 12:35
  • $\begingroup$ Here you have a form of $Ax \le b$ wich can be converted to $(A\quad I) \begin{pmatrix}x\\s\end{pmatrix} = b, s_i \ge 0$ This is an intersection of an affine subspace with a half-space ($s\ge 0$) and thus is a polytope (not necessarily an affine subspace) $\endgroup$
    – AlexR
    Aug 22, 2014 at 12:39

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .