研究生阶段 |《最优化方法》

文章目录

一、前言
二、章节
- 2.1 绪论
- - 2.1.1 最优化数学模型
  - - 什么是最优化问题?
    - 最优化问题的数学模型
    - 最优解的一般概念
    - 最优化理论和方法?理论和方法有什么区别?
    - 最优化问题的分类
    - 具体的学习内容
  - 2.1.2 用到的基本数学知识
  - - 范数与内积
    - 方向导数、梯度、子梯度、Hesse矩阵以及Jacobi矩阵、条件数
    - 泰勒公式
    - 序列的极限和聚点
  - 2.1.3 凸集、Farkas引理、凸函数、凸规划
  - - 什么是凸集?
    - Farkas引理?
    - 什么是凸函数?
    - 凸函数的性质?
    - 凸函数判别定理?
    - 什么是凸规划问题?
    - 凸规划问题的优点?
- 2.2 最优性条件和对偶理论
- - 2.2.1 无约束最优化问题的最优性条件
  - 2.2.2 约束最优化问题的最优性条件
  - 2.2.3 对偶理论——曲线救国
  - - 拉格朗日对偶函数和拉格朗日对偶问题
    - 强对偶性和KKT的关系
    - 强对偶性和鞍点
- 2.3 线搜索
- - 2.3.1 最优化算法结构
  - - 下降算法的两种方式
    - 算法的评价指标
    - 迭代的终止条件（三种）
    - 收敛速度
  - 2.3.2 精确线搜索（步长）
  - - 进退法
    - Fibonacci法——三分法（不是平均分）
    - 0.618法——Fibonacci的极限情况
    - 牛顿法
    - 三点两次插值
    - 精确线搜索和不精确线搜索的算法结构
  - 2.3.3 不精确线搜索
  - - Armijo-Goldstein准则
    - Wolfe-Powell准则
    - 简单准则和回退法
- 2.4 无约束最优化问题的求解算法
- - 2.4.1 最速下降法(梯度下降法)
  - - BB算法
    - 次梯度下降法
    - 随机梯度下降法与小批量随机梯度法
    - 动量(Momentum)梯度法——惯性梯度法
    - Nesteroy Accelerated Gradient(NAG)——加速度梯度法
    - AdaGrad (Adaptive gradient)——自适应梯度法
  - 2.4.2 共轭方向法和共轭梯度法
  - 2.4.3 牛顿法和拟牛顿法
  - - 牛顿法的缺点
  - 2.4.4 信赖域算法
  - 2.4.5 Powell 方法
- 2.5 优化约束问题的求解算法
- - 2.5.1 单纯形算法(求解线性规划问题)
  - - 线性规划的数学模型
    - 图解法
    - 单纯形算法
    - 大M法和两阶段法
    - 线性规划的对偶理论
  - 2.5.2 内点法(求解线性规划问题、非线性规划问题)
  - 2.5.3 信赖域法(求解无约束最优化问题的牛顿型信赖域法、拟牛顿型信赖域法，求解约束优化问题的信赖域法)
  - 2.5.4 高斯牛顿法、LM方法(求解非线性方程组)
  - 2.5.5 起作用集方法、拉格朗日牛顿法、序列二次规划法
  - 2.5.6 罚函数法、广义拉格朗日乘子法、交替方向乘子法(ADMM)
  - - 外罚函数法
    - 内罚函数法
    - 广义拉格朗日乘子法
    - 交替方向乘子法(Alternating Direction Method of Multipliers, ADMM)——大数据集会常用
  - 2.5.7 多目标规划
  - - 评价函数法之线性加权法
    - 评价函数法之平方和加权法/理想点法
    - 评价函数法之极小-极大法
    - 评价函数法之乘除法
  - 2.5.8 智能优化(遗传算法等)
  - 2.5.9 MATLAB优化工具箱
  - 2.5.10 泛函极值
