如果下面图片出不来请到https://www.bilibili.com/read/cv248864，都是我写的

一维搜索对函数的一个要求，不能是有多个极小值的情况，是单峰函数即可，函数没有要求可导和连续，函数只需要满足有一个极小点。

一维搜索缩小区间的一个基本原理

图中解释的很清楚，我就不再多说

1 二分法

每次需要新算两个点

这一次的区间长度和上一次区间长度的关系图中给出来了。

举几个例子

2 等分法

2.1三点等分

每次计算2个

从区间长度关系上我们看出这种方法效率是没有二分法高的，或者说区间收敛速度没有二分法快。

2.2 四等分法

第一次算3个，然后每次算2个

首先我们看到区间长度收缩速度比3等分快很多。

下面来解释为什么只有第一次需要计算新的2个点的值，后面都是一个点，如图，假设最左边是a右边是b，最后确定的区间不管是(a,x2),(x1,x3)还是(x2,b)，这些区间的中点値都已经计算过了。

3 斐波那契搜索

来细看一下原理，最后一轮这种方法用二分法搜索：

往上面推一轮，下图里Ln-2上画O和×的地方是上面最后一轮二分法选的点。上面Ln-1上的×是下面平移上去的。然后为了每次只算一个点，我们新算的点就取×向右移ε的位置。并且新的点和×在Ln-1上是对称的，因为Ln-1=(Ln-2+ε)/2根据O和×的对称性得出Ln=Ln-2-Ln-1=(Ln-2-ε)/2=Ln-1/2-ε。

按照这种方法一直算下去，

看到是有斐波那契数列的通项在里面的。

下面是斐波那契搜索步骤，

第一步是定初始区间和区间长度

第二步必须先知道ε和n，n是要事先计算出来的，然后我们才能知道L2

和前面方法不同的是，斐波那契搜索是先确定区间长度才确定点的位置。

第三步，按照缩小区间基本原理，比较选得点的函数值大小，选一个区间，然后对称着选一个区间，然后知道点，然后就循环，直到n次

这个n和最后区间长度是有关的，也就是区间精度

实际用的时候，

举一个例题吧

要求最后精度Ln<=0.03L1，算到1/34<0.03满足条件，往下计算即可，最后精度一定满足要求。最后结果

这种方法区间缩小的速度还是太小，收缩太慢。

总结一下，每次取斐波那契前一项比后一项的位置和对称位置，第一次算2次，随后每次计算一次,应用的时候ε通常为0 ，应用的时候跟斐波那契数列有关，斐波那契fn-1除以fn从0.5逐渐增大，极限是根5-1的一半即0.618，需要事先指定精度，精度换了如果按照严格算法流程需要重新计算，算一个新的迭代次数，当然也可以在区间任选点进行搜索，但无法事先知道迭代次数，同等精度下计算量小，但必须事先知道精度才能按照精度指定的迭代次数迭代到精度区间。

下面再说一下对称

x,y就是对称的

4 黄金分割算法

上面推导过程其实不是很难，

原理是希望每一轮只计算一个新的点的条件下新的区间和原来区间长度之比不变。这个比值求出来是0.618，所以相比于斐波那契，黄金分割区间长度减小慢一些，算相同个点时效率低一些，但不需要事先指定精度（效率高低是按照计算相同点数时区间收敛速度的大小）。

如果要计算精确解，需要迭代次数太多有时候只需要快速找到一个粗略的值多元优化时先每一个都按照二次插值法估计出最优解二次插值就是要找三个点求出一个近似的二次函数而已。这个应用只要是求快。

下面来看一下二次插值和原来函数的区别

举个例子

上面的lamda帽是二次函数插值的结果，lamda*是精确结果，二次函数很快就能逼近一个粗略的值。

下面介绍需要用到导数的方法

牛顿法

是梯度。

是海森阵的逆矩阵，

上面说的是结论，如果海森阵正定，还有函数是严格凸的话，算法保证会收敛。我默认你们知道正定和严格凸是什么，这是数学基础。

f（x）是二次函数是海森阵是常数阵，只需要计算梯度，基于这一点，可以把高次函数近似为二次函数，这可以用泰勒展开计算到二阶，略去高阶项。

总结一下：将牛顿法中函数换为一阶导数，极值点一阶导数为0，多元情况用到海森阵逆矩阵和梯度，被优化函数二阶可微每一步都需要计算海森阵，函数如果不是严格凸，结果与初始点有关，可能会发散，有很多局部最小值时可能发散二次函数海森阵的逆为常数矩阵，比较好计算，再很小范围内，由泰勒展开可以知道可以近似为二次函数，二次函数用牛顿法可以一步得到最优解那么我们就想是不是也可以用割线法来计算，就不用计算海森阵的逆了。

