Trying to Implement Lagrangian Duality

Metronome

Junior Member
Joined
Jun 12, 2018
Messages
157
I am trying to implement Lagrangian Duality, but seem to be getting a negative duality gap.

I don't need to solve this program in particular. I just wanted to start with something more interesting than an LP.

Hopefully I have made the variable names/output/comments clear enough for non-Mathematica users to see the point; first I solve the primal program and get a minimum objective value of [imath]5[/imath], then compute the Lagrangian, then from that the Lagrange Dual Function, then from that the Lagrangian Dual Program, then solve that and get a maximum objective value of [imath]180[/imath], which does not make sense in light of weak duality, and furthermore, since the primal program is convex and straightforward, I would expect strong duality to likely hold so that the primal program and the dual program objective values should match. What am I doing wrong?

En7MKS1.png

I have also tried to pinpoint the problem through paper computation.

One thing I'm not sure about conceptually is what to make of the system of equations obtained by letting the Gradient of the Lagrangian vanish. The only primal decision variable which appears in that system is [imath]x_1[/imath]; [imath]x_2[/imath] and [imath]x_3[/imath] are lost to the Gradient operation, and the Lagrangain does not explicitly remember the constraints from the primal program, so I am not sure what to substitute into the Lagrangian to eliminate [imath]x_2[/imath] and [imath]x_3[/imath] in order to construct the Lagrange Dual Function.

The other two equations in that system are [imath]\lambda_1 = 2 + \lambda_2 + 2\lambda_3 - 4\nu_2[/imath] and [imath]\nu_1 = 1[/imath], which are treated as part of the domain in Mathematica's output Lagrange Dual Function. Not shown above, I have also tried parsing out the "main" (the noninfinite) value of the Lagrange Dual Function [imath]\frac{1}{4}(15 + ...[/imath] and using just that expression as the dual objective, and the [imath]\lambda_1 = 2 + \lambda_2 + 2\lambda_3 - 4\nu_2[/imath] and [imath]\nu_1 = 1[/imath] as additional dual constraints. The objective value output in that case is still [imath]180[/imath].
 
Top