最速下降法求二次函数的极小点

最速下降法是一种迭代的优化算法，用于求解无约束优化问题。对于二次函数，最速下降法可以直接求出其极小点。

设二次函数为 $f(\mathbf{x})=\frac{1}{2}\mathbf{x}^T\mathbf{Qx}+\mathbf{b}^T\mathbf{x}+c$，其中 $\mathbf{x}\in\mathbb{R}^n$，$\mathbf{Q}$ 是一个对称正定矩阵，$\mathbf{b}\in\mathbb{R}^n$，$c\in\mathbb{R}$。极小点 $\mathbf{x}^*$ 满足 $\nabla f(\mathbf{x}^*)=\mathbf{0}$，即 $\mathbf{Q}\mathbf{x}^*+\mathbf{b}=\mathbf{0}$。

最速下降法从一个初始点 $\mathbf{x}_0$ 开始，通过迭代逐步接近极小点。具体地，每次迭代的更新公式为：

$$
\mathbf{x}_{k+1}=\mathbf{x}_k-\alpha_k\nabla f(\mathbf{x}_k)
$$

其中 $\alpha_k$ 是步长，需要满足 $\alpha_k>0$。在最速下降法中，取 $\alpha_k$ 为使得 $f(\mathbf{x}_{k+1})<f(\mathbf{x}_k)$ 的最小值，即

$$
\alpha_k=\frac{\mathbf{g}_k^T\mathbf{g}_k}{\mathbf{g}_k^T\mathbf{Qg}_k}
$$

其中 $\mathbf{g}_k=-\nabla f(\mathbf{x}_k)$ 是梯度的反方向。

最速下降法的迭代终止条件可以是达到一定的迭代次数，或者满足一定的精度要求。在实现时，还需要注意避免出现数值不稳定的情况，比如 $\mathbf{Q}$ 是病态矩阵的情况。可以采用一些技巧来解决这些问题，比如引入正则化项，或者使用共轭梯度法等更稳定的算法。

下面给出一个 Python 实现：

import numpy as np

def quadratic(x, Q, b, c):
    """二次函数"""
    return 0.5 * x.T @ Q @ x + b.T @ x + c

def grad_quadratic(x, Q, b):
    """二次函数的梯度"""
    return Q @ x + b

def solve_quadratic(Q, b):
    """求二次函数的极小点"""
    n = Q.shape[0]
    x = np.zeros(n)  # 初始点
    for k in range(n):
        g = -grad_quadratic(x, Q, b)
        alpha = g.T @ g / g.T @ Q @ g
        x = x + alpha * g
        if np.linalg.norm(g) < 1e-6:
            break
    return x

# 示例
Q = np.array([[2, 1], [1, 2]])
b = np.array([1, 1])
c = 0
x_star = solve_quadratic(Q, b)
print(x_star)  # [ -0.5  -0.5]
print(quadratic(x_star, Q, b, c))  # -1.5

这个例子中，二次函数为 $f(x_1,x_2)=x_1^2+x_2^2+x_1x_2+x_1+x_2$，极小点为 $(-\frac{1}{2},-\frac{1}{2})$，函数值为 $-\frac{3}{2}$。