最佳化理論與方法

最佳化問題

數學模型

$$ \min f(\vec{x}),\vec{x}\in \vec{R^{n}} $$$$ \text{s.t.}{ \begin{cases} c_i(x)=0,& i \in E = {1,2,\cdots,l}\\ c_i(\vec{x})\ge 0,& i \in I = {l+1,\cdots,l+m}\\ \end{cases}} $$

其中，

• $\vec{x}=(x_1,x_2,\cdots,x_n)^T$ 稱為決策變數
• $f(\vec{x})$ 稱為目標函數
• s.t.（subject to，受限於），稱為約束條件

分類

1. 時間
   1. 靜態問題
   2. 動態問題
2. 約束條件
   1. 有約束問題
   2. 無約束問題
3. 目標函數與約束條件是否為線性函數
   1. 線性規劃
   2. 非線性規劃
4. 目標函數與約束條件是否為凸函數
   1. 凸最佳化問題
   2. 非凸最佳化問題

二次型矩陣

二次型：

$$ \begin{align} f &=x_1^2-3x_3^2-4x_1x_2+x_2x_3\\ &=(x_1,x_2,x_3) \begin{bmatrix} 1 & -2 & 0\\ -2 & 0 & \frac{1}{2}\\ 0 & \frac{1}{2} & -3\\ \end{bmatrix} \begin{bmatrix} x_1\\ x_2\\ x_3\\ \end{bmatrix}\\ &= \vec{X^T} A \vec{X}\\ \end{align} $$

二次型矩陣：

$$ \begin{bmatrix} 1 & -2 & 0\\ -2 & 0 & \frac{1}{2}\\ 0 & \frac{1}{2} & -3\\ \end{bmatrix} $$

Hessen 矩陣

以二元二次函數為例：

$$ \nabla^2 f(x_1,x_2)= \begin{bmatrix} \frac{\partial^2 f}{\partial x_1^2} & \frac{\partial^2 f}{\partial x_1 \partial x_2}\\ \frac{\partial^2 f}{\partial x_2 \partial x_1} & \frac{\partial^2 f}{\partial x_2^2}\\ \end{bmatrix} $$

可行解

• 可行解：滿足所有約束條件的解。
• 可行集（容許集、可行域）：所有可行解所構成的集合。
• 最佳化問題：在可行集中找出使目標函數取得最大值或最小值的點。
• 駐點：$\nabla f(x_0)=0$，稱 $x_0$ 為駐點。
• 鞍點：$x_0$ 為駐點，但不是極值點時，稱為鞍點。

凸集

定義

在平面中，若一個圖形內部任意兩點的連線仍位於圖形內部，則該圖形稱為凸集。

性質

1. 凸集的交集仍為凸集
2. 凸集按比例縮放後仍為凸集
3. 凸集的和集（不是並集）是凸集
   • 設 $D_1,D_2$ 是凸集，則 $D_1+D_2=\{z|z=x+y,x \in D_1,y \in D_2\}$ 是凸集。
4. 凸集的線性組合是凸集。

常見凸集

1. 空集
2. 整個歐氏空間 $\vec{R^n}$
3. 超平面 $H=\{x \in \vec{R^n} | a_1x_1+a_2x_2+\cdots +a_nx_n=b\}$
4. 半空間 $H^+=\{x \in \vec{R^n} | a_1x_1+a_2x_2+\cdots +a_nx_n \ge b\}$

凸組合

設 $x_i \in \vec{R^n},i=1,2,\cdots ,k$，實數 $\lambda_i \ge 0,\sum^k_{i=1}\lambda_i=1$，則 $x=\sum^k_{i=1}\lambda_ix_i$ 稱為 $x_1,x_2,\cdots , x_k$ 的凸組合。
凸集中任意有限個點的凸組合仍然在該凸集中。

極點

設 $D$ 為凸集，$x \in D$，若 $D$ 中不存在兩個相異的點 $y,z$ 及某個實數 $\alpha \in (0,1)$ 使得 $x=\alpha y+(1-\alpha)z$，則稱 $x$ 為 $D$ 的極點。

人話：以平面五邊形為例，極點就是它的頂點；以半圓形為例，極點則是直徑的兩個端點以及半圓弧上的尖端。

凸函數

定義

定義在某個凸集上的函數 $f(x)$，若對凸集內任意兩點 $x_1,x_2$ 都有

$$ f(\alpha x_1+(1-\alpha)x_2) \le \alpha f(x_1)+(1-\alpha)f(x_2) $$

則稱該函數為凸函數。
若不等號為嚴格小於號 $\lt$，則稱為嚴格凸函數。

判斷

1. 多元函數的 Hessen 矩陣為半正定矩陣——>多元函數是凸函數。
2. 多元函數的 Hessen 矩陣為正定矩陣——>多元函數是嚴格凸函數。
3. 多元線性（一次）函數是 $\vec{R^n}$ 上的凸函數。

