二次型优化问题 - 3 - 导数与极值点

本文最后更新于:2022年8月5日 晚上

本文介绍在已经定义好的问题下,二次型导数与极值点相关内容。

导数为0的点是否存在

  • 对于一般的二次型:

$$
f({\bf{x} }) = \frac{1}{2}{\bf{x^TAx} } - { {\bf{b} }^{\bf{T} } }{\bf{x} } + {\bf{c} } \tag{1} \label{1}
$$

  • 导数为:

$$
f’({\bf{x}}) = {\bf{Ax}} - {\bf{b}} \tag{2} \label{2}
$$

  • 导数为0的点是否存在与方程$\bf{Ax}=\bf{b}$是否有解等价
  • 设${r_A} = r(A)$为$\bf{A}$的秩
  • $\bf{Ab}$为增广矩阵,${r_{Ab}} = r(\bf{Ab})$为增广矩阵的秩,有:
条件 结论
$r_{A}<r_{Ab}$ 方程组无解,二次型不存在导数为0的点
$r_{A}=r_{Ab}=n$ 方程组有唯一解,二次型有唯一导数为0的点
$r_{A}=r_{Ab}<n$ 方程组有无数组解,二次型有无数个导数为0的点
$r_{A}>r_{Ab}$ 不可能,增广矩阵的秩不会变小

极值点是否存在

  • 当导数为零的点不存在时,即$\eqref{2}$方程组无解时,极值点不存在

  • 当导数为0的点存在时:

    • 若$\bf{A}$为正定矩阵,则式$\eqref{1}$有极小值,就是最小值
    • 若$\bf{A}$为负定矩阵,则式$\eqref{1}$有极大值,就是最大值
    • 若$\bf{A}$为半正定矩阵,且存在特征值为0,由于前提是方程组有解,则增广矩阵的秩和矩阵$\bf{A}$的秩相等,那么$\bf{b}$中对应的值为0,方程组有无限多组解,但需要满足某种条件,在这组条件下,方程组都是极小值,也就是说若$\bf{A}$为半正定矩阵则$\eqref{1}$有极小值,同时就是最小值
    • 同理若$\bf{A}$为半负定矩阵,则$\eqref{1}$有极大值,也即最大值
    • 若$\bf{A}$的特征值有正有负,则$\eqref{1}$有极小/大值,但不是最小/大值,此时$\eqref{1}$没有最小/大值
  • 为使得讨论有意义,我们之后讨论的$\eqref{1}$的优化均在$\bf{A}$为半正定矩阵的条件下,来寻找其极小值,也就是最小值


二次型优化问题 - 3 - 导数与极值点
https://www.zywvvd.com/notes/study/machine-learning/conjugate-gradient-algorithm/gradient-related/gradient-related/
作者
Yiwei Zhang
发布于
2020年12月13日
许可协议