Linear Programming

• A linear program (LP) is an optimization problem in which we optimize an objective function that is linear in the unknowns, subject to constraints in the form of linear equalities and inequalities.

  We write this in Matrix form as

  Where and and

  • The above is the standard form of an LP problem.

• A linear programming problem can be converted into an augmented form. This introduces slack variables which replaces inequalities with equalities in the constraints. In block form, The matrix can be expressed as

  Where , and . is the variable to be optimized. is the identity matrix

  • Intuition: A slack variable indicates how much we need to add, for each constraint, so that equality is achieved. That is, if , then if the constraint is of the form , we can remove the inequality by also solving for ,
  • If an inequality has a constraint of the form , we can introduce a surplus variable to transform it as
    Where .

• The constraints define a feasible region, which is convex. A feasible solution is a solution (i.e., value for ) in the feasible region. An LP is infeasible if no feasible solution exists.

• The Fundamental Theorem of Linear Programming states the following.

  Consider a linear program. Let be the feasible region. If is bounded, and is an optimal solution to the problem, is either a vertex of or lies on a face of optimal solutions.

  • It can also be stated as follows: the maxima and minima f a linear function over a convex polygonal feasible region must occur at the region’s corners.
  • If an extrema occurs at two corners, then it must also occur everywhere on the line segment between them
  • (Luenberger and Ye 2.4) Another way to interpret this is by considering a matrix from the augmented form of the LP. Assume . We can thus consider a submatrix which is invertible. A solution is basic if variables not associated with the columns of are set to . Then:
    • If there is a feasible solution, there is a basic feasible solution
    • If there is an optimal feasible solution, there is an optimal basic feasible solution
    • Solving a linear program can be done by searching over basic feasible solutions. There are at most such solutions.

Topics §

• Simplex Method
• Primal-Dual Scheme

Links §

• Linear and Nonlinear Programming by Luenberger and Ye
• Linear Algebra
• Convex Optimization