[二次型] - 线性代数，最优化总结

若函数$f: \mathbb{R}^n \rightarrow \mathbb{R}$可以表示为

$f = \mathbf{x}^TA\mathbf{x}$

其中$\mathbf{x} \in R$，$A$是$n \times n$的对称矩阵，那么称$f$为$\mathbf{R}^2$上的二次型，$A$为二次型矩阵

二次型矩阵为对称矩阵

主轴定理

由于$A$为对称矩阵，存在正交矩阵$P$，使得$A = P\Lambda P^T$，$\Lambda$为$A$的特征值矩阵，有

$\Lambda = P^{-1}A(P^T)^{-1} = P^TAP$

其中$P$的列向量的集合是$\mathbb{R}^n$的一个基，由基变换中过渡矩阵一定是非奇异矩阵（可逆矩阵 $\Rightarrow$ 行满秩矩阵，列满秩矩阵），其中因为$P$是正交矩阵（$P^T=P^{-1}$），则任意标准基下的向量$\mathbf{x}$都可以表示为$P$下的向量$\mathbf{y}$的乘积

$\mathbf{x} = P\mathbf{y}$

上述变换：变量变换
当$P$为正交矩阵的时候，上述变换为：正交变量变换

---

• $m \times n$矩阵：
  • $A$与$B$等价：存在$m$阶可逆矩阵$P$和$n$阶可逆矩阵，使得$PAQ = B$
• $n \times n$矩阵：
  • $A$与$B$相似$\Leftrightarrow$存在可逆矩阵$P$，使得$P^{-1}AP = B$
  • $A$与$B$合同$\Leftrightarrow$存在可逆矩阵$P$，使得$P^TAP = B$
  • $A$与$B$正交相似$\Leftrightarrow$存在正交矩阵$P$，使得$P^TAP = P^{-1}AP = B$

相似，合同，正交相似，都是等价的一种，正交相似关系最强，等价关系最弱

二次型规范形

将上述式子带入到二次型当中，得到

$\begin{aligned} f &= \mathbf{x}^TA\mathbf{x} = (P\mathbf{y})^TA (P\mathbf{y}) =\mathbf{y}^T\Lambda \mathbf{y} \\ &= \lambda_1y^2_1 + \lambda_2y^2_2 + \cdots + \lambda_ny^2_n \end{aligned}$

上述中$P$为二次型$\mathbf{x}^TA\mathbf{x}$的主轴

二次型标准形

任给二次型$f = \sum^n_{i,j = 1}a_{ij}x_ix_j(a_{ij} = a_{ji})$，总存在正交变换$\mathbf{x}=P\mathbf{y}$，使得$f$化为标准型

$f = \lambda_1y^2_1 + \lambda_2y^2_2 + \cdots + \lambda_ny^2_n$

• 二次型标准形不是唯一的，但是标准形中所含的项数是确定的
• 二次型矩阵有很多，但是只有一个是对称的，也就是Hermitian矩阵（$A^* = A$）
• 在限定变换为实变换的时候，标准形中正系数的个数是不变的

其中$\lambda_i$为$f$的矩阵$A$的特征值

初等变换法

任意实对称矩阵可以同时进行相同行和列的初等变换化为对角形

对一个$n$阶实对称矩阵$A$，都存在可逆矩阵$C$，使得

$C^TAC = diag(d_1, d_2, \cdots, d_n)$

• $C$不一定实正交矩阵
• $d_1, d_2, \cdots, d_n$不一定是$A$的特征值
• 如果$C$是正交矩阵，则$d_i$为特征值

初等变换，就是对矩阵乘上初等矩阵

$\begin{gathered} P^T_iAP_i \\ \Downarrow \\ P^T_k \cdots P^T_2P^T_1\color{red}A\color{black}P_1 P_2 \cdots P_n\end{gathered}$

记$C=P_1 P_2 \cdots P_n$，则

$C^TAC$

为了得到$C$，可以对单位矩阵进行同等操作

$\begin{pmatrix} A \\ I \end{pmatrix} \longrightarrow \begin{pmatrix} C^TAC \\ C \end{pmatrix}$

惯性定理

设二次型$f(\mathbf{x}) = \mathbf{x}^TA\mathbf{x}$，它的秩为$r$，有2个可逆变换

$\mathbf{x} = C\mathbf{y} \qquad \mathbf{x} = P\mathbf{z}$

使得

$\begin{aligned} f &= k_1y^2_1 + k_2y^2_2 + \cdots + k_ry^2_r & (k_i \neq 0) \\ f &= \lambda_1y^2_1 + \lambda_2y^2_2 + \cdots + \lambda_ry^2_r & (\lambda_i \neq 0) \end{aligned}$

则$k_1, k_2, \cdots, k_r$中正数的个数与$\lambda_1, \lambda_2, \cdots, \lambda_r$中正数的个数相对

