Primal and Dual problem





     


Lagrangian


     



Dual function


     


What  is a family of affine functions? Why does this make it con‐
cave?



Lower bounds property


     


The dual function yields lower bounds on the optimal value p*  of
the primal problem.










Curled inequality symbol:














                               ‐2‐


State the dual problem


     


Verify it is a concave maximization problem


     






Dual optimal value and dual optimal solution


     




Strong duality



     



Supremum and Infimum



     


Why isn’t the dual optimal value achieved at λ=0?

Although  λ  can’t  take  0,  but why being infinitely close to 0
doesn’t lead us to the dual optimal solution?

infimum is like integration, it marginalizes out one variable.

Intermediate step: g(λ) = inf L(λ,x)

Final step: maximize g(λ), λ > 0














                               ‐3‐


     Affine set and convex set