无约束优化

梯度算法

只能找到局部最优解，思想其实很简单。其实确定了下降的方向，即梯度，就可以看做一个一元问题。

观察上上个图，就相当于是在一群山之间下山，你有一个出发点(x0,y0),朝着梯度方向走若干距离，到达一个新的点(x1,y1)依此类推，称为逐次梯度下降法。我们要解决的问题是走多长，能保证收敛吗？以多快的速度收敛。

梯度方向

下面就是说为什么要选梯度方向作为下降方向，而不是其他方向，但是这个解释不够详细，了解就行

我们希望每个新的点都比原来的点的函数值小，并且希望下降大越好。ds是增量，有表达式可以求。增量其实就是比如说(x0,y0)和(x1,y1)之间的欧式距离，就是新的位置和原来的位置之间的距离。

这张图主要是说明按照梯度方向函数值确实可以减小

上面主要是说梯度是最好的方向，走距离相同时，离地平线最近，这个方向就好。

梯度下降方法不能在有限步内达到最优解，尽管它一定收敛的。但是也会有达到的情况，比如等高线是圆形

椭圆就不行。

梯度算法按照下面式子，注意k<0,我们其实是沿着负梯度方向下降的

离散化后，当k足够小，是等价的

k太大，步子太大，会越过最优值，反而会更差，所以k多大才好呢？

下面就引出了最优梯度下降算法

方向已经确定了，下面就是一维优化问题，优化对象就是这个步长k

注意未知量是k，因为已经选定了一个点，方向就是负梯度方向，我们其实是把高维优化问题变为一维了，选定起始点，沿着起始点的负梯度方向，先做一次步长的优化，然后到下一个点也是如此。

二次问题有以下推导

例子

对于一般的函数（泰勒展开到二阶时）

下面是有关收敛速度的定义，x*是最优解，就是说离最优解的距离是线性减小的

如果函数有多个极值点，收敛的结果与初值有关系，梯度下降只能保证收敛到极小值点（如果问题是求极小值的话），无法保证收敛到全局最小，因为梯度算法到了极小值点就走不动了

对于最优梯度方法，有一个结论：连续的两次搜索方向是正交的，证明如下

这种图都是笔者自己在公式编辑器里敲的

通常的做法是，先用二次插值快速找到一个比较粗略的解，然后再按照梯度下降去做，不然初始点选得离最优解太远，梯度下降步长小，太慢。

还有，二次插值是迅速接近最优解的方法，如果步长太小，结合泰勒展开到二次会比较快，步长太小的表现是函数值变化太小，这个时候其实离最优解已经很近了。

二阶收敛算法

1共轭梯度下降法

都是比梯度下降法快的

首先来研究二次函数

A可以写成对称的，如果不对称也可以化为对称的。举个例子

就是说如果(u,Av)=0那么我们说u和v这两个列向量是共轭的。A是单位阵的话就是正交。

如果A正定的话，我们是肯定可以找到一系列组线性无关的u,v的，这就是个结论。这些共轭的向量就是我们要拿来作为搜索方向的。

下面就是证明，共轭梯度是二阶收敛的

先说一下二阶收敛的概念，如果可以保证在有限步内一定可以找到一个二次函数的最优解，那么这个算法就是二阶收敛的。

这个lamda是通过最优梯度来确定的，结果上面也有，上面证明过程中用到了一个线性代数的知识，在hence的第二行到第三行

我们看到有限步的步数最多就是变量的维数，因为一个n维向量最多可以由n个线性无关的列向量表示，最多就是n个比如一个n*n的单位阵，n列就是线性无关的，这里不再细讲，事实上是n维空间是不存在n+1个线性无关的列向量的，都是线性代数知识。这里的初始点可以随便选，共轭的列向量的顺序不影响结果，也就是先按哪个共轭方向搜索，后按哪个方向没有关系。一个二次例子

不是二次的我们一样可以作泰勒展开到二阶（一般都会符合泰勒展开到二阶的条件的），然后用海森阵当作A去计算，但是就不一定可以找到精确的最优解，因为普通函数不像我们上面证明过的二次函数了。注意这里说的最优解都是极小值而已，可能会收敛到局部最小值。最优化算法是不保证收敛到全局最优的，不像笔者另一篇文章的群优化算法，只要参数设置合适，是一定保证收敛到全局最优解的。

