学习笔记|牛顿法介绍了非线性方程求解中的牛顿法，再来看凸优化问题中的牛顿法。

1. 凸优化中的牛顿法

在凸优化问题中，局部最优即为全局最优。除了端点外，目标函数f(x)的极值点必有f'(x)=0。因此，凸优化问题可转化为求解f'(x)=0。

对f'(x)进行一阶泰勒展开

因此，迭代公式为

2. 多维凸优化中的牛顿法

定义H为hessian矩阵

多维下的迭代公式为

迭代终止条件为

3. 牛顿法的Python实现

首先计算偏导数

def df(x, i):
    nx = x.copy()
    nx[i] += 0.0001
    return (f(nx)-f(x))/0.0001

然后计算梯度

def gf(x):
    gx = x.copy()
    for i in range(len(x)):
        gx[i] = df(x, i)
    return gx

计算二阶偏导数

def ddf(x, i, j):
    nx = x.copy()
    nx[j] += 0.0001
    return (df(nx, i)-df(x, i))/0.0001

计算Hessian矩阵

def H(x):
    H = np.zeros((len(x), len(x)))
    for i in range(len(x)):
        for j in range(len(x)):
            H[i, j] = ddf(x, i, j)
    return H

改写牛顿迭代法的实现（原始的牛顿迭代法可参见学习笔记|牛顿法）

def newtonmethod(n, iv, e=0.000001):
    iv = np.array(iv, dtype=float)
    cn = 1
    g = gf(iv)
    v = iv - np.dot(np.linalg.inv(H(iv)), g)
    while cn < n and np.sqrt(np.sum(g ** 2)) > e:
        cn += 1
        iv = v
        g = gf(iv)
        v = iv - np.dot(np.linalg.inv(H(iv)), g)
        print(cn, v)
    return v

最后，为了验证牛顿法实现的准确性，引用参考文献3第17页的例子进行验证。

f(x)为

def f(x):
    return np.exp(x[0])*(4*x[0]**2+2*x[1]**2+3*x[0]*x[1]+2*x[1]+3)

输入

print(newtonmethod(100, (1, 1)))

得到

2 [ 0.77934187 -1.3493452 ]
3 [ 0.37538269 -0.88852594]
4 [ 0.05816671 -0.57757567]
5 [-0.15668942 -0.38980094]
6 [-0.26447199 -0.30247133]
7 [-0.29196656 -0.28109434]
8 [-0.29363991 -0.27981997]
9 [-0.2936462  -0.27981535]
10 [-0.2936462  -0.27981535]
[-0.2936462  -0.27981535]

得到的结果与案例3一致。

参考文献

1.https://blog.csdn.net/michaelhan3/article/details/82350047
2.https://blog.csdn.net/itplus/article/details/21896453
3.https://max.book118.com/html/2018/0514/166248355.shtm