最优化理论

• 2024 研究生课程「最优化理论」笔记 & 复习要点。

1. 绪论

1.1. 概念

• 分类：可以根据不同属性的性质进行分类，如

  1. 目标函数：分为线性优化和非线性优化
  2. 约束条件：有约束（等式约束、不等式约束）和无约束
  3. 决策变量：离散型、连续型
  4. 最优解：单目标、多目标
  5. 优化问题：凸优化（通常为全局最优解）、非凸优化（多个局部最优解）

• 解：

  1. 最优解：目标函数取最值的变量
  2. 可行解：满足约束条件，但不一定最优
  3. 梯度：$g = \nabla f(x)$，目标函数的方向导数
  4. Hesse矩阵：$G = \nabla^2 f(x)$，目标函数的二阶方向导数

1.2. 迭代格式以及敛散性

• 迭代格式：

  1. 初始化：选择$x_0$作为初始解。
  2. 迭代：寻找可行解，找到最优梯度（最优下降方向）更新解。
  3. 停止：满足停止条件（数值不再显著变化、最大迭代次数、特点约束条件）时则停止。

• 敛散性：判断算法能否找到最优解或接近最优解。

2. 最优化数学建模

2.1. 线性规划

• 例如资源分配类问题， 有$n$种产品，每种产品包含$m$个属性需求（原料、价格、利润、时间），而这些资源是有约束的（不能大于、不能少于、必须刚好等），每种资源最多使用$b_i$，每种产品会产生$c_i$的单位价值，让你求如何分配这些资源生产产品获取最大（最小）的价值。

  显然决策变量$x$应该是一个包含$n$个元素的列向量，所有产品即对应的属性需求我们可以写为系数矩阵$A\in \mathbb{R}^{n\times m}$，由此我们可以得到如下目标函数以及约束条件。

  $$\min(\max) z = c^Tx\\ s.t. \begin{cases} A^T_ix &\le(=,\ge) b_i, x &\succeq 0 \end{cases}$$

2.2. 标准化

• 为了方便我们使用通用的方法解决线性规划问题，我们需要将模型进行标准化，方法为

  1. 若目标函数为求最大值，令$z' = -z$，则转化为求$\min z' = -c^T x$。
  2. 当$b_i<0$时，两边乘上-1。
  3. 约束方程为不等式时，则在左边加上/减去非负松弛变量，转化为等式。
  4. 当$x$约束为$x\le 0$时，令$x'=-x,\ x'\ge 0$。
  5. 当$x$无约束时，令$x = x' - x''$，其中$x', x'' \ge 0$

  这样我们便可以得到标准型：最小目标函数、等式约束、决策变量非负约束。

3. 线性规划

3.1. 基本可行解

• 约束为线性函数，标准数学表达式为

  $$\min \mathbf{c}^T\mathbf{x}\\ \mathrm{s.t.}\begin{cases} A\mathbf{x} &= b\\ x &\ge 0 \end{cases},\quad A\in\mathbb{R}^{m\times n}_m,\ \mathbf{x,c} \in\mathbb{R}^{n},\ b\succeq 0$$

• 设$A = (p_1,p_2,\dots,p_n)$，$r(A) = m$。设这$m$个线性无关列向量的下标集合为$S$，其构造的$m\times m$方阵为$B$，设解$x$中以$S$中元素作为下标构成的列向量为$x_B$。

  则$B$为基矩阵，$x_B$为一组基，有$x_B = B^{-1}b$，令其非基变量为0，得$x$基本解。若满足$x\succeq 0$，则称$x$为基础可行解。

  解题时就是排列组合构造$B$，通过$x_B = B^{-1}b$得到基，然后填充0得到$x$为一组可行解。

3.2. 单纯形法

