程序员的数学【最优化】(三)

简介: 本文其实值属于:程序员的数学【AIoT阶段二】 的一部分内容,本篇把这部分内容单独截取出来,方便大家的观看,本文介绍 最优化

五、坐标下降法

🚩坐标下降法就是分治法的思想。

image.pngimage.png

六、最优化算法瓶颈

🚩前面梯度下降法,还有牛顿法求极值的依据都是f(xk)=0,而前面我们也说了函数在某一点的导数或梯度等于 0  就是驻点,它只是函数取得极值的必要条件,不是充分条件,也就是说无法推导出

image.png

所有我们前面介绍的数值优化算法,都会面临两个问题。

6.1 局部极值问题

🚩这个问题好歹是个局部极值,只不过不是全局极值,理论上我们要求全局最优解的话,我们要把所有极小值找出来,你可能要不断的去设置不同的初始迭代点,反复的求解让它收敛到不同的局部最小值,然后来比较谁最小来找到一个全局最小值。

48.png

6.2 鞍点问题

🚩前面我们说过一元函数x3函数,在坐标为 0  处它是驻点,但是它连局部最小值都不是,对应多元函数来说,我们称之为鞍点(既不是极大值点也不是极小值点的临界点,叫做鞍点)。严格定义是,在这一点它的Hessian 矩阵是不定的,既不正定也不负定,这样它就即不是极小值的点也不是极大值的点。

49.png

在物理上要广泛一些,指在一个方向是极大值,另一个方向是极小值的点。

50.png

七、凸优化问题

🚩前面我们说过数值优化面临两个问题,一个是局部极值问题,和鞍点问题,我们能不能避免这两个问题呢?

只要我们对优化问题进行限定就可以,这类问题有两个限定条件

1、优化变量的可行域必须是凸集

2、优化函数必须是个凸函数

同时满足这两个限定条件的问题,叫做凸优化问题,从而才有局部极小值进而全局极小值。

八、凸集

🚩凸集的定义:对于一个点的集合C有 x , y 它都是属于 C 里面的两个点,它们两点的连线中任何一点也是属于集合 C 的。例如立方体就是凸集。

image.png

它的意义在于,很多时候可行域就是欧式空间,那肯定是凸集。在凸集的前提下,才可以进行最优化问题求解。

九、凸函数

🚩凸函数在函数上任意找两点它们的连续就是割线上的值比对应的 f(x)的值要大

51.png

函数的二阶导数是和函数的凹凸性是有关系的,凹凸性怎么定义的?


先来做简单的介绍,这里先记住凸函数是向下凸的, 反正就是凹的,是否是凸函数可以通过二阶导数,如果二阶导数是大于 0 就是凸函数

52.png

如果一元函数,那么f(x)0就是凸函数。多元函数Hessian矩阵是半正定的,它就是凸函数;多元函数Hessian矩阵是正定的,它就是严格的凸函数。

image.png

十、凸优化表达形式

🚩凸优化的定义是目标函数是凸函数,可行域是个凸集,如果有这两个限定条件的话,局部最优解一定是全局最优解。

凸优化一般表达形式:

image.png

十一、拉格朗日乘子法

🚩高等数学和微积分的时候我相信大家都学过,用来求解等式约束下的极值问题的

image.png

拉格朗日乘子法,把对 x带约束条件的优化问题,转化为不带约束条件的优化问题

image.png

image.png

十二、KKT条件

🚩假设我们面对的是不等式条件约束优化问题,如下:

image.png

针对上式,显然是一个不等式约束最优化问题,不能再使用拉格朗日乘数法,因为拉格朗日乘数法是针对等式约束最优化问题。

拉格朗日乘数法的扩展,用来解决带不等式约束条件的一种理论结果:

image.png

约束条件为:

  • L(x,λ)=0
  • λ ≥ 0
  • λh(x)=0

上面条件就称为KKT 条件。

十三、拉格朗日对偶

🚩凸优化,非线性规划问题,甚至是运筹学里面的线性规划问题都会涉及这个概念,它的意义是把原始问题转化为另外一个问题来求解,但是转化之后的问题要容易求解一点,拉格朗日乘数法的扩展,用来解决既带等式约束条件,又带不等式约束条件的一种方法通过把原问题转换为对偶问题来求解,很多时候对偶问题比原问题更容易求解。

