无约束凸优化算法

本章涉及知识点

1、scipy库求解全局最优和局最优

2、多元函数的极值求解算法

3、牛顿迭代法算法

4、牛顿迭代法求解多元函数的驻点

在金融学和经济学中，凸优化起着非常重要的作用，而研究凸优化求解其极值是一个非常有趣的数学问题

我们用一个案例来研究无约束凸优化算法，假设有如下二元目标函数

目标函数

一、scipy库求解全局最优和局最优

我们先用numpy生成50个二维网格点即对应的f(x，y)

50个网格点和对应的函数值

画出f(x，y)的图像观察

案例多元函数图像

显然从图像上可以直观看出，函数存在多个局部极小值。我们通过scipy库封装好的brute和fmin两个工具函数来求解目标函数的极值

scipy的brute函数以参数范围和参数移动的步距作为输入，我们分别以[-10，10]为参数范围，5和0.1为不同的参数移动步距来求解极值

brute函数求解全局最优 参数步距为5时，求解的极值 参数步距为0.1时，求解的极值

可以看到在[-10，10]区间里，brute函数求解多元函数的驻点大概在x=y=-1.4，此时的极值为-1.7749

我们再利用fmin函数求解在初始值为x=y=-1.4时函数的局部最优解，fmin函数以需要最小化的函数和起始参数值作为输入，将brute函数求解出的驻点带入fmin

fmin函数求解局部最优（带入全局最优的驻点） fmin函数求解的极值

可以看到fmin在brute的基础上求解出更低的函数值，可以看到，在求解凸优化问题中，建议在使用局部优化之前先进行全局优化，防止求解过程陷入某个局部最优解（盆地跳跃）

二、多元函数的极值求解算法

上述我们使用了python的scipy库封装好的方法，来求解出多元函数的极值，下面我们来分析求解多元函数极值的纯数学算法

一般地，我们把具有二阶偏导数的函数z=f(x，y)，其求解极值的算法描述如下：

第1步：求出目标函数关于x和y的一阶偏导数，得到一切驻点

第2步：求出目标函数 关于x和y的二阶偏导数，并分别带入驻点求出其 二阶偏导数的值A、B和C

第3步：根据A*C-B*B的符号，判断是否存在极值，是极大值还是极小值

            (1)：A*C-B*B>0时，具有极值，且当A>0时存在极大值，当A<0时存在极小值

            (2)： A*C-B*B<0时，没有极值

            (3)： A*C-B*B=0时，可能有极值，也可能没有极值

带入驻点的二阶偏导数的值

三、牛顿迭代法

有了上述数学算法，我们对目标函数来求一阶偏导数

目标函数关于x的一阶偏导数

上式存在一个问题，要直接计算出一阶偏导数为0对应的x，则求解难度非常大，因为式子中包含了cos函数，而cos的泰勒展开式为

cos的n阶展开式

这是由n个多项式组成，所以我们只能利用逼近法的思路，来近似求解，比如牛顿迭代法

牛顿迭代法示意图

设曲线L=f(x)，则L上任意一点x0对应的切线方程为

x0的切线方程

令y=0，解出切线与x轴的交点的横坐标x1为

切线与x轴的交点

从图上可以看出x1越发靠近曲线L的真实解，如此迭代下去，在点(xn-1，f(xn-1))作切线，可以得到L根的近似值为

牛顿迭代法公式

四、牛顿迭代法求解多元函数的驻点

有了牛顿迭代法的公式，下面我们来解目标函数关于x的一阶偏导数cosx+0.1x=0的根（求解y同理），其一阶导数为-sinx+0.1，迭代出驻点后带入目标函数即可求出其极值

牛顿迭代法解出驻点 驻点对应的极值

从结果上看和scipy库计算出来的极值非常接近，其本质就是求解多元函数极值的算法