[線性規劃] Minimax Problem in LP format

考慮如下 minimax (non-cooperative game)問題：

\[\begin{array}{l}
\mathop {\min }\limits_x \mathop {\max }\limits_{i = 1,...,N} c_i^Tx\\
s.t.\\
Ax \le b
\end{array}
\]注意到上式 $\displaystyle \mathop {\max }\limits_{i = 1,...,N} c_i^Tx$ 為 凸函數 (Convex function) WHY?。故可求解最佳解(min)時 其Local minimum = global minimum。

現在問題是上述的 minimax 問題該如何將其改寫成LP問題呢?

方法如下：

首先引入一個新的變數 $z$ 並考慮如下 新的 LP問題：
\[\begin{array}{l}
\mathop {\min }\limits_{x,z} z\\
s.t.\\
\left\{ \begin{array}{l}
Ax \le b\\
c_i^Tx \le z,\begin{array}{*{20}{c}}
{}
\end{array}\forall i = 1,...,N
\end{array} \right.
\end{array}
\] 則現在此LP問題求解 等價 求解原本的minimax問題。亦即兩者間最佳解相同。

Proof：omitted


那麼如果現在問題變成 min min problem (cooperative game)
\[\begin{array}{l}
\mathop {\min }\limits_x \mathop {\min }\limits_{i = 1,...,N} c_i^Tx\\
s.t.\\
Ax \le b
\end{array}
\]該如何處理呢?

注意到上述的引入新變數 $z$ 的方法在此會失敗。因為此時 $\displaystyle \mathop {\min }\limits_x \mathop {\min }\limits_{i = 1,...,N} c_i^Tx$ 不再是 凸函數 (convex function)，(亦即convexity 無法保證)。求解最佳解(min)的會有問題 (如果其為 凹函數 (concave function)，則最佳解(minimum)不一定存在!)。

一般而言處理mini min problem的問題是將原本問題改寫成求解 $N$ 組 LP問題：
\[\begin{array}{*{20}{l}}
{\mathop {\min }\limits_{i = 1,...,N} \mathop {\min }\limits_x c_i^Tx}\\
{s.t.}\\
{Ax \le b}
\end{array}
\]亦即左右minimum 對調。(Proof: omitted)