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.
using Lagrange Multipliers
is given by
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 (Minimax Inequality)
For any sets
and any function
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