问题定义
- 多元二次多项式，维度为 \(n\)，那么可以用以下公式描述该函数：
$$
f(x_1,x_2,x_3,…,x_n)=a_{1,1}x_1^2+a_{1,2}x_1x_2+a_{1,3}x_1x_3+⋯+a_{1,n}x_1x_n+a_{2,1}x_2x_1+a_{2,2}x_2^2+a_{2,3}x_2x_3+⋯+a_{2,n}x_2x_n+⋯+a_{n,n}x_n^2+b_1x_1+b_2x_2+⋯+b_nx_n+c \tag{1}
$$
其中\(a_{i,j}\)为二次项系数，共有\(n^2\)项，\(1≤i,j≤n\)，且所有的\(a\) 不全为0，即\(∃a_{i,j}≠0\); \(b_k\)为一次项系数，共\(n\)项，\(1≤k≤n\); \(c\) 为常数项。
-
记 \(f(x)=[x_1,x_2,...,x_n]^T\)，则上述函数可以写作二次型的形式：
转化过程中A,b满足：
A 为n阶对称方阵，\(A_{i,j}=a_{i,j}\) 因为\(∃a_{i,j}≠0\)，A不为零矩阵\(b_i=b_i\) -
为了后续计算简便，我们将二次型稍作改动：
$$
f(x)=\frac{1}{2}x^TAx-b^Tx+c\tag{3}
$$ -
我们的目标就是寻找该函数的极值点的坐标，我们把该目标称为\(x^∗\).
-
其中，表示\(A\)：
$$
A=[a_{1,1}^∙⋯a_{n,n}^∙]\tag{4}
$$ -
将 \(A\) 与多项式系数对应：
$$
a_{i,i}^∙=a_{i,i},1≤i≤n\tag{5}
$$
- 那么对应 \(A\) 中非对角线的元素，仅需要保证公式(6)成立即可，那么对于不相等的 \(i,j\)，可以有无数种\(a_{i,j}^∙+a_{j,i}^∙\) 的组合满足条件，\(A\) 该如何确定？
二次型矩阵
-
在定义实数空间内的二次型时，二次型矩阵被要求为对称的，也就是要求：
$$
a_{i,j}^∙=a_{j,i}^∙=\frac{1}{2}a_{i,j},1≤i<j≤n\tag{8}
$$ -
也就确定了唯一的\(A\)，来表示一个确定的多元二次函数。
为何如此
- 定义的用处就是来确定问题，这种定义可以唯一确定二次函数，没有任何歧义和变化，用于统一数学术语
- 我觉得很关键的问题是如此定义\(A\)会给求导带来很大方便
- 我们略去一次项与常数项，得到纯粹的二次型：
-
仍用(4)表示\(A\)，对(9)中的向量\(x\)求导：
$$
f^′(x_i)=\frac{1}{2}\left[∑{j=1,j≠i}^n(a{i,j}^∙+a_{j,i}^∙)x_j+2a_{i,i}^∙x_i\right]\tag{11}
$$ -
如果 \(A\) 是对称阵，那么\(a_{i,j}^∙=a_{j,i}^∙\)，有：
$$
f^′(x)=Ax\tag{13}
$$ -
也就是说定义\(A\)为对称阵可以唯一确定二次型矩阵，也可以方便地对二次型进行求导。
导数为0的点是否存在
-
对于一般的二次型(3)的导数为
$$
f^′(x)=Ax−b\tag{14}
$$ -
导数为0的点是否存在与方程 \(Ax=b\) 是否有解等价
- 设\(r_A=r(A)\)为$A
$的秩 - \(Ab\) 为增广矩阵，\(r_{Ab}=r(Ab)\)为增广矩阵的秩，有：
极值点是否存在
- 当导数为零的点不存在时，即(14)方程组无解时，极值点不存在
- 当导数为0的点存在时：
- 为使得讨论有意义，我们之后讨论的(3)的优化均在A为半正定矩阵的条件下，来寻找其极小值，也就是最小值
优化方法
代数法
高斯消元法
-
在\(A\)的行列式不为0时，可以逐项消除半边系数，得到三角阵，计算得到\(x_n\)再逐步带入计算出其他未知数，得到计算结果。
$$
\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}\tag{15}
$$ -
其他代数方法在高斯消元法基础上进行改进
高斯主元素消元法
- 为解决无法面对主元素为0或主元素绝对值过小带来的精度不够的问题，提出了主元素消元
- 核心思想是选择系数绝对值最大的行作为基准进行消元，可以有效缓解上述问题
矩阵求逆
- 对于矩阵\(A\)可逆的情况，可以直接求出\(A\)的逆矩阵，则：
$$
x=A^{-1}b
$$
迭代法
代数法的时间复杂度都在 \(O(n^3)\)的数量级上，在实践中难以接受；迭代法的思想是可以每次贪心地计算局部最优解，逐步向全局最优解逼近
最速下降法/梯度法
- 沿着当前梯度的反方向前进至方向梯度为0，重新计算当前位置的梯度，重新出发
- 不断重复该过程，直到精度满足要求
共轭梯度法
- 沿着共轭梯度方向前进该共轭基的分量大小的距离
- 在所有共轭基上重复上述操作，即可达到全局最优解
随后我们重点介绍迭代法相关内容