最佳化問題
數學模型
$$ \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，受限於），稱為約束條件
分類
- 時間
- 靜態問題
- 動態問題
- 約束條件
- 有約束問題
- 無約束問題
- 目標函數與約束條件是否為線性函數
- 線性規劃
- 非線性規劃
- 目標函數與約束條件是否為凸函數
- 凸最佳化問題
- 非凸最佳化問題
二次型矩陣
二次型：
$$ \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$ 為駐點，但不是極值點時，稱為鞍點。
凸集
定義
在平面中，若一個圖形內部任意兩點的連線仍位於圖形內部，則該圖形稱為凸集。
性質
- 凸集的交集仍為凸集
- 凸集按比例縮放後仍為凸集
- 凸集的和集（不是並集）是凸集
- 設 $D_1,D_2$ 是凸集，則 $D_1+D_2=\{z|z=x+y,x \in D_1,y \in D_2\}$ 是凸集。
- 凸集的線性組合是凸集。
常見凸集
- 空集
- 整個歐氏空間 $\vec{R^n}$
- 超平面 $H=\{x \in \vec{R^n} | a_1x_1+a_2x_2+\cdots +a_nx_n=b\}$
- 半空間 $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$，則稱為嚴格凸函數。
判斷
- 多元函數的 Hessen 矩陣為半正定矩陣——>多元函數是凸函數。
- 多元函數的 Hessen 矩陣為正定矩陣——>多元函數是嚴格凸函數。
- 多元線性（一次）函數是 $\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} $$
標準形式
- 將極大問題轉為極小化
- 鬆弛變數：對於 $\le$ 約束，引入鬆弛變數使等號成立
- 剩餘變數：對於 $\ge$ 約束，引入剩餘變數使等號成立
- 自由變數：在實際問題中可自由取值的變數，記作 $x_i=x'-x''$
基矩陣
- 基（基矩陣）：係數矩陣中的最大非奇異子矩陣。
- 若係數矩陣 $A$ 為 $m \times n$ 矩陣，且 $rank(A)=m$，則基矩陣為任意 $m \times m$ 的非奇異子矩陣。
- 基變數：基中所有列向量所對應的未知數。
- 非基變數：不屬於基變數的未知數。
- 基本解：令所有非基變數為零所得到的解。
- 非退化基本解：基本解中非零分量個數等於約束方程數。否則稱為退化基本解。
- 基本可行解：滿足 $\text{s.t.}$ 非負條件的基本解。
- 最優基可行解：所有基本可行解中，使函數值達到最優的基可行解。
線性規劃解的性質
- 線性規劃的可行集是凸集
- 若有最優解，必定在可行集頂點取得
單純形法
判別數（檢驗數）
每一個未知數都對應一個判別數
$$ \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，合起來構成最優解，再代回目標函數即可求得最小值。
單純形法適用條件
- 非齊次項元素非負。
- 存在可行解。
- 鬆弛變數與非基變數的值乘積和為零。
- 問題是凸可行域上的線性規劃問題。
- 可行解集合有限。
人工變數法
當係數矩陣中不含單位矩陣時，通常採用引入人工變數的方式，人為構造出一個單位矩陣。
設線性規劃問題的約束條件為 $\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。
將其代回目標函數即可得到最優值（最大或最小）。
何時一樽酒，重與細論文。