2共轭方向算法

上一个算法有的时候共轭方向不是那么好找的，因为要满足（u,Av）=0。下面要介绍一种产生共轭方向的方法

上图就是步骤，n就是变量的维数，我们每一次的步长lamda都是按照最优梯度法来计算的，并且注意我们每次除了负梯度以外，还加上了一个额外的项，是可以证明这些方向是共轭的，虽然视频里没有证明，

截图里的上标i都有些模糊，是因为原视频就只有这点清晰度，原谅笔者不想再用公式编辑器写一遍。看例子

这种FR方法每次都需要计算梯度信息，需要计算n次，这个计算量还是很大的。

下面一种方法不需要计算梯度

Powell方法

这种方法基本原理就是选两个点，按照相同方向v去做一维最优梯度优化算法，得到x1,x2两个点，则x2-x1这个向量和v方向是关于二次函数的A或者一般函数的H是互相共轭的。

下面是算法步骤

第一步是预先给定n个互相线性无关向量，n还是变量的维数，这很好找比如单位向量，选一个初始点x0，用上面的n个向量作为搜索方向，按照最优梯度下降算法优化步长，直到搜索n次到xn。（前n次）

然后替换搜索方向，就像图中写的两行，本来是v1，v2，v3，v4......vn，变为v2,v3,v4......xn-x0。

再按照xn-x0这个方向用最优梯度方法计算一步（第n+1次）。然后替换x0为新的点。每一轮是计算了n+1次。

然后重复搜索，直到满足条件，精度足够。

如果是二元的二次函数的话，两轮轮我们就已经得到了关于共轭的两个方向。图中的u1，u2，但是我们看到计算的内积不是0，这是因为计算机计算误差。

如果n元二次函数并且A正定，n轮之后产生n个新的方向，这n个向量是关于A共轭的。

变尺度算法

x*是最优解，x0距离x*足够近的话我们就把梯度泰勒展开，这个看得清的我就不想载重复打了

由于x*是极小点那么梯度是0，海森阵正定（一定可逆），那么可以化为

这就给了我们一种方法，不用最优梯度算法去优化步长而是直接用

作为步长，但是函数次数大于2时，你不知道x*是多少啊，你没办法去算H（x*），还有一种情况是函数次数比较低，海森阵是常数。比如对于二次函数海森阵是常数阵，所以可以用

一步就能到最优解，很快。

我们能不能搞出来这个海森阵的逆呢？

我们可以通过迭代一步一步去逼近这个海森阵。这就是

FP变尺度算法

视频里图不清楚，我来写一下

H0取任意正定阵，后面的H全是正定的

H0取任意正定阵，后面的H全是正定的

如果是二次函数，迭代两轮H就已经是H（x*）的逆了。

下面是几个比较有意思的性质，和算法本身没关系

X是非零任意列向量。

这里扩展了上面的结论，实际应用中没什么用，只是做理论证明。

有约束优化

拉格朗日乘数法，等式约束

注意

这些条件是对于拉格朗日函数来说，如果拉格朗日函数的最优解存在，这些是必要条件。也就是说最优解带进去一定成立。

约束条件的数要小于变量个数

但是要说明的是lamda可能不存在

例子

画等高线图

容易知道X=1，y=0时有最优解，但是

把最优解带进去，看出来最优解满足不了偏导的等式，因为把X=1，y=0带入偏G除以偏X，他的秩是0。也就是说拉格朗日函数是没有最优解的。这些求偏导等于0都是如果拉格朗日函数有最优解的必要条件，不是原问题，也就是带约束的优化问题的必要条件。就像上例中原问题最优解带入是不成立的。

不等式约束优化问题

不等式约束都可以化为形式

<=可以两边同乘-1，就变为>=，求最大值可以加个-就是求最小值。

为了把不等式约束转化为等式约束，我们引入松弛变量θj满足

然后就可以用拉格朗日乘数法

这里要说一点问题，有人会不会认为θj是x的函数，求偏导怎么没求啊？

我认为在L里θ是和x无关的，它们是不同的变量，只有求极值时，对x求偏导=0这个必要条件时，约束才起作用，这时候θ才与x有关系，不然L里还写那一项干嘛，直接写0得了，因为它就等于0啊，所以说θ真正和x有关系只发生在求偏导并且按照极值的必要条件让偏导=0时。L函数和原约束问题只有在最优解性质才一样，虽然λ不一定存在。