• 正系数的个数，称为二次型的正惯性指数
• 负系数的个数，称为二次型的负惯性指数
• 正，负惯性指数的差，称为符号差

若二次型$f$的正惯性指数为$p$，秩为$r$，则$f$的规范性为

$f = y^2_1 + \cdots + y^2_p - y^2_{p+1} - \cdots - y^2_r$

• 若$A$的正，负惯性指数分别为$p$和$q$，则

$A \simeq diag(1, \cdots, 1, -1, \cdots, -1, 0 ,\cdots, 0)$

其中$1$有$p$个，$-1$有$q$个

正定性

• 如果对任意$\mathbf{x} \neq 0$，都有$f(\mathbf{x}) > 0$，则称$f$为正定二次型，称矩阵$A$为正定矩阵
• 如果对任意$\mathbf{x} \neq 0$，都有$f(\mathbf{x}) < 0$，则称$f$为负定二次型，称矩阵$A$为负定矩阵
• 如果对任意$\mathbf{x} \neq 0$，$f(\mathbf{x}) \leq 0$，则称$f$为半正定二次型，称矩阵$A$为正定矩阵
• 如果对任意$\mathbf{x} \neq 0$，$f(\mathbf{x}) \geq 0$，则称$f$为负定二次型，称矩阵$A$为负定矩阵

正定和半正定，以及负定和半负定⼆次型，统称为有定⼆次型，如果⼆次型不是有定的，就称为不定二次型

正定

二次型是正定的充要条件为

• $A$的正惯性指数为$n$，即$A \simeq I$
• 存在可逆矩阵$P$，使得$A = P^TP$
• $A$的$n$个特征值全为正
• $A$的$n$个顺序主子式全为正，即

