二次型优化问题 - 4 - 二次型优化方法

本文最后更新于:2022年8月10日 上午

在确定了可优化二次型的类型后,本文讨论二次型的优化方法。

当前问题

  • 解方程$\bf{Ax}=\bf{b}$

  • 其中$\bf{A}$为半正定矩阵

  • $\bf{A}$的秩与其增广矩阵$\bf{Ab}$的秩相等

优化方法

代数法

高斯消元法

数学上,高斯消元法(或译:高斯消去法),是线性代数规划中的一个算法,可用来为线性方程组求解。但其算法十分复杂,不常用于加减消元法,求出矩阵的秩,以及求出可逆方阵的逆矩阵。

  • 在$\bf{A}$的行列式不为0时,可以逐项消除半边系数,得到三角阵,计算得到$x_n$再逐步带入计算出其他未知数,得到计算结果。

$$
\begin{equation}
\begin{split}
{a_{11}}{x_1} + {a_{12}}{x_2} + \cdots {a_{1n}}{x_n} = {b_1}\\
{a_{22}}{x_2} + \cdots {a_{2n}}{x_n} = {b_2}\\
\vdots \\
{a_{nn}}{x_n} = {b_n}
\end{split}
\end{equation}
$$

  • 其他代数方法在高斯消元法基础上进行改进

高斯主元素消元法

  • 为解决无法面对主元素为0或主元素绝对值过小带来的精度不够的问题,提出了主元素消元
  • 核心思想是选择系数绝对值最大的行作为基准进行消元,可以有效缓解上述问题

矩阵求逆

  • 对于矩阵$\bf{A}$可逆的情况,可以直接求出$\bf{A}$的逆矩阵,则:

$$
{\bf{x}} = {\bf{A^{-1}}}{\bf{b}}
$$

迭代法

代数法的时间复杂度都在 $O(n^3)$的数量级上,在实践中难以接受;

迭代法的思想是可以每次贪心地计算局部最优解,逐步向全局最优解逼近

最速下降法/梯度法

  • 沿着当前梯度的反方向前进至方向梯度为0,重新计算当前位置的梯度,重新出发
  • 不断重复该过程,直到精度满足要求

共轭梯度法

共轭梯度法(Conjugate Gradient)是介于最速下降法牛顿法之间的一个方法,它仅需利用一阶导数信息,但克服了最速下降法收敛慢的缺点,又避免了牛顿法需要存储和计算Hesse矩阵并求逆的缺点,共轭梯度法不仅是解决大型线性方程组最有用的方法之一,也是解大型非线性最优化最有效的算法之一。

  • 沿着共轭梯度方向前进该共轭基的分量大小的距离
  • 在所有共轭基上重复上述操作,即可达到全局最优解

随后我们重点介绍迭代法相关内容

参考资料


二次型优化问题 - 4 - 二次型优化方法
https://www.zywvvd.com/notes/study/machine-learning/conjugate-gradient-algorithm/ways-to-optimize/ways-to-optimize/
作者
Yiwei Zhang
发布于
2020年12月15日
许可协议