[最佳化] 淺談線性規劃(2)- Optimality Theorem & Fundamental Theorem of LP

延續上篇，我們知道了標準型式的Linear Programming 問題若存在feasible solution，則必定存在一個 basic + feasible solution，但我們完全沒有提及到底如何最佳化(在此我們以最小化為主；亦即目標是要盡可能降低cost function的值)，

也就是在從一個feasible solution移動到下一個basic + feasible solution之後，cost function的值是如何被降低的。這次要介紹的是 Optimality Theorem

=========================

Theorem: Optimality Theorem

對具有標準形式的Linear Programming問題，若其存在一個optimal + feasible solution $x^*$，則必定存在一個optimal basic + feasible solution $\tilde x^*$。
=========================

Proof:
考慮下列兩種情況：
1. $x^*$  為 Basic solution
2. $x^*$  不為 Basic solution

對情況1而言 (trivially true)：
假設 $x^*$ 為Basic solution，則由假設我們又知道 $x^*$ 為 optimal + feasible solution；故在此情況下 $x^*$ 為 optimal basic + feasible solution 。

對情況2而言
假設 $x^*$  不為Basic solution，則由Basic Solution 定義可知
-----
一個向量 $x \in \mathbb{R}^n$ 稱作對 $Ax=b$ 的 Basic Solution ，若 $x$中 nonzero components 對應到$A$矩陣的線性獨立 Columns。
-----

故若  $x^*$  不為Basic solution，則表示  $x^*$  中的nonzero components 對應到$A$矩陣 Columns為線性相關 ；故我們進一步改寫此結果：

令   $x_1^*, x_2^*, ..., x_m^*$ 為  $x^*$中 nonzero components；其對應到 $A$ 矩陣Columns:
$a^1, a^2, ..., a^m$ 為線性相關；故由線性相關定義可知必定存在一組 非零純量 $y_i$ 使得
\[
\sum_{i=1}^{m} y_i a^i =0
\]

現在我們定義 $\eta^\varepsilon$ 如下
\[
{\eta _i^\varepsilon  }: = \left\{ \begin{array}{l}
x_i^*  - \varepsilon {y_i}, \ \ i \le m\\
0, \ \ \ \ i > m
\end{array} \right.
\] 則

\[\begin{array}{l}
A{\eta ^\varepsilon } = \left[ {\begin{array}{*{20}{c}}
{{a^1}}&{{a^2}}& \cdots &{{a^m}}&{{a^{m + 1}}}& \cdots &{{a^n}}
\end{array}} \right]\left[ {\begin{array}{*{20}{c}}
{x_1^* - \varepsilon {y_1}}\\
{x_2^* - \varepsilon {y_2}}\\
 \vdots \\
{x_m^* - \varepsilon {y_m}}\\
0\\
 \vdots \\
0
\end{array}} \right]\\
 \Rightarrow A{\eta ^\varepsilon } = {a^1}\left( {x_1^* - \varepsilon {y_1}} \right) +  \cdots  + {a^m}\left( {x_m^* - \varepsilon {y_m}} \right)\\
 \Rightarrow A{\eta ^\varepsilon } = \left( {{a^1}x_1^* +  \cdots  + {a^m}x_m^*} \right) - \left( {\varepsilon {a^1}{y_1} +  \cdots  + \varepsilon {a^m}{y_m}} \right)\\
 \Rightarrow A{\eta ^\varepsilon } = \left( {{a^1}x_1^* +  \cdots  + {a^m}x_m^*} \right) - \underbrace {\varepsilon \sum\limits_{i = 1}^m {{a^i}{y_i}} }_{ = 0}\\
 \Rightarrow A{\eta ^\varepsilon } = \underbrace {\left[ {\begin{array}{*{20}{c}}
{{a^1}}&{{a^2}}& \cdots &{{a^m}}
\end{array}} \right]\left[ {\begin{array}{*{20}{c}}
{x_1^*}\\
{x_2^*}\\
 \vdots \\
{x_m^*}
\end{array}} \right]}_{ = b}
\end{array}\]亦即，
\[
A \eta^{\varepsilon} = b
\]因此，如果 $|\varepsilon|$ 足夠小的時候，$\eta^\varepsilon$ 為 feasible solution；故我們說 $|\varepsilon| < \delta$；現在我們回頭檢查 對於Cost function $J = c^T x$ 有甚麼影響 :
\[
c^T \eta^\varepsilon = c^T (x^* - \varepsilon y)= c^T x^* - \varepsilon \cdot c^T y \ \ \ \ (*)
\] 且對 $i>m$的時候， $y_i =0$

觀察上式 $(*)$：可知如果我們有 $ \varepsilon \cdot c^T y >0 $ 則 Cost 就可以被我們降低。故定義 $\varepsilon := \delta \cdot \text{sign}(c^T y)$；則對此$\varepsilon$而言，
\[\begin{array}{l}
{c^T}{\eta ^\varepsilon } = {c^T}{x^*} - \varepsilon  \cdot {c^T}y\;\\
 \Rightarrow {c^T}{\eta ^\varepsilon } = {c^T}{x^*} - \delta \cdot \text{sign}\left( {{c^T}y\;} \right) \cdot {c^T}y\;\\
 \Rightarrow {c^T}{\eta ^\varepsilon } = {c^T}{x^*} - \delta \left| {{c^T}y\;} \right| \le {c^T}{x^*}
\end{array}
\]故我們得到 $\eta^\varepsilon$ 為對於 $|\varepsilon| \leq \delta$最佳解。故Optimality 被保證；亦即
我們現在找到 標準型式的Linear Programming 問題的 feasible solution $\eta^\varepsilon$，接著我們保證了此解的Optimality。
接著我們回憶前一篇得到的結果
----
標準型式的Linear Programming 問題若存在feasible solution，則必定存在一個 basic + feasible solution，
----
故我們得到
對具有標準形式的Linear Programming問題，若其存在一個optimal + feasible solution $x^*$，則必定存在一個optimal basic + feasible solution $\tilde x^*$。 至此證明完畢。 $\square$

============
Comments

一般而言，前篇的定理與Optimality Theorem合稱為 Fundamental Theorem of LP

我們將其寫在下方
=================================
Theorem (Fundamental Theorem of LP)：
考慮標準型式的線性規劃 (Standard LP)問題

令 $x \in \mathbb{R}^n$，
\[\begin{array}{l}
\min {c^T}x\\
s.t.\\
\left\{ \begin{array}{l}
Ax = b,\\
x \ge 0
\end{array} \right.
\end{array}\]其中 $A$ 為 $m \times n$ 矩陣且 $n>m$, $rank(A) = m$，$A$ 沒有全為零的column$；b \geq 0$，
1. 若其存在一個 Feasible Solution，則必存在一個 Basic + Feasible 的解
2. 若其存在一個optimal + feasible solution，則必定存在一個optimal basic + feasible solution 。
=================================

ref: E. K. P. Chong, S. H. Zak, An Introduction to Optimization 2nd, Chapter 15.

==============
延伸閱讀
[最佳化] 淺談線性規劃(0)- Standard form of Linear Programming

[最佳化] 淺談線性規劃(1)- Feasible solution and Basic solution

[最佳化] 淺談線性規劃(2)- Optimality Theorem

[最佳化] 淺談線性規劃(3)- Geometric View of LP

[最佳化] 淺談線性規劃(4)- How to move from one Basic Feasible solution to another- An Example