Minimax Inequality

Weak Duality > Dual problem | Geometry | Minimax Inequality

Primal problem as a minimax problem

The Lagrange function allows to rewrite the problem in an unconstrained fashion, as follows.

Right angle property: For any fixed $f in mathbf{R}^m$ ,

$max_{y ge 0} y^Tf = left{ begin{array}{ll} 0 & mbox{if } f le 0 +infty & mbox{otherwise.} end{array} right.$

That is, for any pair of vectors $f,-y in mathbf{R}^n_+$ , the angle between and is always less or equal than 90^o . This comes from the fact that the non-negative orthant $mathbf{R}^n_+$ is a convex cone with a right angle at the origin.

Thus, for fixed , applying the above to f = f(x):= (f_1(x),ldots,f_m(x)) :

$max_{y ge 0} y^Tf(x) = left{ begin{array}{ll} 0 & mbox{if } f le 0 +infty & mbox{otherwise.} end{array} right.$

The above function (of ) acts like a barrier for the feasible set of the primal problem: it is whenever is feasible, and +infty outside the feasible set. Thus:

$p^ast = min_x : max_{y ge 0} : L(x,y).$

Minimax inequality

The minimax inequality states that for any function of two vector variables $L : mathbf{R}^n times mathbf{R}^m rightarrow mathbf{R}$ , and two subsets $mathbf{X} subseteq mathbf{R}^n$ , $mathbf{Y} subseteq mathbf{R}^m$ , we have

$min_{x in mathbf{X}} : max_{y in mathbf{Y}} : L(x,y) : ge max_{y in mathbf{Y}} : min_{x in mathbf{X}} : L(x,y).$

The proof is very simple.

Applying this result to the expression of p^ast as a minimax, we obtain

$d^ast ge max_{y ge 0} : min_x : L(x,y) = max_{y ge 0} : g(y),$

where is the dual function.

Interpretation as a game

We can interpret the minimax inequality in the context of a game, with primal and dual variables acting as adversaries.

Consider a game with two players and : decides over the primal variables, and seeks to minimize the ‘‘cost’’ L(x,y) ; player plays the dual variables , subject to the constraint y ge 0 , and seeks to maximize the ‘‘payoff’’ L(x,y) . We assume that one of the players goes first, the game is played only once, and both players have full information on the other's choice, once their decision is made.

If plays first, it is at a disadvantage: it does not know the decision of in advance, and must prepare for the worst outcome. In constrast, can adapt to whatever the decision of is, and make a better choice than if it could not adapt. Therefore, we expect the cost (to ) to be higher in the case when plays first than if it plays second.

Let us assume plays first, and chooses the decision vector . Since that decision is known to once it is made, the optimal strategy for is to set to be optimal for the optimization problem (here is fixed)

$max_{y ge 0} : L(x,y) .$

The best choice for , knowing that will adapt this way to any of its decisions , is to set to be such that the above payoff (to ) is the smallest. That is, the best decision for (when it plays first) is to set to solve the problem

$p^ast = min_x : max_{y ge 0} : L(x,y).$

The above represent the minimum cost that is going to pay in the worst-case, that is, in the case when plays optimally as a second player.

Now assume that plays second. This time, it is who adapts to the decision of . For any given such decision , the best decision (for ) is to solve

This is nothing else than the dual function. That is, the dual function tells us the optimal strategy (for ) as a function of the dual variable .

The best choice for , knowing that will adapt this way to any of its decisions , is to set to be such that the above cost (to ) is the largest. That is, the best decision for (when it plays first) is to set to solve the problem

$d^ast = max_{y ge 0} : min_x : L(x,y).$

The minimax inequality simply states that indeed is at a disadvantage if it plays first.