$a_{11}>0 \quad \begin{vmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \end{vmatrix} > 0 \quad \begin{vmatrix} a_{11} & \cdots & a_{1n} \\ \vdots & & \vdots \\ a_{n1} & \cdots & a_{nn} \end{vmatrix} > 0$

正定矩阵性质2

必要性：因为$A$为正定矩阵，所以$A \simeq I$，即存在可逆矩阵$C$，使得$C^TAC = I$，即

$A = -(C^{-1})^TC^{-1}$

取$P = C^{-1}$，则有$P$可逆，且$A = P^TP$

---

充分性：因为存在可逆矩阵$P$使得$A=P^TP$，即

$(P^T)^{-1}AP^{-1} = I$

从而$A \simeq I$，所以$A$为正定矩阵

正定矩阵性质3

$\begin{aligned} A\mathbf{x} &= \lambda \mathbf{x} \\ \mathbf{x}^TA\mathbf{x} &= \lambda \mathbf{x}^T\mathbf{x} \end{aligned}$

其中$\mathbf{x}^TA\mathbf{x} > 0, \mathbf{x}^T\mathbf{x} > 0$，则可得$\lambda > 0$

负定

二次型是负定的充要条件为

• $A$的负惯性指数为$n$，即$A \simeq -I$
• 存在可逆矩阵$P$，使得$A = -P^TP$
• $A$的$n$个特征值全为负
• 奇数阶顺序主子式为负，偶数阶顺序主兹式为正，即

$(-1)^r \begin{vmatrix} a_{11} & \cdots & a_{1r} \\ \vdots & & \vdots \\ a_{r1} & \cdots & a_{rr} \end{vmatrix} > 0 \quad (r=1,2,\cdots,n)$

实对称

设$A$是$n$阶实对称矩阵的充要条件为

• $A$的正惯性指数$< n$
• 存在降序矩阵$P(r(P) < n)$，使得$A = P^TP$
• $A$的$n$个特征值全为非负，但至少有一个等于$0$
• $A$的各阶主子式非负，但是至少有一个为$0$

XY的二次型

$\begin{aligned} f(x, y) &= a_{11}x^2 + a_{22}y^2 + 2a_{12}xy + 2b_1x + 2b_2y + c = 0 \\ &= \begin{pmatrix} x & y \end{pmatrix}A\begin{pmatrix} x \\ y \end{pmatrix}+2\begin{pmatrix} b_1 & b_2 \end{pmatrix}*\begin{pmatrix} x \\ y \end{pmatrix}+c \\ &=\begin{pmatrix} x & y & 1 \end{pmatrix}\begin{pmatrix} a_{11} & a_{12} & b_1 \\ a_{21} & a_{22} & b_2 \\ b_1 & b_2 & c \end{pmatrix} * \begin{pmatrix} x \\ y \\ 1 \end{pmatrix} \end{aligned}$

$\hat{A} = \begin{pmatrix} a_{11} & a_{12} & b_1 \\ a_{21} & a_{22} & b_2 \\ b_1 & b_2 & c \end{pmatrix} \qquad A = \begin{pmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \end{pmatrix}$

记

• $p$为$A$的正固有值数量
• $q$为$A$的负固有值数量
• $\hat{p}$为$\hat{A}$的正固有值数量
• $\hat{q}$为$\hat{A}$的负固有值数量

则有一下关系

$p$	$q$	$\hat{p}$	$\hat{q}$	形状
2	0	2	1	椭圆
1	1	2	1	双曲线
1	1	1	1	相交的两条直线
1	0	2	1	抛物线
1	0	1	1	平行的两条直线

同理，取

$\hat{A} = \begin{pmatrix} a_{11} & a_{12} & a_{13} & b_1 \\ a_{21} & a_{22} & a_{23} & b_2 \\ a_{31} & a_{32} & a_{33} & b_3 \\ b_1 & b_2 &b_3 & c \end{pmatrix} \qquad A = \begin{pmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{pmatrix}$

令$\tilde{r} = \tilde{p} + \tilde{q}$，则

$p$	$q$	$\hat{p}$	$\hat{q}$	$\tilde{r}$	形状
3	0	3	1		椭圆面
2	1	2	2		单叶双曲面
2	1	3	1		双叶双曲面
2	1	2	1		二次锥面
2	0			4	椭圆抛物面
2	0	2	1		椭圆柱
1	1			4	双面抛物面
1	1			3	双曲柱体
1	1			2	相交的两各面
1	0			3	抛物面柱体
1	0	1	1		平行的两各面

无约束凸二次规划

设有二次凸函数

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

名称	式子
$\nabla f(\mathbf{x})$	$A\mathbf{x} + \mathbf{b}$
$\nabla^2 f(\mathbf{x})$	$A$

无约束凸函数任何局部极小点$x^*$都是该函数的一个全局极小点，若该函数时可微的，则满足$\frac{\partial f(x)}{\partial x} = 0$

$\nabla f(\mathbf{x}) = A\mathbf{x} + \mathbf{b} = 0$

得到最优解

$\mathbf{x} = -A^{-1} \mathbf{b}$

牛顿法求解

$\begin{aligned} \mathbf{x}_1 &= \mathbf{x}_0 - A^{-1}\nabla f(\mathbf{x}_0) = \mathbf{x}_0 - A^{-1}(A\mathbf{x} + \mathbf{b}) = A^{-1}b \end{aligned}$

即1次迭代到极小点，这种性质称为二次终止性

二次规划

$\begin{aligned} min &\qquad f(\mathbf{x})=\frac{1}{2}\mathbf{x}^TP\mathbf{x} + \mathbf{q}^T\mathbf{x} + r \\ s.t. &\qquad G\mathbf{x} \preceq \mathbf{h} \\ &\qquad A\mathbf{x} = \mathbf{b} \end{aligned}$

其中

• $P_i \in \mathbb{R}^n_+$
• $G \in \mathbb{R}^{m \times n}$
• $A \in \mathbb{R}^{p \times n}$

线性规划

若$A = 0$，二次规划问题则变为线性规划问题

$\begin{aligned} min &\qquad f(\mathbf{x})=\mathbf{c}^T\mathbf{x} + d \\ s.t. &\qquad G\mathbf{x} \preceq \mathbf{h} \\ &\qquad A\mathbf{x} = \mathbf{b} \end{aligned}$

等式约束二次规划

$\begin{aligned} min &\qquad f(\mathbf{x})=\frac{1}{2}\mathbf{x}^TP_0\mathbf{x} + \mathbf{c}_0^T\mathbf{x} + d_0 \\ s.t. &\qquad \frac{1}{2}\mathbf{x}^TP_i\mathbf{x} + \mathbf{c}^T_i\mathbf{x} + d_i \leq 0 \qquad i = 1, \cdots, m \\ &\qquad A\mathbf{x} = \mathbf{b} \end{aligned}$

其中

• $P_i \in \mathbb{R}^n_+$

利用Lagrange乘子法

$L(\mathbf{x}, \lambda) = \frac{1}{2}\mathbf{x}^TA\mathbf{x} + \mathbf{c}^T\mathbf{x} + \lambda^T(A\mathbf{x} - \mathbf{b})$

令$L(\mathbf{x}, \lambda)$对$\mathbf{x}$和$\lambda$的导数为零，得

$\begin{aligned} A\mathbf{x} + \mathbf{c}^T + A^T\lambda = 0 \\ A\mathbf{x} - \mathbf{b} = 0 \end{aligned}$

解得$\mathbf{x}$即可

二次约束二次规划

$\begin{aligned} min &\qquad f(\mathbf{x})=\frac{1}{2}\mathbf{x}^TP_0\mathbf{x} + \mathbf{c}_0^T\mathbf{x} + d_0 \\ s.t. &\qquad \frac{1}{2}\mathbf{x}^TP_i\mathbf{x} + \mathbf{c}^T_i\mathbf{x} + d_i \leq 0 \qquad i = 1, \cdots, m \\ &\qquad A\mathbf{x} = \mathbf{b} \end{aligned}$

其中

• $P_i \in \mathbb{R}^n_+$