最后更新: 2026-06-16 16:38 查看: 4 次纠错评论(0) 课件开VIP

梯度下降法

3.4 梯度下降法

本节从优化的角度研究线性方程组的求解．首先建立线性方程组解与二次优化问题全局最优解的如下等价关系。

定理 3.10 设 $A$ 为对称正定矩阵，则 $x^*$ 是线性方程组 $A x=b$ 解的充分必要条件是 $x^*$ 是如下二次优化问题的全局最优解，即

$$
x^*=\underset{x \in \mathbf{R}^n}{\arg \min } f(x) \triangleq \frac{1}{2}(A x, x)-(b, x)=\frac{1}{2} \sum_{i=1}^n \sum_{j=1}^n a_{i, j} x_i x_j-\sum_{j=1}^n b_j x_j .
$$

证明 必要性：设 $x^*$ 是 $A x^*=b$ 的解，下面证明 $x^*$ 是二次优化问题的全局最优解，即 $f(x)-f\left(x^*\right) \geqslant 0$ ．

$$
\begin{aligned}
f(x)-f\left(x^*\right) & =\frac{1}{2}(A x, x)-(b, x)-\frac{1}{2}\left(A x^*, x^*\right)+\left(b, x^*\right) \\
& =\frac{1}{2}(A x, x)-\left(A x^*, x\right)-\frac{1}{2}\left(A x^*, x^*\right)+\left(A x^*, x^*\right) \\
& =\frac{1}{2}(A x, x)-\frac{1}{2}\left(A x^*, x\right)-\frac{1}{2}\left(A x^*, x\right)+\frac{1}{2}\left(A x^*, x^*\right) \\
& =\frac{1}{2}\left(A\left(x-x^*\right), x\right)-\frac{1}{2}\left(A x^*, x-x^*\right) \\
& =\frac{1}{2}\left(A\left(x-x^*\right),\left(x-x^*\right)\right) \geqslant 0
\end{aligned}
$$

充分性：设 $x^*$ 是二次优化问题 $f(x)$ 的全局最优解．对任意 $t \in \mathbf{R}$ 和非零向量 $x \in \mathbf{R}^n$ ，构造关于 $t$ 的一元函数如下

$$
\begin{aligned}
g(t) & \triangleq f\left(x^*+t x\right)=\frac{1}{2}\left(A\left(x^*+t x\right), x^*+t x\right)-\left(b, x^*+t x\right) \\
& =f\left(x^*\right)+t\left(A x^*-b, x\right)+\frac{t^2}{2}(A x, x)
\end{aligned}
$$

当 $t=0$ 时，$g(t)$ 达到最优值．由费马引理知 $g^{\prime}(0)=0$ ，即对任意向量 $x$ 成立 $\left(A x^*-b, x\right)=0$ ．所以 $A x^*-b=0$ ，即 $x^*$ 是线性方程组 $A x=b$ 的解．

上述定理提供了求解线性方程组的新角度，即可以通过求解优化问题来求解线性方程组。由于一般优化问题

$$
x^*=\underset{x \in \mathbf{R}^n}{\arg \min } f(x)
$$

通常没有显式解，一般考虑迭代方法计算其数值解。通用迭代格式一般如下：

$$
x^{(k+1)}=x^{(k)}+\alpha_k p^{(k)}
$$

其中上标 $k$ 为迭代步数，$p^{(k)}$ 为第 $k$ 迭代搜索方向，正实数 $\alpha_k$ 为第 $k$ 迭代步长。
梯度下降（gradient descent）法选取负梯度方向 $-\nabla\left(f^{(k)}\right)$ 为第 $k$ 迭代搜索方向，则梯度下降法的迭代格式为

$$
x^{(k+1)}=x^{(k)}-\alpha_k \nabla f\left(x^{(k)}\right)
$$

下面简要介绍选择负梯度方向为搜索方向的原因。将 $f\left(x^{(k)}+\alpha p\right)$ 在 $x^{(k)}$ 处进行多元泰勒展开

$$
f\left(x^{(k)}+\alpha p\right)=f\left(x^{(k)}\right)+\alpha p^{\mathrm{T}} \nabla f\left(x^{(k)}\right)+\frac{1}{2} \alpha^2 p^{\mathrm{T}} \nabla^2 f\left(x^{(k)}+t p\right) p, \quad t \in(0, \alpha)
$$

