最优化方法课程复习

组合优化问题

一. 线性规划的图解法

二. 基本单纯形法

采用单纯形法解决线性规划问题，在将线性规划问题化成标准型后，首先，我们要判断能否找到初始基（即线性无关的列），如果不能一眼找到，我们就用两阶段法的第一阶段来找到这个基。

用到的符号及等式：

$c_B{X}_B+c_N{X}_N=c_B{B}^{-1}b-(c_B{B}^{-1}N-c_N)X_N$ 检验数向量：$\zeta =c_B{B}^{-1}N-c_N$

$X_B=B^{-1}b-B^{-1}N{X}_N$

三. 两阶段单纯形法

第一阶段：

对于原问题的约束条件，加入人工变量， 目的是使约束条件中能够存在显而易见的基（基以单位矩阵的形式呈现），目标函数改为求人工变量之和的最小值。此时，可将问题完全视为找到初始基的线性规划问题进行单纯形算法求解。

求解之后的结果分为几种情况，对几种情况进行讨论，目的是获得原问题的初始基。

第二阶段：

既然已知初始基，则采用基本单纯形算法来求解线性规划。

四. 对偶单纯形法

首先，我们要通过解一个扩充问题找到初始对偶可行的基本解，然后，我们在原问题上构造单纯形表，构造的单纯形表的区别在于，我们不要求必须全部非负。其基本运算如下：

五. 背包问题的动态规划算法

六. 给线性规划，写其对偶规划

当给出线性规划的时候，从推导的角度来讲，我们总是要从标准型里抽取出线性规划一般型和规范型的对偶规划

利用检验数向量所进行的推导。

如果是做题，可以从理解的角度记住结论直接进行书写。

如图所示：

标准型：

一般型：

规范型：

连续优化问题

一维搜索的方法包括试探法和函数逼近法

七. 最速下降法

最速下降法属于试探法，在此之前，先说一说黄金分割法

黄金分割法：

当我们给定一个函数及区间，且该函数在该区间上是单峰函数，要求给出满足一定精度的解，如果是凸函数，我们以此来说明：采用黄金分割法，也即是0.618法，是将区间分割成四部分
$$[a,\lambda ,\mu ,b]$$

$$b-\lambda =\mu -a=0.618(b-a)$$

$$b-\mu =\lambda -a=0.382(b-a)$$

如果x落在区间$\mu -a$中，则$\mu$是该区间的b，$\lambda$是该区间的$\mu$，如果x落在区间$b-\lambda$中，则$\lambda$是该区间的a，$\mu$是该区间的 $\lambda$。同理依次进行区间判断及缩小，最后当b-a的值小于精度时，即停止。此时得出解
$$\overline{x}=\frac{1}{2}(b-a)$$
接下来说最速下降法

下降方向：

下降方向的概念及***d***的两种表达形式

最速下降法的基本思想是：当当前点$x^k$处的梯度不为0（或不满足精度要求）时，从当前点$x^k$出发沿负梯度方向$-▽f(x^k)$出发前进到下一个点$x^{k+1}$，直到满足要求。

八. 牛顿法

牛顿法的基本思想是在极小点附件用简单的函数–二阶泰勒多项式近似目标函数f(x)，进而求出极小值的估计值。

一元优化问题的牛顿法：一元优化问题的牛顿法是一种用于一维搜索的函数逼近法。

由于一元优化问题的牛顿法很简单，这里直接给出求解步骤：

多元优化问题的牛顿法：

类比一元优化问题的牛顿法，这里直接给出计算步骤并做出一定说明：

这里对迭代点公式做出说明：

是函数f(x)在点**$x^{(k)}$**处的黑塞矩阵，黑塞矩阵的具体计算公式如下：

九. 阻尼牛顿法

我们将记为牛顿方向，于是迭代点公式可以写为：

受一维搜索的启发，很容易想到在牛顿方向上增加步长因子$\lambda$，即在第k次迭代时进行一维搜索，找${\lambda }_k$满足：

这就是阻尼牛顿法。

十. 用K-T条件解约束优化问题

首先，明确一点，这里讨论的是约束最优化问题，其一般形式如下：🔽

与非约束优化问题相比，我们自然引出了可行方向的概念。

K-T条件：

我们先来看不等式约束问题的一阶最优性条件：

当加入积极约束的梯度向量线性无关这一个约束规格时，我们就得到了不等式约束问题的一阶最优性条件：

需要说明的是，K-T条件是$\overline{x}$是全局最优解的必要条件，在一定条件下，K-T条件才成为问题（CPI）最优解的充分条件：

类似于不等式约束问题的推导，我们也可以得到一般约束问题的K-T条件

外点罚函数和内点罚函数的设计思路都是将约束优化问题转化为无约束优化问题来求解最优值

十一. 外点罚函数法

外点罚函数是通过对目标函数引入一个惩罚因子$\sigma$来将约束条件转化到目标函数上，从而将目标函数当作无约束问题求解。

$\sigma$是一个很大的数，当解不在可行域内时，惩罚因子为导致惩罚项尤其大，从而保证了最优解的取得位置。

十二. 内点罚函数法

内点罚函数法是通过对目标函数引入一个惩罚因子$\mu$来将约束条件转化到目标函数上，从而将目标函数当作无约束问题求解。

$\mu$是一个很小的数，当可行域内的解临近可行域边界时，惩罚因子会导致惩罚项尤其大，从而保证了最优解的取得位置。

正因为如此，从计算意义上讲，内外点罚函数法求解最优解问题是属于无约束求解的问题。

本复习笔记参考老师讲义及陈宝林老师《最优化理论与方法（第2版）》教材