Why is curve of lagrangian dual problem always concave
Answers
because it wants to be like that.
Concavity of the dual function is very much a non-intuitive property.
One way to show it is to use the fact that a function is convex if and only if its epigraph is a convex set. The epigraph of a function f(x⃗ )f(x→) is the set of points 'above' that function:
{(x⃗ ,y)∣y≥f(x⃗ )}{(x→,y)∣y≥f(x→)}
For the dual function we have the pointwise infimum of a family of affine functions:
D(λ⃗ ,ν⃗ )=infx⃗ L(x⃗ ,λ⃗ ,ν⃗ )=infx⃗ A(x⃗ )[λ⃗ ν⃗ ]+b⃗ (x⃗ )D(λ→,ν→)=infx→L(x→,λ→,ν→)=infx→A(x→)[λ→ν→]+b→(x→)
That is, we can re-write the Lagrangian to have the form Aλ⃗ +b⃗ Aλ→+b→ for some matrix AA and vector b⃗ b→ that both depend on x⃗ x→.
Loosely speaking, pointwise means we can pick different values for x⃗ x→ depending on the value of λ⃗ λ→.
The epigraph of LL is for any given value of x⃗ x→ is going to be a convex set, as once x⃗ x→ is fixed the function is affine, and affine functions are both convex and concave. If we flip this notion, we can look at negative epigraphs, or the set of points 'below' the function. This negative epigraph of DD is going to be the intersection of the negative eopigraphs of all possible functions formed by fixing all possible values of x⃗ x→. The intersection of convex sets is a convex set, so this negative epigraph is a convex set. The negative epigraph of a function is a convex set if and only if the function is concave, so the dual function DD must be concave!
It helps a bit to draw this out on a sheet of paper. hope it will be the answer.