下降方向为满足 $f\left(x^{(k)}+\alpha p\right)<f\left(x^{(k)}\right)$ 的搜索方向 $p$ 。如果二次项足够小可以忽略不计，假设搜索方向为单位向量 $\|p\|=1$ ，则寻找最速下降方向的问题转化为

$$
\min _p p^{\mathrm{T}} \nabla f\left(x^{(k)}\right), \quad \text { s.t. }\|p\|_2=1 .
$$

由余弦定理知，$p^{\mathrm{T}} \nabla f\left(x^{(k)}\right)=\|p\|\left\|\nabla f\left(x^{(k)}\right)\right\| \cos \theta=\left\|\nabla f\left(x^{(k)}\right)\right\| \cos \theta$ ，其中 $\theta$ 是 $p$ 和 $\nabla f\left(x^{(k)}\right)$ 的夹角．上述优化问题的最小值在 $\cos \theta=-1$（即 $p$ 的方向与 $\nabla f\left(x^{(k)}\right)$ 的方向相反）时取得．上述优化问题的最优解即最佳搜索方向为

$$
p=-\nabla f\left(x^{(k)}\right) /\left\|\nabla f\left(x^{(k)}\right)\right\|_2 .
$$

对于一般优化问题，给定搜索方向后，梯度下降法的步长通常手动选取．对于二次优化问题，给定搜索方向 $r^{(k)} \triangleq-\nabla f\left(x^{(k)}\right)=b-A x^k$ ，优化问题的目标函数为关于 $\alpha$ 的一元函数

$$
\begin{aligned}
g(\alpha) & \triangleq f\left(x^{(k)}+\alpha r^{(k)}\right)=\frac{1}{2}\left(A\left(x^{(k)}+\alpha r^{(k)}\right), x^{(k)}+\alpha r^{(k)}\right)-\left(b, x^{(k)}+\alpha r^{(k)}\right) \\
& =f\left(x^{(k)}\right)+\alpha\left(A x^{(k)}-b, r^{(k)}\right)+\frac{\alpha^2}{2}\left(A r^{(k)}, r^{(k)}\right)
\end{aligned}
$$

由费马引理知最佳步长 $\alpha^*$ 满足 $g^{\prime}\left(\alpha^*\right)=0$ ，则最佳步长为

$$
\alpha_k=\frac{\left(r^{(k)}, r^{(k)}\right)}{\left(A r^{(k)}, r^{(k)}\right)} .
$$

下面我们通过两个例子进一步理解梯度下降法．

例 3.6 通过梯度下降法求解如下优化问题的最优解：

$$
x^*=\underset{x \in \mathbf{R}^2}{\operatorname{argmin}} f(x)=x_1^2+x_2^2 \text {, 其中最优解为 }(0,0)^{\mathrm{T}} \text {. }
$$

解 由于目标函数梯度为 $\nabla f=\left(2 x_1, 2 x_2\right)^{\mathrm{T}}$ ，梯度下降法迭代格式为

$$
\binom{x_1^{(k+1)}}{x_2^{(k+1)}}=\binom{x_1^{(k)}}{x_2^{(k)}}-\alpha\binom{2 x_1^{(k)}}{2 x_2^{(k)}}=(1-2 \alpha)\binom{x_1^{(k)}}{x_2^{(k)}} .
$$

选取初始向量 $\left(x_1^{(0)}, x_2^{(0)}\right)^{\mathrm{T}}=(1,3)^{\mathrm{T}}$ 和步长 $\alpha=0.1$ ，则迭代结果为

$$
\begin{aligned}
& x^{(0)}=(1.0000,3.0000)^{\mathrm{T}}, \\
& x^{(1)}=(0.8000,2.4000)^{\mathrm{T}}, \\
& x^{(2)}=(0.6400,1.9200)^{\mathrm{T}}, \\
& x^{(3)}=(0.5120,1.5360)^{\mathrm{T}}, \\
& x^{(4)}=(0.4096,1.2288)^{\mathrm{T}},
\end{aligned}
$$

$$
x^{(10)}=(0.1074,0.3221)^{\mathrm{T}} .
$$

大家可以尝试不同大小步长对收敛结果的影响。
例 3.7 通过梯度下降法求解线性方程组 $A x=b$ ，其中

$$
A=\left(\begin{array}{ll}
2 & 2 \\
2 & 5
\end{array}\right), \quad x=\binom{x_1}{x_2}, \quad b=\binom{6}{3} .
$$

解 线性方程组可以转化为相应二次优化问题

