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

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

本文介绍问题定义。

问题定义

• 多元二次多项式，维度为$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的点是否就是极值点
• 对于给定的二次型如何判断是否可优化
• 对于可优化的二次型都有什么方法寻找极值点
• 寻找极值点的方法们都有哪些优缺点，为什么需要提出共轭梯度法
• 代数解法，梯度下降法介绍与分析
• 共轭梯度法介绍与分析
• 共轭梯度法的相关证明

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