Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
add comment

2 Answers

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|improve this answer
    
I have an idea of what you mean. Could you define gradient? –  flapjackery 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
add comment

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 http://www.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf p.215 for example.

share|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
add comment

Your Answer

 
discard

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.