Maximin without the min

Experience has shown that many scholars/analysts who are not at home with the modeling aspects of the maximin paradigm are surprised to learn that true-blue maximin models such as this

\displaystyle z^{*}:= \max_{y\in Y}\min_{u\in \Pi(y)}\ \{g(y,u): C(y,u),\forall u\in \Pi(y)\}

can have an equivalent phrasing, without the iconic inner \displaystyle \min_{u\in \Pi(y)} operation. Here C(y,u) represents a list of constraints on (y,u) pairs.

The following result, that is used widely in game theory and robust optimization, explains how to dispose of this iconic operation:

\textsc{Theorem}.

\displaystyle \min_{a\in A} h(a) \equiv \max_{\substack{a\in A\\ v\in \mathbb{R}}} \{v: v\le h(a)\}

assuming that the \min is attained on A, where \mathbb{R} denotes the real line.

The \equiv sign indicates that the two optimization problems are equivalent in the sense that they yield the same optimal value for the objective functions and the same optimal value(s) for the decision variable a. The optimal value of v is equal to the optimal value of h(a).

The following is then an immediate implication of the theorem:

\textsc{Corollary}.

\begin{array}{rcl}      \displaystyle z^{*} &  \displaystyle := &  \displaystyle \max_{y\in Y}\min_{u\in \Pi(y)}\ \{g(y,u): C(y,u),\forall u\in \Pi(y)\}\\    & \displaystyle  \equiv & \displaystyle \max_{\substack{y\in Y\\ v\in \mathbb{R}}}\ \{v: v\le g(y,u), C(y,u),\forall u\in \Pi(y)\}\\        & \displaystyle \equiv & \displaystyle \max_{\substack{y\in Y\\ v\in \mathbb{R}}}\ \{v: CC(y,v,u),\forall u\in \Pi(y)\} \end{array}

where CC(y,v,u) consists of all the constraints in C(y,u), as well as the additional constraint v\le g(y,u).

Such formulations of maximin models are often called Mathematical Programming (MP) formulations. If you use maximin models often, you would do well to develop the skills to switch easily from the iconic formulations to the MP formulations and back.

More …

Advertisements

Your comment:

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s