• 由于基本可行解会有很多，此时可以用单纯形法来系统搜索最优解。

  其理论依据为若问题存在可行解，则问题的可行域是凸集。则基可行解对应问题可行域的顶点，若存在最优解，则最优解一定是基可行解（即顶点）。

  1. 将线性规划转换为标准形

  2. 在$A$中寻找一个基矩阵$B$，通过初等行变换将$[B, b]$转换为单位矩阵$[I,b']$，若此时$b'\not \succeq 0$，则重新寻找$B$。

     令非基变量为0,计算得到初始基本可行变量$x = (0,0,540,450,720)^T$，此时可以画出单纯型表

     	$x_1$	$x_2$	$x_3$	$x_4$	$x_5$	$b$	$\theta$
     $f(x)$	70	30	0	0	0	0
     $x_3$	3	9	1	0	0	540	180
     $x_4$	5	5	0	1	0	450	90
     $x_5$	9	3	0	0	1	720	80

  3. 判断当前点$x$是否为最优解

     计算每一列的判别数$\sigma_j = c_j - c^Tp_j$，取$\sigma_k = \max_j\{\sigma_j\}$，若$\forall \sigma_j \le 0$，则算法无解，停止，否则选择$p_k$作为入基列。

     若当前目标函数非基变量系数小于等于（如果是$\min$问题则是大于等于）0时则为最优解，而现在不等于0,则意味着如果$x_1,x_2$继续增大还会有更大的目标函数值。

  4. 基变量出基与非基变量入基

     入基的规则为选择使目标函数变化最快的非基变量入基，即系数最大的非基变量。例如这里我们选择$x_1$，然后我们需要计算单纯型表的$\theta$，有$\theta = b / a_i$，这里我们可以看到约束3对应的$\theta$最小，则选择对应的$x_5$出基。

     画出单纯型表

     	$x_1$	$x_2$	$x_3$	$x_4$	$x_5$	$b$	$\theta$
     $f(x)$	0	20/3	0	0	-70/9	5600
     $x_3$	0	8	1	0	-1/3	300
     $x_4$	0	10/3	0	1	-5/9	50
     $x_1$	1	1/3	0	0	1/9	80

     这里的变换过程便是做初等行变换让$x_{11}$置1，所在列置$0$，当前点的解$x = (80,0,300,50,0)^T$。

  继续这个过程，直到当前解为最优解为止。

3.3. 大M法

• 增加两个$m$维度向量$e = (1,1,\dots, 1)^T, x_M=(x_{n+1},x_{n+2},\dots,x_{n+m})^T$。其中$x_M$为人工变量。将标准形式的线性规划问题转换为

  $$\min \mathbf{c}^T\mathbf{x} + Me^Tx_M\\ \mathrm{s.t.}\begin{cases} A\mathbf{x} + x_M&= b\\ x &\ge 0 \\ x_M &\ge 0 \end{cases},\quad A\in\mathbb{R}^{m\times n}_m,\ \mathbf{x,c} \in\mathbb{R}^{n},\ b\succeq 0$$

  其中$M$为很大的数，然后使用单纯型法求解，结果可能为：

  1. 求得最优解，且人工变量全是0，则该解为原问题最优解。
  2. 求得最优解，但人工变量不全是0，则原问题无最优解。
  3. 没有最优解，则原问题没有最优解或可行解。

3.4. 两阶段法

• 去掉人工变量，以第一阶段最后的基变量为初始变量开始迭代。问题格式为

• 第一阶段

  $$\min \mathbf{e}^T\mathbf{x_a}\\ \mathrm{s.t.}\begin{cases} A\mathbf{x} + x_a &= b\\ x &\ge 0\\ x_a &\ge 0 \end{cases}$$

  用单纯形法求解得到解$(x,x_a)^T$，此时有

  1. $x_a \not = 0$，原问题无可行解。
  2. $x_a = 0$且$x_a$的分量都是非基变量，此时$x$就是原问题的一个基可行解。
  3. $x_a=0$且$x_a$的分量都是基变量，此时用主元消去法，把原来变量中的某些非基变量引入基，替换出基变量中的人工变量，再开始新的第二阶段。

• 第二阶段即为在上述基可行解$x$的基础上使用单纯形法求最优解。

3.5. 计算机求解

• 对于标准线性规划问题，matlab求解函数为

  [x, fval] = linprog(f, A, b, A_eq, b_eq, lb, ub)

  参数分别为：

  $x$：决策向量，返回最优解。 $f$：价值向量，即目标函数中的系数数组。 $A$：不等式约束的系数矩阵，默认为$\le$ 。 $b$：不等式约束的右端常数向量。 $A_{eq}$：等式约束矩阵。 $b_{eq}$：等式约束的右端常数向量。 $lb, ub$：变量取值范围的下界和上界（闭区间）。

  参数没有默认为空数组。题目给的不是标准形要转换。

3.6. 其他方法

• 分支定界法：
• 隐枚举法：
• 表上作业法：
• 匈牙利法：

4. 非线性规划

4.1. 概念

• 当目标函数或约束中含有非线性函数的最优化问题称为非线性规划。

  与线性规划的区别在于，若线性规划的最优解一定在边界上，而非线性规划则可能在任意一点达到。

• 梯度

  $$\nabla f(x) = [\frac{\partial f(x)}{\partial x_1},\frac{\partial f(x)}{\partial x_2},\dots,\frac{\partial f(x)}{\partial x_n}]^T$$

• Hesse矩阵：即二阶偏导矩阵

  $$H_f = \nabla^2 f(x) = \begin{bmatrix} \frac{\partial f(x)}{\partial x_1^2}&\frac{\partial f(x)}{\partial x_1\partial x_2}&\cdots&\frac{\partial f(x)}{\partial x_1\partial x_n}\\ \frac{\partial f(x)}{\partial x_2\partial x_1}&\frac{\partial f(x)}{\partial x_2^2}&\cdots&\frac{\partial f(x)}{\partial x_2\partial x_n}\\ \vdots&\vdots&\ddots&\vdots\\ \frac{\partial f(x)}{\partial x_n\partial x_1}&\frac{\partial f(x)}{\partial x_n\partial x_2}&\cdots&\frac{\partial f(x)}{\partial x_n^2} \end{bmatrix}_{n\times n}$$

• Taylor展开

  $$f(x) = f(\bar{x}) + \nabla f(\bar{x})^T(x-\bar{x})+\frac{1}{2}(x-\bar{x})^T\nabla^2f(\bar{x})^T(x-\bar{x}) + o(\lVert x - \bar{x}\rVert ^2)$$

• 凸集：集合$S\in \mathbb{R}^{n}$中任意两点的连结线段仍属于$S$，即$\lambda x^{(1)} + (1-\lambda)x^{(2)} \in S, \lambda\in[0,1]$。则$S$为凸集。

• 凸函数：$f(\lambda x^{(1)} + (1-\lambda)x^{(2)}) \le \lambda f(x^{(1)}) + (1-\lambda)f(x^{(2)})$

  一般求解其Hesse矩阵的特征值，特征值均大于等于0，则为凸函数。

  或者Hesse正定（主子式均大于等于0）

4.2. 一维线性搜索

• 对于多元函数的极值点求解常采用迭代求解，令$x^{k+1} = x^k + \alpha^k S^k$，其中

  $x^0$为初始点，$\alpha^k$为迭代方向，$S^k$为步长。

  当方向确定时，求最佳步长$S^k$就是求

  $$f(x^{k+1}) = f(x^k + \alpha^k S^k) = \varphi(\alpha_k)$$

  的极值，这一过程称为一维搜索（单变量优化）。

4.3. 黄金分割法

1. 初始区间$[a_1, b_1]$和精度$L>0$，计算试探点$\lambda_1$和$\mu_1$，计算函数值$f(\lambda_1), f(\mu_1)$，其中

   $$\lambda_1 = a_1 + 0.382(b_1-a_1)\\ \mu_1 = a_1 + 0.618(b_1-a_1)$$

2. 若$b_k - a_k < L$，则停止计算。当$f(\lambda_k)>f(\mu_k)$时令$a_{k+1} = \lambda_k, b_{k+1}=b_k,\lambda_{k+1}=\mu_k$，重新计算$\mu_{k+1}$。否则为$b_{k+1}=\mu_k, \mu_{k+1}=\lambda_k$，重新计算$\lambda_{k+1}$。

• 优点：算法简单，缩短率固定为黄金分割数，无需事先确定搜索次数，收敛速度可以接受。

4.4. Fibonacci法

1. 初始区间$[a_1, b_1]$和精度$L>0$，计算次数$n$使得$F_n\ge \frac{b_1-a_1}{L}$，辨别常数$\delta > 0$，试探点$x_1,x_1'$和对应函数值。

2. 若$f(x_k)>f(x_k')$，则$a_{k+1}=x_1,x_{k+1}=x_k'$，重新计算$x_{k+1}'$，否则反过来。

   $$x_{k+1} = a_{k+1} + \frac{F_{n-k-1}}{F_{n-k}}(b_{k+1}-a_{k+1})\\ x_{k+1}' = a_{k+1} + \frac{F_{n-k-2}}{F_{n-k}}(b_{k+1}-a_{k+1})\\$$

3. 当$k=n-2$时，令$x_n=x_{n-1},x_n'=x_{n-1}+\delta$，若$f(x_n)>f(x_n')$，则$a_n=a_{n-1},b_n=b_{n-1}$，反之$a_n=a_{n-1},b_n=x_n$。

• 二者相同点

  1. 都是分割方法
  2. 都是通过试探点进行函数值比较缩短搜索区间。
  3. 适用对象相同：极小化目标函数是单峰函数

• 区别：

  1. 搜索区间长度和缩短率不同
  2. 黄金分割法是近似最优，Fibonacci法是最优策略
  3. Fibonacci需要事先知道迭代次数，收敛速度略优于黄金分割法。

5. 无约束非线性规划

5.1. 最速下降法

• 梯度方向是函数值增长最快的方向，让迭代沿着负梯度方向前进，保证最速下降。

  即$x_{k+1} = x^k - \lambda \nabla f(x^k) = x^k+\lambda d^k$

  令$\varphi(\lambda) = f(x^k+\lambda d^k)$，利用精确一维搜索有

  $$\varphi '(\lambda_k) = \nabla f(x^k+\lambda d^k)^Td^k = 0$$

  即可求解得出$\lambda_k$。

• 特点：相邻两次迭代搜索总是垂直（正交），迭代过程为锯齿状，收敛速度慢。

5.2. 牛顿法

• 相比最速下降只考虑一阶导，牛顿法使用了二阶导作为每一个分量的步长。迭代式为

  $$x^{k+1} = x^k - \nabla^2 f(x^k)^{-1}\nabla f(x^k)$$

5.3. FR共轭梯度法

• 若$x^Ty = 0$则两向量正交，若$x^TAy = 0$，则称向量$x,y$关于$A$共轭正交，简称关于$A$共轭。迭代式为

  $$x^{k+1} = x^{k} + \lambda_k d_k$$

  其中$d_k = -\nabla f(x_k) + \frac{\lVert \nabla f(x_k)\rVert^2}{\lVert \nabla f(x_{k-1})\rVert ^2}d_{k-1}$，$\lambda_k = \frac{\nabla f(x_k)^T\nabla f(x_k)}{d_k^TQd_k}$。初始方向$d_0 = - \nabla f(x_0)$，如果$f$不是正定函数的话，$\lambda$还是用精确一维搜索得到，即$\nabla f(x_{k+1}) = 0$。

6. 带约束非线性规划

6.1. 罚函数法

• 对于带约束非线性规划方程，我们可以通过增加罚函数的方式将原问题转为无约束问题。

  若原问题带有约束$g_i(x)\ge 0, h_j(x) = 0$，设函数

  $$\phi(x, r, m) = f(x) + r\sum_{i=1}^p{G[g_i(x)]} + m\sum_{j=1}^qH[h_j(x)]$$

  其中$r,m$为罚因子，$H[h_j(x)] = [h_j(x)]^2$，$G$根据构造方式不同可以分为外点形式和内点形式。

• 内点罚函数：$G[g_i(x)] = \frac{1}{g_i(x)} \text{or} -\ln(g_i(x))$，且罚因子是递减序列一般为$\frac{1}{\sqrt{r^{(k)}}}$，仅适用于不等式约束优化问题。

  外点罚函数：$G[g_i(x)] = \{\min[0,g_i(x)]\}^2$，罚因子是递增序列。

• 算法思想：当$x$为可行点时，惩罚项等于0，此时$\phi(x,r,m) = f(x)$，当$x$为不可行点时，惩罚项是一个大正数，迫使迭代点靠近可行域。

• 计算式先选择外点还是内点构造罚函数。确定罚因子序列，初始点。然后用无约束问题求解方式求解。

  终止条件为差值收敛或变化量收敛。

6.2. 乘子法

• 只能处理等式约束，类似罚函数，将约束条件带入到目标函数中得到拉格朗日乘函数

  $$F(x, \lambda) = f(x) + \sum_{k=1}{l}\lambda_k h_k(x)$$

  其中$\lambda_k$为拉格朗日乘子，然后分别求对$x,\lambda_k$的偏导，令其等于0进行求解。

6.3. KKT条件

• 若既有等式约束也有不等式约束，定义如下拉格朗日函数

  $$L(x,\lambda,\mu) = f(x) + \sum_{j=1}^p \lambda_j h_j(x) + \sum_{k=1}^q \mu_k g_k(x)$$

  其中$\mu_k>0$是为不等式约束引入的松弛变量，也叫做KKT乘子。KKT条件为极值点$x*$满足

  $$\begin{aligned} \nabla f(x*) + \nabla \mu_k g_k(x*) &= 0\\ \mu_k g_k(x*) &= 0\\ g_k(x*) &\le 0 \end{aligned}$$

• 解题时找到$g_k(x*) = 0$的条件，构造$\nabla = 0$求解$\mu_k$，观察$\mu_k$是否大于等于0。

7. 动态规划

• 适用条件：

  1. 最优子结构：如果问题的最优解所含的子问题的解也是最优的，则称该问题具有最优子结构。
  2. 无后效性：子问题解一旦确定便不再改变，不受之后的问题的求解决策影响。
  3. 重叠子问题：空间换时间。

• 问题模型：

  1. 状态变量$s_k$：代表第$k$阶段的解。
  2. 决策变量$u_k(s_k)$：代表第$k$阶段的状态为$s_k$的决策变量，即确定第$k+1$阶段的状态。
  3. 转移方程：$s_{k+1} = T_k(s_k, u_k)$。

7.1. 逆推法

• 设$f_k(s_k) = \max/\min\{v_k(s_k,x_k)+f_{k+1}(s_{k+1})\}$，其中$f_{n+1}(s_{n+1}) = 0$。从后往前递推。

  对于资源分配问题状态变量$s_k$一般代表第$n$阶段至第$k$阶段剩余资源数，$x_k$为分配给第$k$个变量的资源数，则转移方程为

  $$s_{k+1} = s_k + a_{k}x_k$$

  这样由$s_{n+1}$可以得到关于$x_{n}$的约束，带入$f_{n}(s_{n})$得到$x_n$的最优值，然后带入$f_{n-1}(s_{n-1})$递推求解。遇到非线性函数时同样令$\varphi(x) = f(x)$，令$\varphi '(x) = 0$进行求解。

  最后取$s_1 = 0$代表最后不剩任何资源带入$f_1(s_1)$计算$x_1$的值，然后再依次求解$x_2,\dots$。

7.2. 顺推法

• 逆推法的反向，从最开始可分配资源$s_0 = 0$开始向后递推。转移方程为

  $$s_{k-1} = s_k - a_kx_k$$

  最后取$s_n = M$带入求解极值。

8. 多目标规划问题

8.1. 概念

1. 形式：$\max z_i = f_i(x)$，即满足多个约束条件下求最值，此时约束不严格。

2. 有效解：若$x$为解，若不存在其他解$x'$使得所有目标函数都有$f_k(x')\le f_k(x)$，并且其中至少有一个严格不等式，则$x$是原问题的有效解。（类似普通规划的最优解）

