There are three things :
- Original problem (Primal problem)
- Dual function (Function of lagrange multiplier)
- Dual problem
Suppose p is the solution of primal problem and d the dual problem.
If original problem is minimization, we are interested in lower bound (d) such that d<p. We want to find maximum value of d and dual problem becomes maximization problem.
If original problem is maximization, we are interested in finding upper bound (d) such that p<d. We want to find minimum value of d and dual problem become minimization problem.
Dual problem is always convex irrespective of primal problem.
d<p is weak duality, while d=p is strong duality.
If primal problem is convex strong duality generally holds.
Slater’s condition is sufficient tests for convex optimization.
Further reading :
Kanpsack Problem here
Click to access classbfs121109082344836.pdf
Convex Optimization by Stephen Boyd
Data Stories 