A Finding dual optimum of a linear problem

  • A
  • Thread starter Thread starter Trollfaz
  • Start date Start date
  • Tags Tags
    Linear programming
AI Thread Summary
The discussion focuses on finding the dual optimum of a linear problem defined by affine constraints. The Lagrangian function is derived as c'x + λ'(Dx-e) when constraints are transformed. By differentiating the Lagrangian with respect to x, it is established that c = -D'λ. The dual function g(λ) is then expressed as -λ.e, leading to the conclusion that d* equals the supremum of g(λ). The query raised is whether this differentiation method yields the dual optimum for all convex inequality constraints and convex objective functions.
Trollfaz
Messages
143
Reaction score
14
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?
 
Seemingly by some mathematical coincidence, a hexagon of sides 2,2,7,7, 11, and 11 can be inscribed in a circle of radius 7. The other day I saw a math problem on line, which they said came from a Polish Olympiad, where you compute the length x of the 3rd side which is the same as the radius, so that the sides of length 2,x, and 11 are inscribed on the arc of a semi-circle. The law of cosines applied twice gives the answer for x of exactly 7, but the arithmetic is so complex that the...
Is it possible to arrange six pencils such that each one touches the other five? If so, how? This is an adaption of a Martin Gardner puzzle only I changed it from cigarettes to pencils and left out the clues because PF folks don’t need clues. From the book “My Best Mathematical and Logic Puzzles”. Dover, 1994.
Back
Top