凸最佳化問題

定義

目標函數與約束函數都是凸函數的最佳化問題。

• 凸最佳化的可行集是凸集
• 任何區域最優解都是全域最優解
• 若目標函數是嚴格凸函數，則區域最優解存在且唯一

線性規劃

形式

非標準形式

• 目標函數：$\max z=\sum^{n}_{j=1}c_jx_j=CX$
• 係數矩陣： $$ A= \begin{bmatrix} a_{11} & \cdots & a_{1n}\\ \vdots & \ddots & \vdots\\ a_{m1} & \cdots & a_{mn}\\ \end{bmatrix} =(P_1,P_2,\cdots,P_n) $$
• 資源向量：$b=\begin{bmatrix} b_1\\ \vdots \\ b_m\\ \end{bmatrix}$
• 決策變數向量：$X=(x_1,x_2,\cdots , x_n)^T$
• 約束條件： $$ \begin{cases} \sum^{n}_{j=1}a_{ij}x_j=b_i,&i=1,2,\cdots,m\\ x_j \ge 0,& j=1,2,\cdots,n\\ \end{cases} $$ $$ \begin{cases} AX=b\\ X \ge \vec{0} \end{cases} $$

標準形式

1. 將極大問題轉為極小化
2. 鬆弛變數：對於 $\le$ 約束，引入鬆弛變數使等號成立
3. 剩餘變數：對於 $\ge$ 約束，引入剩餘變數使等號成立
4. 自由變數：在實際問題中可自由取值的變數，記作 $x_i=x'-x''$

$$ \begin{cases} \min f(x_1,x_2,\cdots , x_n)\\ \text{s.t.} \begin{cases} h_j(x_1,x_2,\cdots,x_n)=0&(j=1,2,\cdots)\\ x_j \ge 0\\ \end{cases} \end{cases} $$

基矩陣

• 基（基矩陣）：係數矩陣中的最大非奇異子矩陣。
  • 若係數矩陣 $A$ 為 $m \times n$ 矩陣，且 $rank(A)=m$，則基矩陣為任意 $m \times m$ 的非奇異子矩陣。
• 基變數：基中所有列向量所對應的未知數。
• 非基變數：不屬於基變數的未知數。
• 基本解：令所有非基變數為零所得到的解。
• 非退化基本解：基本解中非零分量個數等於約束方程數。否則稱為退化基本解。
• 基本可行解：滿足 $\text{s.t.}$ 非負條件的基本解。
• 最優基可行解：所有基本可行解中，使函數值達到最優的基可行解。

線性規劃解的性質

1. 線性規劃的可行集是凸集
2. 若有最優解，必定在可行集頂點取得

單純形法

判別數（檢驗數）

每一個未知數都對應一個判別數

$$ \sigma_j=C^T_J \vec{P_j}-c_j=\sum^{m}_{i=1}c_ia_{ij}-c_j $$

• $C^T$ 為目標函數係數
• $C^T_J$ 為基變數在目標函數中的係數
• $P_j$ 表示 $A$ 矩陣第 $j$ 列
• $c_i$ 表示第 $i$ 個基變數在目標函數中的係數
• $c_j$ 表示目標函數中第 $j$ 個變數的係數，與 $c_i$ 無關。

當所有判別數都小於等於零時，基可行解即為最優解。

一般來說，基變數的判別數為零。

基變換

選取基矩陣

優先選取單位矩陣作為基矩陣，先計算初始基可行解與判別數。

畫出初始單純形表

	$P_1$	$P_2$	$\cdots$	$P_n$	$\vec{b}$
係數矩陣	$a_{11}$	$a_{12}$	$\cdots$	$a_{1n}$	$b_1$
	$a_{21}$	$a_{22}$	$\cdots$	$a_{2n}$	$b_2$
	$\vdots$	$\vdots$	$\ddots$	$\vdots$	$\vdots$
	$a_{m1}$	$a_{m2}$	$\cdots$	$a_{mn}$	$b_m$
判別數	$\sigma_1$	$\sigma_2$	$\cdots$	$\sigma_n$	最優值

選取合適的進基列

若判別數大於零，則該列有分量大於零，選取該列作為進基列 $P_j$，對應變數為進基變數 $x_j$。

選取主元

在該進基列中挑選大於零的元素 $a_{ij}$，將 $b$ 中對應元素除以所選元素，取比值最小者，該元素 $a_{ij}$ 即為主元。
若判別數大於零，而該列元素全都小於零，則此線性規劃無最優解。

初等列運算

將主元化為 1，並把該列其他係數元素化為 0。
幾何意義：更換可行域頂點。

出基列

