Finding dual optimum of a linear problem

[Trollfaz]

A simple linear problem goes
min c'x such that f_i(x)<= 0 and Ax=b
x
Suppose we make all constraints affine. Then

Dx-e<=0 and Ax-b =0
We get the Langrangian function as
c'x + λ'(Dx-e) +ν'(Ax-b) and since Ax-b is 0,
we reduce L to
c'x + λ'(Dx-e)
The dual function g is
inf L(x,λ)
x
Then I differentiate L against x to get c=-D'λ
With that we get g(λ) as -λ.e
So I conclude that d*=sup g(λ) against λ.
Does differentiation of the Lagrangian function give me the dual optimum and does it work for all convex inequality constraints and convex objective functions?

 

[Mathfor]

Hi! You are touching on some fundamental concepts of Duality in Linear Programming, but there's a critical flaw in how you are handling the constraints in the Lagrangian. When you construct the Lagrangian function L(x, lambda, nu), you cannot assume Ax - b = 0 and remove it. The entire purpose of the Lagrangian relaxation is to drop the constraints from the physical problem and bring them into the objective function as penalties (using the multipliers lambda and nu). When you evaluate the dual function g(lambda, nu) = inf_x L(x, lambda, nu), the variable x becomes completely unconstrained. If you force Ax = b at this stage, you are not building the unconstrained dual; you are just staying inside the primal feasible region.

Differentiating L with respect to x and setting it to zero does not give you the dual optimum. Because L is affine (linear) with respect to x, its infimum is -infinity unless its slope (the derivative) is exactly zero.Therefore, setting nabla_x L = c + D^T lambda + A^T nu = 0 generates the constraints of your dual problem. It simply ensures the dual function is bounded. To find the actual dual optimum d*, you still have to maximize that resulting function g(lambda, nu).

In practice, finding these dual optimums isn't done through manual differentiation, but through algorithms like the Simplex Method. A beautiful property of linear programming is strong duality: when you solve the primal problem using Simplex, the optimal values of your dual variables (often called shadow prices) automatically emerge in the objective function row (Z) of your optimal tableau. If you want to se how it works just search simplex solver in yout browser and you will find some articles which may help you. Personally, I like [URL redacted by the Mentors] because its free and easy to use. You can run a Primal problem through the Simplex Method module and see exactly where and how these theoretical dual variables appear in the final tableau iteration.

Hope this helps!