三、考试
- 3.1 凸函数的性质
- 3.2 最优性条件
- 3.3 广义拉格朗日乘子法
- 3.4 最佳步长
- 3.5 最速下降法、牛顿法、共轭梯度法
- 3.6 KKT条件（求KKT点，并判断是否为全局最优解）
- 3.7 互补松弛定理
- 3.8 单纯形表法
四、作业
- 4.1 牛顿法为何收敛速度快？
- 4.2 共轭方向法为何效率高？
- 4.3 KKT 里的拉格朗日乘子是不是对偶问题的最优解？如果不是，什么条件下是对偶问题的最优解何时是 kkt 条件里的拉格朗日乘子？
- 4.4 从连续函数的范数和向量范数的相似性理解连续函数可以看成向量，这在求解泛函的最佳曲线时可以用传统的最优化方法求解。
- 4.5 如何理解无约束最优化问题的一阶必要性条件？
- 4.6 区别高斯牛顿法、拉格朗日牛顿法
- 4.7 强对偶下，从 KKT 条件推线性规划问题的互补松弛性。
- 4.8 利用对偶问题的定义推线性规划问题的对偶问题
- 4.9 推导在 2 范数下，最速下降法中负梯度方向是使得函数下降速度最快的方向，在椭球范数下，牛顿方向是使得函数值下降速度最快的方向.
- 4.10 区分差分、微分、泛函的变分
- 4.11 如何理解什么是真正的约束优化问题
五、最后

一、前言

嗯，这门课给范围很小；比数值分析好上一万倍。建议选择；当然可能学校不一样，情况可能也不一样。嗯，是一场知识盛宴，感谢shm老师馈赠！！！

二、章节

2.1 绪论

2.1.1 最优化数学模型

什么是最优化问题?

最优化问题是指在一定的约束条件下，寻找某个目标函数的最大值或最小值的问题。

最优化问题的数学模型

在这里插入图片描述

最优解的一般概念

在这里插入图片描述

最优化理论和方法?理论和方法有什么区别?

在这里插入图片描述

最优化问题的分类

在这里插入图片描述

具体的学习内容

在这里插入图片描述

2.1.2 用到的基本数学知识

范数与内积

嗯，这个就不讲了
在这里插入图片描述

方向导数、梯度、子梯度、Hesse矩阵以及Jacobi矩阵、条件数

Hesse就是二阶求导、
这个Jacobi矩阵，就是对函数而写的
在这里插入图片描述
条件数

泰勒公式

在这里插入图片描述

序列的极限和聚点

在这里插入图片描述

2.1.3 凸集、Farkas引理、凸函数、凸规划

什么是凸集?

在这里插入图片描述

Farkas引理?

在这里插入图片描述

什么是凸函数?

在这里插入图片描述

凸函数的性质?

在这里插入图片描述

凸函数判别定理?

在这里插入图片描述

什么是凸规划问题?

在这里插入图片描述

凸规划问题的优点?

在这里插入图片描述

2.2 最优性条件和对偶理论

2.2.1 无约束最优化问题的最优性条件

一阶条件(一阶必要性条件、一阶充分条件、一阶充要条件)
二阶条件(二阶必要性条件、二阶充分条件、二阶充要条件)

就是下面考点里面的最优性条件

在这里插入图片描述

2.2.2 约束最优化问题的最优性条件

一阶条件(一阶必要性条件、一阶充分条件、一阶充要条件)
二阶条件(二阶必要性条件、二阶充分条件、二阶充要条件)

KKT：一阶条件

第一个式子，▽g(x)是不等式的梯度，▽h(x)是等式的梯度
这也是互补松弛定理

在这里插入图片描述
二阶

2.2.3 对偶理论——曲线救国

拉格朗日对偶函数和拉格朗日对偶问题

在这里插入图片描述

强对偶性和KKT的关系

在这里插入图片描述

强对偶性和鞍点