image.png

原始问题

image.png

我们定义对偶问题为(对上面方程的求解等效求解下面方程):

image.png

其实就是把 m i n 和 m a x  对调了一下,当然对应的变量也要变换。

image.png53.png







目录
相关文章
|
程序员
程序员的数学【最优化】(二)
本文其实值属于:程序员的数学【AIoT阶段二】 的一部分内容,本篇把这部分内容单独截取出来,方便大家的观看,本文介绍 最优化
245 0
程序员的数学【最优化】(二)
|
机器学习/深度学习 算法 数据挖掘
程序员的数学【最优化】(一)
本文其实值属于:程序员的数学【AIoT阶段二】 的一部分内容,本篇把这部分内容单独截取出来,方便大家的观看,本文介绍 最优化
214 0
程序员的数学【最优化】(一)
|
机器学习/深度学习 程序员
程序员的数学【微积分基础】(一)
本文其实值属于:程序员的数学【AIoT阶段二】 的一部分内容,本篇把这部分内容单独截取出来,方便大家的观看,本文介绍 微积分基础,微积分是公式推导的基础,如果你也关注我的专栏:西瓜书读书笔记,里面对公式进行详细推导的过程中,运用到了大量的 导数,积分,身为一名程序员,我们务必掌握一些必备的数学知识。
298 0
程序员的数学【微积分基础】(一)
|
机器学习/深度学习 程序员
程序员的数学【微积分基础】(二)
本文其实值属于:程序员的数学【AIoT阶段二】 的一部分内容,本篇把这部分内容单独截取出来,方便大家的观看,本文介绍 微积分基础,微积分是公式推导的基础,如果你也关注我的专栏:西瓜书读书笔记,里面对公式进行详细推导的过程中,运用到了大量的 导数,积分,身为一名程序员,我们务必掌握一些必备的数学知识。
245 0
程序员的数学【微积分基础】(二)
|
程序员
程序员的数学【概率论】(二)
本文其实值属于:程序员的数学【AIoT阶段二】 的一部分内容,本篇把这部分内容单独截取出来,方便大家的观看,本文介绍 概率论
238 0
程序员的数学【概率论】(二)
|
机器学习/深度学习 程序员
程序员的数学【概率论】(三)
本文其实值属于:程序员的数学【AIoT阶段二】 的一部分内容,本篇把这部分内容单独截取出来,方便大家的观看,本文介绍 概率论
147 0
程序员的数学【概率论】(三)
|
机器学习/深度学习 算法 数据挖掘
程序员的数学【概率论】(一)
本文其实值属于:程序员的数学【AIoT阶段二】 的一部分内容,本篇把这部分内容单独截取出来,方便大家的观看,本文介绍 概率论
282 0
程序员的数学【概率论】(一)
|
机器学习/深度学习 程序员
程序员的数学【线性代数基础】(三)
本文其实值属于:程序员的数学【AIoT阶段二】 的一部分内容,本篇把这部分内容单独截取出来,方便大家的观看,本文介绍 线性代数基础,在机器学习中经常会有矩阵、向量的定义以及计算,是公式定义、推导中必不可少的一部分内容,很多基础概念的定义中都用到了向量的概念,有关线性代数,
345 0
程序员的数学【线性代数基础】(三)
|
机器学习/深度学习 数据挖掘 程序员
程序员的数学【线性代数基础】(一)
本文其实值属于:程序员的数学【AIoT阶段二】 的一部分内容,本篇把这部分内容单独截取出来,方便大家的观看,本文介绍 线性代数基础,在机器学习中经常会有矩阵、向量的定义以及计算,是公式定义、推导中必不可少的一部分内容,很多基础概念的定义中都用到了向量的概念,有关线性代数,
368 0
程序员的数学【线性代数基础】(一)
|
设计模式 机器学习/深度学习 算法
数学,离一个程序员有多近?
for循环没算法快 1. for 循环实现 2. 算法逻辑实现 3. 耗时曲线对比 四、Java中的算法运用 1. HashMap的扰动函数 2. 斐波那契(Fibonacci)散列法 3. 梅森旋转算法(Mersenne twister) 五、程序员数学入门
259 0
数学,离一个程序员有多近?