根據係數矩陣選取新的基矩陣。與原來的基矩陣相比，被取代的那一列為出基列，對應變數即為出基變數。
接著重新計算判別數，列出新的單純形表。

新一輪基變換

當判別數行發生變化後，如果又出現新的正判別數，就再選取該列作為新的進基列，重新選主元並做初等變換。

結果

當所有判別數都小於等於零時，$\vec{b}$ 中的值就是基變數的值，非基變數取 0，合起來構成最優解，再代回目標函數即可求得最小值。

單純形法適用條件

1. 非齊次項元素非負。
2. 存在可行解。
3. 鬆弛變數與非基變數的值乘積和為零。
4. 問題是凸可行域上的線性規劃問題。
5. 可行解集合有限。

人工變數法

當係數矩陣中不含單位矩陣時，通常採用引入人工變數的方式，人為構造出一個單位矩陣。

設線性規劃問題的約束條件為 $\sum^{n}_{j=1}a_{ij}=b_i(i=1,2,\cdots ,m)$，分別給每個約束條件加入人工變數 $x_{n+1},x_{n+2},\cdots,x_{n+m}$，以其作為基變數（構成單位矩陣），其餘變數置零，即得到一組可行解 $x^{(0)}=(0,0,\cdots,0,b_1,b_2,\cdots,b_m)^T$。
在此基礎上再透過基變換求解，最終得到不含非零人工變數的最優解。

若當所有判別數小於零時，仍有非零人工變數存在，則說明原問題無可行解。

大 M 法

對於最小化問題，在約束條件中加入人工變數後，令人工變數在目標函數中的係數為 $M$（$M \in \vec{R^+}$）。
為了求得最小目標函數值，需要不斷進行基變換，使人工變數取值為 0。對於最大化問題，則取 $M \in \vec{R^-}$。

退化情形

若單純形法陷入循環，而該問題又確有最優解，可透過以下方法避免循環。

攝動法

修正單純形法

線性規劃對偶理論

線性規劃對偶問題形式

對稱形式

原問題

$$ \begin{cases} \min f=\vec{c^T}\vec{x}\\ \text{s.t.} \begin{cases} \vec{A}\vec{x} \ge \vec{b}\\ \vec{x} \ge \vec{0} \end{cases} \end{cases} $$

對偶問題

$$ \begin{cases} \max w=\vec{b^T}\vec{y}\\ \text{s.t.} \begin{cases} \vec{A^T}\vec{y} \le \vec{c}\\ \vec{y} \ge \vec{0}\\ \end{cases} \end{cases} $$

對應關係：

• （1）原問題中的約束條件個數等於其對偶問題中的變數個數；
• （2）原問題目標函數的係數，就是對偶問題中約束條件右端項；
• （3）原問題目標函數為最小化時，對偶問題目標函數為最大化；
• （4）原問題的約束條件為「≥」，則對偶問題的約束條件為「≤」。

非對稱形式

原問題

$$ \begin{cases} \min f=\vec{c^T}\vec{x}\\ \text{s.t.} \begin{cases} \vec{A}\vec{x} = \vec{b}\\ \vec{x} \ge \vec{0} \end{cases} \end{cases} $$

對偶問題

$$ \begin{cases} \max w=\vec{b^T}\vec{y}\\ \text{s.t.} \begin{cases} \vec{A^T}\vec{y} \le \vec{c}\\ \vec{y} \text{無約束} \end{cases} \end{cases} $$

一般情形

若原問題同時含有 $\le,\ge,=$ 等多種約束，則先引入鬆弛變數與剩餘變數，將約束統一化為 $=$，再用非對稱形式建立對偶問題。

對偶單純形法

• 單純形法：先保證 $\vec{b} \ge 0$，再根據檢驗數 $\le 0$ 迭代。
• 對偶單純形法：先保證檢驗數 $\le 0$，再依據 $\vec{b} \ge 0$ 迭代。

確保檢驗數 $\le 0$

選取出基

若存在 $b_i \lt 0$，則取其中最小的 $\min b_i$ 所在列作為出基列，對應變數為出基變數。

選取進基

將檢驗數除以出基列中為負值的係數（$a_{ij} \lt 0$），取結果最小值所對應的列作為進基列，對應變數為進基變數。

行變換

透過行變換，將進基列變成可匹配基矩陣（單位矩陣）的形式，此時 $\vec{b}$ 也會隨之改變。
重新計算檢驗數，並確保其不大於零。

新一輪基變換

若仍有負值 $b_i \lt 0$，則取最小的 $\min b_i$ 進行下一輪基變換。

結果

當所有 $b_i \ge 0$ 時，$\vec{b}$ 構成基變數的最優解部分，而非基變數部分取 0。
將其代回目標函數即可得到最優值（最大或最小）。

靈敏度分析