在这里插入图片描述

2.3 线搜索

2.3.1 最优化算法结构

下降算法的两种方式

在这里插入图片描述
一个是先确定大小，再确定方向——信赖域
一个是先确定方向，再确定步长——最速、共轭、牛顿

算法的评价指标

在这里插入图片描述

迭代的终止条件（三种）

在这里插入图片描述

上面三个结合一下

在这里插入图片描述

收敛速度

在这里插入图片描述

2.3.2 精确线搜索（步长）

精确线搜索和不精确先搜索，都是讨论步长的；牛顿法、最速下降和共轭梯度是讨论方向的
不精确用的更多

进退法、Fibonacci法、0.618法、二分法、牛顿法、三点两次插值法

进退法

在这里插入图片描述

Fibonacci法——三分法（不是平均分）

在这里插入图片描述

0.618法——Fibonacci的极限情况

在这里插入图片描述

这其中，matlab用了0.618和三点两次插值法

牛顿法

近似二次函数，逼近
在这里插入图片描述

三点两次插值

3点，就是三个方程，求二次函数的三个系数
在这里插入图片描述

比牛顿法而言，不需要导数、减少计算量、但是慢

在这里插入图片描述

精确线搜索和不精确线搜索的算法结构

在这里插入图片描述

2.3.3 不精确线搜索

在这里插入图片描述

Armijo-Goldstein准则

在这里插入图片描述

步长比L_B小，比L_A大

Wolfe-Powell准则

在这里插入图片描述

简单准则和回退法

在这里插入图片描述

2.4 无约束最优化问题的求解算法

2.4.1 最速下降法(梯度下降法)

在这里插入图片描述
范数就是标准，不同的标准有不同的人才

在这里插入图片描述

下面这几个主要是两类；一类是改变方向，一类是讨论步长，除了BB算法、随机梯度下降法是第二类，其他都是第一类

BB算法

在这里插入图片描述

次梯度下降法

在这里插入图片描述

随机梯度下降法与小批量随机梯度法

在这里插入图片描述

动量(Momentum)梯度法——惯性梯度法

在这里插入图片描述

Nesteroy Accelerated Gradient(NAG)——加速度梯度法

在这里插入图片描述

AdaGrad (Adaptive gradient)——自适应梯度法

学习率就是步长

什么是自适应？
在这里插入图片描述

2.4.2 共轭方向法和共轭梯度法

在这里插入图片描述
共轭的话，就是根据当前的梯度信息加上之前的梯度信息就是迭代方向。

2.4.3 牛顿法和拟牛顿法

牛顿法就是基于原本的负梯度方向之后乘上Hesse矩阵。

在这里插入图片描述

牛顿法的缺点

在这里插入图片描述

2.4.4 信赖域算法

在这里插入图片描述

2.4.5 Powell 方法

函数值构造，嗯，这个没看懂，老师也没细讲

在这里插入图片描述

2.5 优化约束问题的求解算法

2.5.1 单纯形算法(求解线性规划问题)

线性规划的数学模型

在这里插入图片描述

图解法

在这里插入图片描述

单纯形算法

这个在考点里面讲到了

大M法和两阶段法

这个老师没讲，沾了gpt的

在这里插入图片描述

线性规划的对偶理论

在这里插入图片描述

2.5.2 内点法(求解线性规划问题、非线性规划问题)

在这里插入图片描述

2.5.3 信赖域法(求解无约束最优化问题的牛顿型信赖域法、拟牛顿型信赖域法，求解约束优化问题的信赖域法)

之前在线搜索那边讲过

2.5.4 高斯牛顿法、LM方法(求解非线性方程组)

在4.6节讲到高斯牛顿法

在这里插入图片描述

2.5.5 起作用集方法、拉格朗日牛顿法、序列二次规划法

在这里插入图片描述

2.5.6 罚函数法、广义拉格朗日乘子法、交替方向乘子法(ADMM)