3. 弱有效解：不存在另一个解严格优于该解。

4. 与单目标规划问题的区别：

   1. 目标函数有多个，且互相冲突，需要决策者进行权衡。
   2. 不存在唯一最优解，而是一个解集（帕累托最优解集），解集中不存在严格的优劣关系。
   3. 求解方式不同。

8.2. 评价函数法

1. 理想点法

   对于$A_{m\times n}x = b$的多目标规划问题，规范化决策矩阵为$B$，其中$b_{ij}$等于$a_{ij}$初上对应列的模长。

   $$b_{ij} = a_{ij} / \sqrt{\sum_{i=1}^m}{a_{ij}^2}$$

   构造加权规范阵$C$，设各属性的权值向量$w = (w_1,w_2,\dots,w_n)^T$，则

   $$c_{ij} = w_j\cdot b_{ij}$$

   确定正理想解$C^*$和负理想解$C^0$，设正理想解$C^*$第$j$个属性值为$c^*_j$，其中

   $$c^*_j = \begin{cases} \max_i c_{ij},\ j\mathrm{为效益属性},\\ \min_i c_{ij},\ j\mathrm{为成本属性} \end{cases}$$

   即最少的成本，最大的收益，而负理想解则是上述的反内容。

   备选方案到理想解的距离分别为

   $$s^*_i = \sqrt{\sum_{j=1}^n{(c_{ij} - c^*_j)^2}},\ s^0_i = \sqrt{\sum_{j=1}^n{(c_{ij} - c^0_j)^2}}$$

   计算各方案的排序指标值（综合评价指数），即

   $$f^*_i = s^0_i / (s^0_i + s^*_i)$$

   按照$f^*_i$从大到小排优劣次序。

2. 线性加权和法

   对应解$x$，直接计算$Y = \sum w_if_i(x)$得到评价值。

3. 平方和加权法

   对应解$x$，直接计算$Y = \sum w_if_i(x)^2$得到评价值。

4. 极大极小法

   在不利的情况找到一个最有利的解，$Y = \max w_if_i(x)$

8.3. 主要目标法

8.4. 分层排序法

8.5. 计算机求解