0
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ The Lagrange multipliers method is made to find the stationary points, it doesn't help to deal with the extremal points on the boundary. $\endgroup$ – Yves Daoust Jun 24 at 18:28
  • $\begingroup$ Refer to Gilbert Strang $introduction\ to\ applied\ mathematics$. It gives some brilliant answers! $\endgroup$ – Book Book Book Jun 25 at 19:14
2
$\begingroup$

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.

$\endgroup$

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.