最优化问题
数学模型
$$ \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$ 中对应元素 $b_j$ 除选取元素，比较结果取最小值，该元素 $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}$，以其为基变量（构成单位矩阵），其余变量为 0，得到一组可行解 $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 。
带入目标函数求得最优值（最大｜最小）。
何时一樽酒，重与细论文。