Geometry of Linear Programs

Convex Sets

A set of points is called a convex set if all the points on the straight line segment joining any two points in the set belong to the set.

Affine Sets

Affine sets: allows us to describe a set independently of system of coordinates

Note

line going through the origin defines a Subspace i.e. \(y = ax\)

line going through through \(y(0) = b\), or defined by \(y=ax+b\) defines an affine set

Affine sets let us define systems independent of the origin.

Note

Parallel Subspace To every set \(C\), we can associate a subspace \(V\) called a “parallel subspace”

The dimension of a parallel subspace can be defined by the affinely independent vectors of the subspace !add formal definition!

Every affine set can be expressed as the set of solutions of linear equations.

References

[1]	Dantzig, G. Bernard, Linear Programming and Extensions. RAND Report. August 1963. Chapter 7.