还可以这么说，原问题的约束在拉格朗日函数极值的必要条件里已经有了，你在求解的时候是一定会用到这些必要条件的，所以没有必要在拉格朗日函数里加上约束条件，因为这些约束在极值必要性条件里有了。理解这点很重要。

我们看到第三个式子有三种情况。

λ=0或者θ=0或者都为0，下面就是分析这几种情况。

另外笔者想说明一点，有的时候不等式就能解决的问题，就不用拉格朗日了，不是我觉得不是杀鸡用牛刀的问题，而是速度的问题。

笔者想说的是不要学了高数干什么都是见面就积分求导，不动脑子思考。你可以试试，绝对比拉格朗日函数快。

KKT方法

f和g是可导的。我们用的是类拉格朗日函数。这样做主要是少引入了未知数个数，因为对于不等式约束来说，需要加入松弛变量。那么拉格朗日函数里变量的个数就是大于n+m的，不等式约束越多，松弛变量越多，我们用KKT方法最后只有n+m个变量，没有松弛变量。

KKT方法第三个条件其实就是普通的拉格朗日引人松弛变量的结果，第四项对λ的要求是因为求min而且g小于等于0，同样情况下λ大于等于0时,L更小。其实不知道你们有没有学过运筹学，感觉和单纯形法最后要求的检验数大于0的思想很像，有时间笔者写一个关于运筹学的文章吧。

需要说明的话，这些条件也都是必要条件，如果f和g函数都是凸函数的话，就是充要条件。

要注意min和约束条件的<=，不是的话转化过来即可。

下面介绍的是约束梯度优化算法

基本思想是先按照负梯度方向走，如果走出了边界，那么我们就按照破坏的约束条件的梯度走回去。举个例子

需要注意的是如果约束条件是>=时，回去的时候是按照约束条件的梯度条件。小于等于的时候就是按照负梯度方向。

这个图表示的是一个优化的过程，是之字形，阴影是可行区域从上向下看是优化的过程。但是这种方法效率太低，于是就改进了搜索方向，如果在界外的话不仅要考虑回去，还要兼顾梯度下降方向。

如果在界内，就按照梯度下降方法，可以用最优梯度下降。出了边界，搜索方向就是负梯度方向和边界函数梯度的合成。

看出来效率就比上面高很多。

这里还要说的是如果选得初始点不同，最后收敛的结果也不一样。下图的三角形，在三角形ABC里会收敛到（2，0）而三角形ABD里会收敛（0，3）。所以在应用的时候，一般会选很多个点，比较然后选择最后的最优解，所以笔者就想可以和遗传算法结合，因为遗传算法迭代速度太慢，效率太低，结合梯度算法效率就很高。

还是要注意约束条件的大于还是小于对边界函数正梯度还是负梯度的对应关系。可以这么想，如果g大于0，如果出去了，那么说明g<0,需要g变大，如果导数是正的，我们就应该按照这个方向才能进到可行区域，如果g小于0，如果出去了，那么说明g>0,需要g变小，如果导数是正的，我们就应该按照这个方向的负方向才能进到可行区域。

还有一种思路

先按照无约束优化问题求解，求出最优解后，如果最优解满足边界条件，那就停止，最优解在界外时，直接去边界上找，边界不一定是线性的，是线性可以用一维搜索方法，边界非线性，我们往往用可行方向法，想了解其他方法的戳https://rc.mbd.baidu.com/5fdxgnx。

可行方向法

如果在边界里面，存在一个步长使下一个点还在边界内。如果在边界上，我们希望下一步还在边界内，根据边界条件的泰勒展开，又根据边界小于等于0的要求

我们想下一个点在界内就要求

如果边界是大于等于0上面也是大于号。

就是这么一个思想来寻找可行方向，方法有很多，常用的是线性规划

下一步方向应是下降方向，是线性规划中第一个约束条件，

也是可行方向，即第二个约束条件，

这两个约束都可以用泰勒展开一阶形式得到，求出x0最大的意义就是满足下降最大时也满足边界条件，尽量离边界远，同时满足。x0=0，则已经是最优解，不是则继续算，需要注意的是我认为可行方向步长已经确定是1了。可行方向其实是基于基本按照边界方向来搜索，线性边界的话搜索方向一定是边界方向，非线性边界略有偏差。x0=0时其实也就在边界上。线性规划如果用不了图解法，一般用单纯形法求解，有时间会介绍。

下面是步骤