Duality
Last updated
Last updated
The primal problem is essentially the standard form of optimization. There are no assumptions of convexity on any of the functions involved. We can would like to express primal problems as a min-max optimization with no constraints.
The Lagrangian achieves the goal of removing the constraints in the min-max optimization
This is true because if any inequality constraints are violated, then , and the maximization could set very large to make the overall problem , and if any equality constraints are violated, then , and the maximization would set to a very large number of the same sign as to make the overall problem . Thus the minimax problem is equivalent to the original problem. At this point, it might be easier to solve the problem if the order of min and max were switched.
Theorem 22 can be interpreted as a game where there is a minimizing player and a maximizing player. If the maximizer goes first, it will always produce a higher score than if the minimizer goes first (unless they are equal). We can now apply Theorem 22 to switch the and in our optimization with the Lagrangian.
What weak duality does is convert our minimization problem to a maximization problem.
It removes constraints, potentially making the problem easier to solve.
It can turn a non-convex problems into a convex one.
Even when there are no constraints, we can sometimes introduce constraints to leverage duality by adding slack variables that are equal to expressions in the objective.
In some cases, duality gives not just a lower bound, but an exact value. When this happens, we have Strong Duality.
If we focus on convex problems, then we can find conditions which indicate strong duality holds.
Note that is a concave function because it is the pointwise minimum of functions that are affine in and . A maximization of a concave function over a convex set is a convex problem, so the dual problem (minimizing ) is convex. Thus duality achieves two primary purposes.
Let be convex, and be bounded and closed (compact). Let be a function such that is convex and continuous, and is concave and continuous, then
Once we find a solution to the dual problem, then the solution to the primal problem is recovered by minimized where are the optimal dual variables, and if no such feasible point exists, then the primal itself is infeasible. When searching for strong duality and an optimal solution , it can be useful to consider particular conditions.
For a convex primal problem which is feasible and has a feasible dual where strong duality holds, a primal dual pair is optimal if and only if the KKT conditions are satisfied.
Primal Feasibility satisfies and .
Dual Feasibility .
Complementary Slackness
The complementary slackness requirement essentially says that if a primal constraint is slack (, then , and if , then .