外罚函数法

从函数的外面，惩罚进可行域内
在这里插入图片描述

内罚函数法

从函数的里面，惩罚到可行域

有对数罚函数、倒数罚函数

广义拉格朗日乘子法

考点里面有

交替方向乘子法(Alternating Direction Method of Multipliers, ADMM)——大数据集会常用

思想：分批最优化

上面是传统的算法，下面就是近代开发的算法

2.5.7 多目标规划

在这里插入图片描述

评价函数法之线性加权法

在这里插入图片描述

评价函数法之平方和加权法/理想点法

在这里插入图片描述

评价函数法之极小-极大法

在这里插入图片描述

评价函数法之乘除法

在这里插入图片描述

2.5.8 智能优化(遗传算法等)

遗传算法——跳出局部最优（用概率增加多样性）

2.5.9 MATLAB优化工具箱

在这里插入图片描述

fminnunc——利用导数信息

锥规划不行，约束最优化fmincon（单纯形）

非线性最小二乘问题：高斯牛顿法
单纯形：边界寻优
内敛法：内罚外罚
智能算法：ga:遗传算法、particleswarm:粒子群算法、simulannealbnd:模拟退火算法

2.5.10 泛函极值

自变量是函数，泛函极值：最快的函数

在这里插入图片描述

约等于梯度为0

测地线，球面最短距离

三、考试

3.1 凸函数的性质

在这里插入图片描述

3.2 最优性条件

最优性条件这个东西呢，主要是一阶二阶的充分条件、必要条件。其实是函数的一阶or二阶泰勒展开；一阶二阶的充分条件，正常展开进行证明就行；但是一阶二阶的必要条件都是用反证法，所以也是通过假设之后，正常展开，发现矛盾，从而反证

在这里插入图片描述

3.3 广义拉格朗日乘子法

还是hjc老师写的证明写的好

在这里插入图片描述

3.4 最佳步长

不管是最速下降法、牛顿法、共轭梯度法；最佳补充公式都是这个；区别是这几个方法的方向是不一样的。

3.5 最速下降法、牛顿法、共轭梯度法

最速下降的方向就是负梯度方向；牛顿法的方法是负梯度方向乘上Hesse矩阵，也就是对于负梯度方向进行了偏移；共轭梯度就是不仅使用了当前负梯度方向，还使用了上一次迭代方向。

3.6 KKT条件（求KKT点，并判断是否为全局最优解）

无约束就是梯度为0；如果有约束的话，就是使用KKT条件；不等式约束都得变成小于等于0

3.7 互补松弛定理

对偶问题写法口诀：大同小异互颠倒；
互补松弛定理的应用技巧口诀（版权：我最亲爱的对象——yss）：对偶方程找不等号，原问题x找不等于0

3.8 单纯形表法

在这里插入图片描述

四、作业

4.1 牛顿法为何收敛速度快？

首先，牛顿法提取的是导数信息，导数信息比点所提供的信息要更多，因此一般情况下收敛速度会越快。其次，牛顿法是二次近似，也就是目标函数在该点通过泰勒近似为一个二次函数，能够精确找到这个二次函数的极小值点，理想情况下，能一次收敛到目标函数的极小值点。最后，牛顿法的方向是对负梯度方向一个偏移，这个偏移也就是利用二阶导数（Hessian矩阵），即乘上了负的Hessian矩阵，Hessian矩阵，使得牛顿法能够更准确地估计函数的局部行为。构造函数的极小值方向，因为二次函数的寻优效果好。

4.2 共轭方向法为何效率高？

共轭梯度方向，只与上一次搜送方向有关；一定条件下，精确线搜的PRP共轭梯度具有全局收敛性。共轭向量组构成基，共轭方向搜索相当于沿着坐标轴搜索，目标函数经过坐标变换没有耦合项。综上所述，共轭方向法之所以效率高，是因为它在保持收敛速度的同时，减少了计算量和存储需求，并且利用了共轭方向的特性来优化搜索过程。这些特性使得共轭方向法在许多优化问题中成为一种实用而有效的选择。

