二阶优化
之前介绍的一阶的优化方法，能够找到迭代的方向，但是往往不能决定迭代的步长，本文介绍的牛顿相关方法能一定程度上解决这个问题。
牛顿法
首先我们来看看牛顿法的推导过程，
对于函数f(x)在$x_{k}$处进行二阶泰勒展开。
$$
f(x)=f(x_{k})+f'(x_{k})(x-x_{k})+\frac{1}{2}f''(x_{k})(x-x_{k})^{2}
$$
前两阶求导等于0
$$\begin{gathered}f'(x_{k})+(x-x_{k})f''(x_{k})=0 \\
x_{n+1} = x_{n}+\frac{f'(x_{k})}{f''(x_{k})}\end{gathered}$$
迭代过程如下图。
从上面的迭代过程能够看出，对于底部碗装的线性，其效果会十分的差。如前两种线性。
割线法
通过上面的讲解，我们知道牛顿法是要求有二阶导数的，但是并不是所有的函数都存在二阶导数， 割线法主要就是解决这个问题的。
$$
f''(x_{k})=\frac{f'(x_{k})-f''(x_{k-1})}{x_{k}-x_{k-1}}
$$
这样就能解决没有二阶导数的函数的牛顿法的使用上。
拟牛顿法
拟牛顿法也是解决类似的问题， 但是在矩阵上近似黑塞矩阵，这里就不做进一步的讲解啦。
约束优化
接下来咱们来介绍约束优化，什么样的优化是约束优化呢？ 其实就是咱们原有的优化函数上加上约束条件而已。
$$\begin{gathered}min\ f(x) \\
s.t. \ h(x)=0\end{gathered}$$
h(x)可以是等式也可以是不等式。 实际上就是在约束范围内找到最优解。
其方法也是尽可能的消除掉约束，从而变成一个正常的优化问题。
消除转换
例如下面这个问题。
$$\begin{gathered}min\ xsin(x) \\
s.t. \ \ \ 2<x<6\end{gathered}$$
可以通过如下的转换
$$
x=t_{2,6}(x)=\frac{2+6}{2}+\frac{6-2}{2} \frac{2x}{1+x^{2}}
$$
通过上面的转换，原来的公式就变成了
$$\begin{gathered}min\ \ t_{2,6}(x)sin(t_{2,6}(x)) \\
min\ \ [4+2( \frac{2x}{1+x^{2}})] sin[4+2( \frac{2x}{1+x^{2}})]\end{gathered}$$
这样就变成了一个无约束问题。
拉格朗日乘法
拉格朗日乘法主要是解决受限约束的函数是等式的情况下，如下公式。
$$\begin{gathered}min\ \ f(x)\\
s.t. \ \ h(x)=0\end{gathered}$$
利用拉格朗日乘法计算f的等高线与h(x)=0的等高线对齐的位置。由于函数在某个点的梯度垂直于该函数通过该店的等高线，我们知道h的梯度将垂直于等高线h(x)=0,因此需要找到f的梯度和h的梯度在哪里对齐。
$$
\nabla f(x)=\lambda \nabla h(x)
$$
其拉格朗日函数为
$$
L(x, \lambda )=f(x)-\lambda h(x)
$$
举例
看下面这个例子。求解如下的公式
$$\begin{gathered}min\ \ -exp(-(x_{1}x_{2}-\frac{3}{2})^{2}-(x_{2}-\frac{3}{2})^{2}) \\
s.t.\ \ x_{1}-x_{2}^{2}=0\end{gathered}$$
使用拉格朗日法
$$\begin{gathered}L(x_{1},x_{2},\lambda)=-exp(-(x_{1}x_{2}-\frac{3}{2})^{2}-(x_{2}-\frac{3}{2})^{2})-\lambda(x_{1}-x_{2}^{2}) \\
\frac{\partial L}{\partial x_{1}}=2x_{2} f(x)(\frac{3}{2}-x_{1}x_{2})-\lambda \\
\frac{\partial L}{\partial x_{2}}=2\lambda x_{2}+f(x)(-2x_{1}(x_{1}x_{2}-\frac{3}{2})-2(x_{2}-\frac{3}{2})) \\
\frac{\partial L}{\partial \lambda}=x_{2}^{2}-x_{1}\end{gathered}$$
分别令上面的导数为0，就能求出相应的x
惩罚方法
通过向目标函数增加惩罚项，可以使用惩罚方法将约束问题转化为非约束问题。
$$\begin{gathered}min \ \ f(x) \\
s.t.\\
f(x)<0 \\
h(x)=0\end{gathered}$$
一种简单的惩罚方法是计算违反的约束方程数量
$$
P_{count}(x)=\sum g_{i}(x)>0 + \sum (h_{i}(x) \neq 0)
$$
那么新的方程就是
$$
min\ \ f(x)+a P_{count}(x)
$$
a是乘法幅度。 惩罚方法从初始点x和一个很小的a开始，求解无约束优化方程。然后得到一个点作为另一个优化的起点，并增加惩罚，直到得到可行结果，或者达到了最大迭代次数。