$$
\begin{aligned}
x^* & =\underset{x \in \mathbf{R}^2}{\operatorname{argmin}} f(x) \triangleq \frac{1}{2}(A x, x)-(b, x) \\
& =\frac{1}{2}\left(\begin{array}{ll}
x_1 & x_2
\end{array}\right)\left(\begin{array}{ll}
2 & 2 \\
2 & 5
\end{array}\right)\binom{x_1}{x_2}-\left(x_1, x_2\right)\binom{6}{3} .
\end{aligned}
$$

下面通过梯度下降法求解上述二次优化问题．由于目标函数的负梯度方向为

$$
r \triangleq-\nabla f(x)=\binom{6}{3}-\left(\begin{array}{ll}
2 & 2 \\
2 & 5
\end{array}\right)\binom{x_1}{x_2}
$$

则梯度下降法迭代格式为

$$
\binom{x_1^{(k+1)}}{x_2^{(k+1)}}=\binom{x_1^{(k)}}{x_2^{(k)}}+\alpha\binom{r_1^{(k)}}{r_2^{(k)}} .
$$

选取初始向量 $\left(x_1^{(0)}, x_2^{(0)}\right)^{\mathrm{T}}=(0,0)^{\mathrm{T}}$ ，则第一步迭代的搜索方向 $r^{(0)}$ 为

$$
r^{(0)}=-\nabla f\left(x^{(0)}\right)=\binom{6}{3}-\left(\begin{array}{ll}
2 & 2 \\
2 & 5
\end{array}\right)\binom{0}{0}=\binom{6}{3}
$$

第一步步长 $\alpha_0$ 为

$$
\alpha_0=\frac{\left(r^{(0)}, r^{(0)}\right)}{\left(A r^{(0)}, r^{(0)}\right)}=0.2381 .
$$

第一步迭代近似解为

$$
x^{(1)}=x^{(0)}+\alpha_0 r^{(0)}=\binom{1.4286}{0.7143}
$$

第二步迭代的搜索方向 $r^{(1)}$ 为

$$
r^{(1)}=-\nabla f\left(x^{(1)}\right)=b-A x^{(1)}=\binom{1.7143}{-3.4286} .
$$

第二步步长 $\alpha_1$ 为

$$
\alpha_1=\frac{\left(r^{(1)}, r^{(1)}\right)}{\left(A r^{(1)}, r^{(1)}\right)}=0.3571 .
$$

第二步迭代近似解为

$$
x^{(2)}=x^{(1)}+\alpha_1 r^{(1)}=\binom{2.0408}{-0.5102} .
$$

由于思想简单且复杂度低，梯度下降法及其变种（如随机梯度下降法等）被广泛应用于机器学习等领域的优化问题求解中，如计算回归模型的参数和深度神经网络的参数等．

科数题库(单机版) 会议室预约系统(book)

今日还可看 0 篇未注册用户每天查看4篇，注册用户每天8篇，开通VIP会员无限制查看。

免费注册

《高等数学》难点解析

高数教程 泰勒公式切线与法线切平面与法平面驻点·拐点·极值点·零点间断点渐进线瑕积分欧拉方程伯努利方程 Abel 收敛定理偏导数的几何意义偏导数的几何意义梯度数量场与向量场多元函数极值拉格朗日算子通量与散度环流量与旋度格林公式高斯公式斯托克斯公式三大公式比较傅里叶级数极坐标微元点法式方程变上限定积分 X型计算面积 Y型计算面积微分的意义渐近线间断点 y''+py'+qy=f(x)方程高斯黎曼傅里叶变换(复数) 拉普拉斯变换(复数)

《线性代数》难点解析

线代教程 近世代数对数学的整体思考线性的意义矩阵乘法(列视角) 矩阵乘法(行视角) 矩阵左乘矩阵右乘逆矩阵求解方程组阶梯形矩阵的求法方程组解的判定四阶行列式的计算线性变换的意义线性空间向量组的等价线性空间的几何意义基础解系的求法施密特正交化特征值与特征向量的意义矩阵相似的几何意义矩阵可对角化的理解秩的意义(向量版) 秩的意义(方程版) 二次型的意义

《概率论与数理统计》难点解析

概率教程 置信区间与上a分位数概率中的“取”与“放” 贝叶斯公式全概率公式泊松分布指数分布伽玛分布二维密度图的意义卷积的意义相关系数的意义 k阶矩是与矩母函数卡方分布的作用单正态区间估计理解假设检验理解切比雪夫不等式中心极限定理

上一篇：迭代法的收敛性质(2)

下一篇：特征值的估计

本文对您是否有用？有用 (0) 无用 (0)