4.3 KKT 里的拉格朗日乘子是不是对偶问题的最优解？如果不是，什么条件下是对偶问题的最优解何时是 kkt 条件里的拉格朗日乘子？

不是，如果Slater条件成立，那么对偶问题的最优解是 kkt 条件里的拉格朗日乘子。总结来说，KKT条件中的拉格朗日乘子是原优化问题最优解的必要条件，它们与对偶问题的最优解相关联的条件是原问题和对偶问题都满足强对偶性，并且原问题是凸优化问题。在这种情况下，KKT条件中的拉格朗日乘子可以视为对偶问题的最优解。

4.4 从连续函数的范数和向量范数的相似性理解连续函数可以看成向量，这在求解泛函的最佳曲线时可以用传统的最优化方法求解。

通过将连续函数视为向量，我们可以利用向量空间中的理论和方法来解决函数空间中的问题。向量空间具有加法和数乘的封闭性，即任意两个向量的和与任意标量与向量的乘积仍然是该空间中的向量。同样，连续函数空间也是一个线性空间，其中两个连续函数的和与一个连续函数的标量倍仍然是连续函数。在向量空间中，最优化问题通常涉及寻找最小化或最大化某个目标函数的向量。在函数空间中，泛函的最优化问题涉及寻找最小化或最大化某个泛函的连续函数。

4.5 如何理解无约束最优化问题的一阶必要性条件？

梯度的定义是，函数值增加最快的。负梯度，就是减小最快的方向。如果一个点是局部最优解，那么就不会在附近找到比这个点还要小的点，即无法找到下降方向，即梯度为0，即线性主部为0。无约束最优化问题的一阶必要性条件是梯度为零，这是函数在某点取得极值的必要条件，但不是充分条件。在实际应用中，我们通常需要结合二阶条件或其他分析方法来确定极值点。

4.6 区别高斯牛顿法、拉格朗日牛顿法

牛顿法，就是搜索方向是负梯度乘上负的Hessian矩阵并且拟合二次。高斯牛顿法就是通过最小二乘法，利用一阶泰勒展开近似目标函数，并使用雅可比矩阵近似Hessian矩阵来迭代求解。拉格朗日牛顿法是通过拉格朗日乘子法，利用拉格朗日乘数法将约束整合到目标函数中，然后使用牛顿法求解。

4.7 强对偶下，从 KKT 条件推线性规划问题的互补松弛性。

在这里插入图片描述

4.8 利用对偶问题的定义推线性规划问题的对偶问题

在这里插入图片描述

4.9 推导在 2 范数下，最速下降法中负梯度方向是使得函数下降速度最快的方向，在椭球范数下，牛顿方向是使得函数值下降速度最快的方向.

在这里插入图片描述

4.10 区分差分、微分、泛函的变分

差分是离散数学中的概念，用于描述函数在离散点上的变化，而微分是微积分中的概念，用于描述函数在某一点处的瞬时变化率。差分和微分都是针对函数的，而泛函的变分是针对泛函的，泛函是函数的函数，即它将一个函数映射到一个实数。差分和微分都是线性近似，而泛函的变分是非线性近似，因为泛函的变分涉及到函数的增量，而函数的增量可以是任意的。

4.11 如何理解什么是真正的约束优化问题

就是和无约束优化问题比起来，就是作用域不同，作用域是否存在最优解，如果作用域中存在最优解，此时问题就是无约束问题，如果最优解不在作用域上，此时才为真正的约束优化问题。无约束就是梯度为0，约束就是使用KKT。因为，我们跟倾向于无约束问题，所以有时候约束问题也可以使用拉格朗日乘子法变成无约束问题进行求解。