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

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

本文介绍问题定义。

问题定义

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

$$f(x_1,x_2,x_3,\dots ,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，即$\mathrm{\exists }{a}_{i,j}\ne 0$;

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

$c$为常数项。

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

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

转化过程中$\mathbf{A}\mathbf{,}\mathbf{b}$满足：

$\mathbf{A}$ 为$n$阶对称方阵，${\mathbf{A}}_{i,j}=a_{i,j}$

因为$\mathrm{\exists }{a}_{i,j}\ne 0$，$\mathbf{A}$不为零矩阵

${\mathbf{b}}_{\mathbf{i}}\mathbf{=}{\mathbf{b}}_{\mathbf{i}}$

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

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

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

简要分析

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

需要解决的问题

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

文章链接：
https://www.zywvvd.com/notes/study/machine-learning/conjugate-gradient-algorithm/conjugate-gradient/conjugate-gradient/