伺服控制系统常⽤参数寻优算法
参数寻优——转⾃
参数寻优背景
参数寻优问题随处可见，举⼏个例⼦。
1. ⼩明假期结束回校，可以坐⽕车，可以坐汽车，可以坐飞机，还可以⾛着，⼩明从哪条路去学校更好呢？
2. 简单的数学，⼀元⼆次⽅程求根。
3. ⾼深的数学，七桥问题，怎么才能通过所有的桥各⾃⼀次⾛回七点所在的岸边。
4. 机器学习中，求代价函数在约束条件下的最优解问题。
其上四个问题，均是参数寻优问题。问题1中，⼩明可以通过试探法将所有的⽅式计算⼀下时间成本，经济成本，舒适程度，来选择⼀个性价⽐最合适的返校⽅式。问题2中，可以通过⼀元⼆次⽅程的求根公式直接求出解来。问题3中，七桥问题则是典型的图论问题，通过抽象为图，推理得出该题⽆解。问题4中，机器学习则是数值分析中⽅程的迭代解法。
本⽂⽬标
本⽂主要讲清楚梯度下降法、⽜顿下降法是如何想到并引⼊参数寻优中的，以及他们为什么有效。
参数寻优的迭代法的基本原理
图1 ⼀维的⼆阶代价函数展⽰
图2 ⼆维的⼆阶代价函数展⽰
通过代价函数的形状，我们很⾃然地想到，如果我们从任意⼀个参数点出发，是否可以找到刚好是让代价下降的⽅向，沿着这个⽅向，⼀定能找到当前的极值点。
于是，迭代法参数寻优的基本原理有了：沿着（代价）函数下降的⽅向寻找参数，能够找到极值点。
梯度下降法的引⼊
在我们已经学过的数学知识中，导数和⽅向导数是能找到函数变化⽅向的。导数表⽰了曲线的斜率（倾斜度），⽅向导数表⽰了曲⾯沿着任意⽅向的斜率（倾斜度）。⼀维时，导数就⾜够了。但多维时，就需要借助⽅向导数了，⽽我们更希望能找到变化率最⼤的⽅向。因此，多维下借⽤⽅向导数变化最⼤的情况：梯度，梯度的⽅向是函数某点增长最快的⽅向，梯度的⼤⼩是该点的最⼤变化率。
微格教学
捉迷藏怎么写 三维下，推导⽅向导数与梯度的关系
⽅向导数：
∂f∂l=∂f∂x∗cos(α)+∂f∂y∗cos(β)+∂f∂z∗cos(γ)
⽅向：l=(cos(α),cos(β),cos(γ))梦见掉发
梯度：Grad=(∂f∂x,∂f∂x,∂f∂x)
∂f∂l=Grad∗l
∂f∂l=|Grad|∗1∗cos(Grad,l)
大三元镜头 当两者⽅向相同时，cos(Grad,l)=1，∂f∂l 取得最⼤值|Grad| 。因此，梯度表⽰了函数增长最快的⽅向，和最⼤的增长率。
⽜顿下降法的引⼊
⽜顿法求解f(x)=0
在讲⽜顿下降法之前，先讲⼀下 f(x)=0 的求解。将 f(x) 在 x0 处进⾏⼀阶泰勒展开：
图 3，⽜顿法求解 f(x)=0
f(x)=f(x0)+f′(x0)1!(x−x0)
则得到f(x0)+f′(x0)(x−x0)=0
解得x=x0−f(x0)f′(x0)=x1
从图中可以看出，x1⽐x0 更靠近真实解。如果接下来在x1 处⼀阶泰勒展开，会得到更靠近真实解的x2 ，以此类推：
xn+1=xn−f(xn)f′(xn)
⽜顿法具有天然的迭代性，可以不断逼近真实解。
⽜顿下降法
那么⽜顿下降法是如何引⼊的呢？求解最优解 minx[Cost(x)] ，等价于找到 x 满⾜ f′(x)=0 。对于 f′(x)=0 的求解，就可以⽤上⾯的⽜顿法来不断逼近真实解了。
对 f′(x) 在 x0 处⼀阶泰勒展开。
f′(x)=f′(x0)+(x−x0)∗f′′(x0)
令 f′(x)=0
得 x=x0−f′(x0)f′′(x0)=x1
xn+1=xn−f′(xn)f′′(xn)
⽜顿下降法的⼏何意义
⼀阶导数决定的函数当前是否增减，⼆阶则决定这当时是否凹凸。⽜顿下降法⽤⼆次曲⾯去拟合当前所处位置的局部曲⾯，下降⽅向上的选择不仅考虑了坡度是否⾜够⼤，⽽且考虑了⾛了这⼀步之后，坡度是否会变得更⼤。所以，⽜顿下降法⽐梯度下降法看得更远，能更快
地⾛到局部的最底部。
⽜顿下降法的局限性
（1）收敛性对初始点的选取依赖性很⼤；
（2）每次迭代都要计算Hessian矩阵（⼆阶导数），计算量⼤；
（3）要求⼆阶可微分，计算Dk时，⽅程组有时⾮正定或者病态，⽆法求解Dk或者Dk不是下降⽅向。
阻尼⽜顿法的引⼊
对⽜顿法局限性的不同改进，导致阻尼⽜顿法和拟⽜顿法的出现。
针对⽜顿法，有时得到的⽜顿⽅向不是下降的情况，提出了阻尼⽜顿法。上升的情况，⽐如 f′(x)<0,f′′(x)<0 。
解决⽅法是：在新的迭代之前，找到下降⽅向，且是下降最⼤的⽅向。
（1）先确定最优解的所在区间[a, b]。
（2）⼀维搜索。在解区间[a, b]内搜索使得⽬标函数下降最⼤的点。
其中（1）可以⽤进退法，找到三个点，使得 f(a−h),f(a),f(a+h) 满⾜⼤⼩⼤的规律即可。
⼀维搜索⽅法主要分为试探法和插值法，试探法有黄⾦分割法、fibonacci法、平分法、格点法等；插值法有⽜顿法、抛物线法等。判断解两边值的⼤⼩关系或者求导为0。
剩下的部分就是跟⽜顿下降法⼀样了。(具体实现看前⾯的博客)
拟⽜顿法的引⼊
针对⽜顿下降法hessian矩阵计算量⼤，需要正定矩阵的局限性，提出了拟⽜顿法，拟⽜顿法的核⼼是对Hessian矩阵的逆的估计。
根据不同的估计⽅法，分为DFP和BFGS。
图 4 DFP
师生情作文
图 5 BFGS
机器学习的⼀个重要组成部分是如何寻找最优参数解。本⽂就常见寻优⽅法进⾏总结，并给出简单python2.7实现，可能⽂章有点长，⼤家耐⼼些。
寻找最优参数解，就是在⼀块参数区域上，去找到满⾜约束条件的那组参数。形象描述，⽐如代价函数是个碗状的，那我们就是去找最底部（代价最⼩）的那个地⽅的对应的参数值作为最优解。那么，如何找到那个底部的最优参数解呢，如何由⼀个初始值，⼀步⼀步地接近该最优解呢。寻优⽅法，提供了靠近最优解的⽅法，其中涉及到的核⼼点，⽆外乎两点：靠近最优解的⽅向和步幅（每步的长度）。
最优化，分为线性最优化理论和⾮线性最优化理论。其中线性最优化⼜称线性规划。⽬标函数和约束条件的表达是线性的， Y=aX ；⾮线性最优化理论，是⾮线性的。其中包括梯度法，⽜顿法，拟⽜顿法（DFP/BFGS），约束变尺度（SQP），Lagrange乘⼦法，信赖域法等。
算法原理及简单推导
最速下降法（梯度下降法）
借助梯度，找到下降最快的⽅向，⼤⼩为最⼤变化率。
θnew=θold−α∗Gradient
梯度：是⽅向导数中，变化最⼤的那个⽅向导数。
梯度⽅向：标量场中增长最快的⽅向。
梯度⼤⼩：最⼤变化率。
更新：沿着梯度的负向，更新参数（靠近最优解）。
*********************************************
Algorithm:GradientDescent
Input:x−Data;y−Label;α−调节步幅;θ0;Iternum;
Output:θoptimal
Process:
1. Initial θ=θ0
2. While Loop<Iternum
H=f(x,θ)；模型函数H
催促的近义词是什么
Compute Gradient According to f(x,θ)
Update θ:=θ−α∗Gradient
Loop=Loop+1
3. Return θ
*********************************************
梯度下降法
优点：⽅便直观，便于理解。
缺点：下降速度慢，有时参数会震荡在最优解附近⽆法终⽌。
⽜顿下降法
⽜顿下降法，是通过泰勒展开到⼆阶，推到出参数更新公式的。
f(x+Δ(x))≈f(x)+f′(x)∗Δ(x)+12∗f′′(x)∗Δ2(x)
上式等价于 f′(x)+f′′(x)∗Δ=0孩子早餐吃什么
从⽽得到更新公式:
xnew−xold=−f′(x)f′′(x)=−[f′′(x)]−1∗f′(x)
调整了参数更新的⽅向和⼤⼩（⽜顿⽅向）。
*********************************************
Algorithm:Newton Descent
Input:x−Data;y−label;θ0;ϵ−终⽌条件;
Ouput:θoptimal
Process:
1. Initial θ=θ0
2. Compute f′(x,θ)
if|f′(x),θ)|⩽ϵ
return θoptimal=θ
el
Compute H=f′′(x,θ)
Dk=−[H]−1∗f′(x,θ)
Update θ:=θ+Dk
3. Return step 2
*********************************************
⽜顿下降法
优点：对于正定⼆次函数，迭代⼀次，就可以得到极⼩值点。下降的⽬的性更强。
黄色性 缺点：要求⼆阶可微分；收敛性对初始点的选取依赖性很⼤；每次迭代都要计算Hessian矩阵，计算量⼤；计算Dk时，⽅程组有时奇异或者病态，⽆法求解Dk或者Dk不是下降⽅向。
阻尼⽜顿法
