1
$\begingroup$

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?

2 Answers 2

3

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).

  • 0
    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})$.2012-05-14
0

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.

  • 0
    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$.2012-05-14