二次型优化问题 - 1 - 问题描述

本文最后更新于:2022年7月4日 上午

在各种场景可能都会遇到需要求解多元二次函数极值的问题,本系列文章介绍相关的计算方法,核心内容为共轭梯度法。

本文介绍问题定义。

问题定义

  • 多元二次多项式,维度为$n$,那么可以用以下公式描述该函数:

$$
f({x_1},{x_2},{x_3},…,{x_n}) = {a_{1,1}}x_1^2 + {a_{1,2}}{x_1}{x_2} + {a_{1,3}}{x_1}{x_3} + \cdots + {a_{1,n}}{x_1}{x_n} + {a_{2,1}}x_2{x_1} + {a_{2,2}}{x_2^2} + {a_{2,3}}{x_2}{x_3} + \cdots + {a_{2,n}}{x_2}{x_n} + \cdots + {a_{n,n}}x_n^2+{b_1}x_1+{b_2}x_2+\cdots+{b_n}x_n+c
$$

其中$a_{i,j}$为二次项系数,共有$n^2$项,$1 \le i,j \le n$,且所有的$a$不全为0,即$\exists a_{i,j} \ne 0$;

$b_k$为一次项系数,共$n$项,$1 \le k \le n$;

$c$为常数项。

  • 记 $f({\bf{x}}) = {[{x_1},{x_2}, \cdots ,{x_n}]^T}$ ,则上述函数可以写作二次型的形式:

$$
f({x_1},{x_2},{x_3},…,{ x_n}) = f({\bf{x}}) = {\bf{x^T} }\bf{A}{\bf{x} } + { {\bf{b} }^T}{\bf{x} } + c
$$

转化过程中$\bf{A},\bf{b}$满足:

${\bf{A} }$ 为$n$阶对称方阵,${ { \bf { A } } _ { i , j } } = { a _ { i , j } }$

因为$\exists a_{i,j} \ne 0$,$\bf{A}$不为零矩阵

$\bf{b}_i=b_i$

  • 为了后续计算简便,我们将二次型稍作改动:

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

  • 我们的目标就是寻找该函数的极值点的坐标,我们把该目标称为$\bf{x^*}$。

简要分析

  • 当前问题其实就是多元二次方程极值求解的问题
  • 此类函数在函数定义域内处处连续可导
  • 极值点必然处于导数为0的位置

需要解决的问题

  • 同一个多元二次方程表示成二次型的参数$\bf{A},\bf{b},\bf{c}$是否唯一,如果不唯一该如何设置,为什么如此设置
  • 该问题是否存在导数为0的点
  • 导数为0的点如何求解
  • 导数为0的点是否就是极值点
  • 对于给定的二次型如何判断是否可优化
  • 对于可优化的二次型都有什么方法寻找极值点
  • 寻找极值点的方法们都有哪些优缺点,为什么需要提出共轭梯度法
  • 代数解法,梯度下降法介绍与分析
  • 共轭梯度法介绍与分析
  • 共轭梯度法的相关证明

二次型优化问题 - 1 - 问题描述
https://www.zywvvd.com/notes/study/machine-learning/conjugate-gradient-algorithm/conjugate-gradient/conjugate-gradient/
作者
Yiwei Zhang
发布于
2020年11月16日
许可协议