I am trying to understand the Simplex Algorithm from a gradient perspective, and I am wondering if anyone knows of a method for determining the variables that should both enter and leave the basis of the Simplex Algorithm by using Lagrange multipliers?
That is, given an objective function and a set of linear constraints that form a convex polytope, how could one go about using the Lagrange multipliers at the current point (vertex of the polytope) to determine the direction (or constraint) to move toward during the next iteration?
Best Answer
First, you have to move from Lagrange multipliers (which assume equality constraints), to Karush-Kuhn-Tucker multipliers (which accommodate inequality constraints). The KKT multipliers are also known as dual variables or "shadow prices".
The reduced costs in the simplex method are the original costs minus the constraint coefficients after weighting the constraint coefficients by the corresponding KKT multipliers. So this is the natural extension of Lagrangian relaxation. Nonbinding constraints will have zero multipliers. The reduced cost of a nonbasic variable is the (instantaneous) rate of change of the objective if you increase the nonbasic variable from zero (and adjust the basic variables to balance the constraints).
Assuming a problem with nonnegative variables, every variable can be viewed as a slack for some constraint. (The original variables are slacks for the nonnegativity constraints.) A nonbasic variable corresponds to a binding constraint at the current solution. Increasing such a variable makes the constraint nonbinding. So if you picture a nondegenerate corner point (intersection of a bunch of hyperplanes for binding constraints) and make one constraint nonbinding (by moving off its hyperplane), you now find yourself moving along an edge. The reduced cost of the variable entering the basis represents the inner product of the objective coefficient vector (gradient of the objective function) onto that edge.