Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Say we are given a linear program where the goal is to minimize $c^Tx$ with the constraints $Ax\ge b$. Why is there a sign restriction on the Lagrange multiplier associated with the active constraints at the solution?

share|cite|improve this question
up vote 3 down vote accepted

The sign restriction corresponds to the fact that the constraints are inequalities. The Lagrange multipliers are coefficients for expressing the gradient of the objective as a linear combination of the gradients of the active constraints. Since the constraints are inequalities, they allow you to move away from the solution in certain directions, but if the solution is optimal, doing so will cause the objective to decrease (or at least not increase).

share|cite|improve this answer
I have an idea of what you mean. Could you define gradient? – mathjacks May 14 '12 at 18:54
The gradient of $f(x_1,x_2,\ldots, x_n)$ is the vector $(\dfrac{\partial f}{\partial x_1}, \ldots, \dfrac{\partial f}{\partial x_n})$. – Robert Israel May 14 '12 at 19:10

The sign is here to ensure that the dual problem gives a lower bound to the primal problem. in your case, which describes a linear problem, strong duality implies that this lower bound corresponds to an optimal point for the primal problem (no duality gap). You can see this detailed in p.215 for example.

share|cite|improve this answer
I can't comment the Robert Israel answer directly, but the gradient of the cost function would be $c^T$, and the gradient of the individual constraints would be the rows of $A$. – vkubicki May 14 '12 at 19:06

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.