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?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
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).
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.