Duality Gap | Duality Gap |
|
"Duality is a powerful and widely employed tool in applied mathematics for a number of reasons. First, the dual program is always convex even if the primal is not. Second, the number of variables in the dual is equal to the number of constraints in the primal which is often less than the number of variables in the primal program. Third, the maximum value achieved by the dual problem is often equal to the minimum of the primal."
Essentially, duality theory concerns representation of a given optimization problem as half a minimax problem. Given any real function f(x,z) minimize_x maximize_z f (x,z) >= maximize_z minimize_x f (x,z) always holds. When minimize_x maximize_z f (x,z) = maximize_z minimize_x f (x,z) we have strong duality and then a saddle value exists, as depicted, and the duality gap is 0 (g(z) kisses f(x)). |
