二阶优化

之前介绍的一阶的优化方法，能够找到迭代的方向，但是往往不能决定迭代的步长，本文介绍的牛顿相关方法能一定程度上解决这个问题。

牛顿法

首先我们来看看牛顿法的推导过程，
对于函数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

$$f'(x_{k})+(x-x_{k})f''(x_{k})=0 \\ x_{n+1} = x_{n}+\frac{f'(x_{k})}{f''(x_{k})}$$

迭代过程如下图。

从上面的迭代过程能够看出，对于底部碗装的线性，其效果会十分的差。如前两种线性。

割线法

通过上面的讲解，我们知道牛顿法是要求有二阶导数的，但是并不是所有的函数都存在二阶导数， 割线法主要就是解决这个问题的。

$$f''(x_{k})=\frac{f'(x_{k})-f''(x_{k-1})}{x_{k}-x_{k-1}}$$

这样就能解决没有二阶导数的函数的牛顿法的使用上。

拟牛顿法

拟牛顿法也是解决类似的问题， 但是在矩阵上近似黑塞矩阵，这里就不做进一步的讲解啦。

约束优化

接下来咱们来介绍约束优化，什么样的优化是约束优化呢？ 其实就是咱们原有的优化函数上加上约束条件而已。

$$min\ f(x) \\ s.t. \ h(x)=0$$

h(x)可以是等式也可以是不等式。 实际上就是在约束范围内找到最优解。
其方法也是尽可能的消除掉约束，从而变成一个正常的优化问题。

消除转换

例如下面这个问题。

$$min\ xsin(x) \\ s.t. \ \ \ 2<x<6$$

可以通过如下的转换

$$x=t_{2,6}(x)=\frac{2+6}{2}+\frac{6-2}{2} \frac{2x}{1+x^{2}}$$

通过上面的转换，原来的公式就变成了

$$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}})]$$

这样就变成了一个无约束问题。

拉格朗日乘法

拉格朗日乘法主要是解决受限约束的函数是等式的情况下，如下公式。

$$min\ \ f(x)\\ s.t. \ \ h(x)=0$$

利用拉格朗日乘法计算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)$$

举例

看下面这个例子。求解如下的公式

$$min\ \ -exp(-(x_{1}x_{2}-\frac{3}{2})^{2}-(x_{2}-\frac{3}{2})^{2}) \\ s.t.\ \ x_{1}-x_{2}^{2}=0$$

使用拉格朗日法

$$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}$$

分别令上面的导数为0，就能求出相应的x

惩罚方法

通过向目标函数增加惩罚项，可以使用惩罚方法将约束问题转化为非约束问题。

$$min \ \ f(x) \\ s.t.\\ f(x)<0 \\ h(x)=0$$

一种简单的惩罚方法是计算违反的约束方程数量

$$P_{count}(x)=\sum g_{i}(x)>0 + \sum (h_{i}(x) \neq 0)$$

那么新的方程就是

$$min\ \ f(x)+a P_{count}(x)$$

a是乘法幅度。 惩罚方法从初始点x和一个很小的a开始，求解无约束优化方程。然后得到一个点作为另一个优化的起点，并增加惩罚，直到得到可行结果，或者达到了最大迭代次数。