最优化方法学习笔记

明年再来，我给你加位。

Chapter1

1.1 向量

向量：一个有序的数字列表
可写成
$\begin{bmatrix}-1.1 \\ 0.0 \\ 3.6 \\ -7.2\end{bmatrix} or \begin{pmatrix}-1.1 \\ 0.0 \\ 3.6 \\ -7.2\end{pmatrix} or \begin{pmatrix}-1.1, 0.0, 3.6, -7.2\end{pmatrix}$
列表中的数字是元素（项、系数、分量）
元素的数量是向量的大小（维数、长度），大小为n的向量称为n维向量
向量中的数字通常被称作标量

向量默认为列向量

1.1.1 向量的符号表示

$a_i$ 中的 $i$ 表示为索引，注意：有时i指的是向量列表中的第i个向量
对于所有 $i$ ，如果有 $a_i=b_i$ ，则称两个相同大小的向量 $a$ 和 $b$ 是相等的，可写成 $a=b$

1.1.2 块向量

块向量 $a = \begin{bmatrix} b \\ c \\ d \end{bmatrix}$ 具有块项 $b$ ， $c$ ， $d$
块向量 $a$ 的大小是 $m+n+p$ （各块项的大小之和）

1.1.3 零向量、全一向量和单位向量

零向量：所有项全为0
全一向量：所有项全为1
单位向量：仅有一个元素为1，其余全为0；当第 $i$ 项为1，其余项为0时表示为 $e_i$

1.1.4 稀疏向量

如果一个向量的许多项是0，该向量为稀疏（Sparse）的
$nnz(x)$ 是指向量中非零的项数（number of non-zeros），有时用 $\ell_0$ 表示
例：零向量，单位向量

1.2 数域

	有理数	实数	复数
符号	$\bold{Q}$	$\bold{R}$	$\bold{C}$
例	$\frac{1}{3}$	$\pi$	$1+i$

数的非空集合P，且其中任意两个数的和、差、积、商（除数不为0）仍属于该集合，则称数集P为一个数域。

1.2 向量空间

设 $V$ 是非空子集， $P$ 是一数域，向量空间 $V$ 满足：

向量加法： $V+V\to V$ ，即 $\forall x,y \in V, x+y \in V$ （加法封闭）
标量乘法： $F \times V \to V$ ，即 $\forall x \in V, \lambda \in P, \lambda x \in v$ （乘法封闭）

上述两种运算满足如下八条规则

$\forall x,y,z \in V, \lambda , \mu \in P:$

交换律： $x+y=y+x$
结合律： $x+(y+z)=(x+y)+z$
$V$ 存在一个零元素，记作 $0$ ， $x+0=x$
存在 $x$ 的负元素，记作 $-x$ ，满足 $x+(-x)=0$
$\forall x \in V, 1x=x,1 \in P$
$\lambda ( \mu x)=( \lambda \mu)x$
$( \lambda + \mu )x= \lambda x + \mu x$
$\lambda(x+y)=\lambda x+\lambda y$

向量空间也被称为线性空间

1.2.1 向量加法的性质

设向量 $a,b,c \in V$ ， $V$ 是一个向量空间，有：

交换律： $a+b=b+a$
结合律： $(a+b)+c=a+(b+c)$
$a+0=0+a=a$
$a-a=0$

1.2.3 一点到另一点的位移

点 $\color{red}{q}$ 到点 $\color{yellow}{p}$ 的位移是 $\color{yellow}{p} \color{grey}- \color{red}{q}$ ，不确定可以找个原点想象一下

1.3 标量与向量的乘法

标量 $\beta$ 与n维向量 $a$ 进行相乘（也可表示为 $a\beta$ ）：

\beta a = \begin{bmatrix} \beta a_1 \\ \vdots \\ \beta a_n\end{bmatrix}

1.3.1 标向量乘法（纯量乘法）的性质

标量 $\beta, \gamma$ ，向量 $a,b$ ：

结合律： $(\beta \gamma )a=\beta(\gamma a)$
左分配律： $(\beta+\gamma)a=\beta a+\gamma a$
右分配律： $\beta(a+b)=\beta a+\beta b$

1.3.2 线性组合

对于向量 $a_1, \cdots , a_m$ 和标量 $\beta_1, \cdots, \beta_m$ ， $\beta_1 a_1 + \cdots + \beta_m a_m$ 是向量的线性组合， $\beta_1, \cdots, \beta_m$ 是该向量的系数

1.4 内积

\langle a, b \rangle = a_1 b_1+a_2 b_2+\cdots + a_n b_n = a^T b

定义：在数域 $\mathbb{R}$ 上的向量空间 $V$ ，定义函数 $\langle\cdot,\cdot \rangle:V \times V \to \mathbb{R}$ ，满足：

$\langle a, a \rangle \ge 0, \forall a \in V$ ，当且仅当a=0时， $\langle a, a \rangle = 0$
$\langle \alpha a + \beta b, c \rangle = \alpha \langle a, c \rangle + \beta \langle b, c \rangle,\forall \alpha, \beta \in \mathbb{R}$ ,且 $a,b,c \in V$
$\langle a, b \rangle = \langle b, a \rangle, \forall a,b \in V$

则函数 $\langle\cdot,\cdot \rangle$ 称为内积

1.4.1 内积的性质

交换律： $a^T b=b^T a$
结合律： $(\gamma a)^T b = \gamma (a^T b)$
分配律： $(a+b)^T c = a^T c + b^T c$

1.4.2 常用的内积等式

选出第 $i$ 项： $e_i^T a = a_i$
向量每一项之和： $\bold{1}^T a = a_1 + \cdots + a_n$
向量每一项的平方和： $a^T a = a_1^2+\cdots +a_n^2$

1.4.3 柯西-施瓦茨不等式(Cauchy-Schwartzn)

设 $\langle\cdot,\cdot \rangle$ 是向量空间 $V$ 上的内积， $\forall x,y \in V$ ，有

|\langle x,y \rangle |^2 \le \langle x,x \rangle \langle y,y \rangle

当 $x=\beta y, \beta \in \mathbb{R}$ 等式成立

Chapter2

2.1 线性函数

线性函数： $f: \mathbb{R}^n \to \mathbb{R. f}$ 是一个将n维向量映射成数的函数
线性函数 $f$ 满足（ $k\in \mathbb{R}, x,y \in \mathbb{R}^n$ ）:
- 齐次性（homogeneity）： $f(kx)=kf(x)$
- 叠加性（Additivity）： $f(x+y)=f(x)+f(y)$
一个函数如果满足这两个性质，就称其为线性函数

2.1.1 内积函数

对于n维向量 $a$ ，满足以下形式的函数成为内积函数（inner product function）：

f(x)=a^T x=a_1 x_1 + a_2 x_2 + \cdots + a_n x_n

内积函数都是线性的

2.1.2 所有线性函数都是内积

线性函数表示为内积形式：

\begin{aligned} f(x)&=f(x_1 e_1 + x_2 e_2 + \cdots + x_n e_n)\\ &= x_1 f(e_1) + x_2 f(e_2) + \cdots + x_n f(e_n) \end{aligned}

此时表示为内积形式（ $f(e_n)$ 为常量对应 $a_n$ ）

2.1.3 仿射函数

定义：一个线性函数加上一个常数称为仿射函数(affine function)
一般形式为 $f(x)=a^T x+b, \space a \in \mathbb{R}^n,b \in \mathbb{R}$
函数 $f:\mathbb{R}^n \to \mathbb{R}$ 满足：

f(\alpha x + \beta y)=\alpha f(x) + \beta f(y), \space \alpha + \beta =1,\alpha, \beta \in \mathbb{R},x,y \in \mathbb{R} ^n

2.2 梯度与偏导

假设： $f:\mathbb{R}^n \to \mathbb{R}$ ，函数 $f$ 在 $z$ 点可微，其第 $i$ 个分量的一阶偏导为：

\begin{aligned} \frac{\partial f}{\partial z_i}(z) &=\lim_{t \to 0} \frac{f(z_1,\cdots,z_{i-1},z_i+t,z_{i+1},\cdots,z_n)-f(z)}{t} \\ &=\lim_{t \to 0} \frac{f(z+te_i)-f(z)}{t} \end{aligned}

$f$ 在点 $z$ 的梯度为：

\nabla f(z)=\begin{bmatrix} \frac{\partial f}{\partial z_1}(z) \\ \vdots \\ \frac{\partial f}{\partial z_n}(z)\end{bmatrix}

2.2 一阶泰勒近似

假设： $f:\mathbb{R}^n \to \mathbb{R}$ ，函数 $f$ 在 $z$ 点可导，其附近的一阶泰勒公式为：

\hat{f}(x)=f(z)+\frac{\partial f}{\partial x_1}(z)(x_1-z)+\frac{\partial f}{\partial x_2}(z)(x_2-z)+\cdots+\frac{\partial f}{\partial x_n}(z)(x_n-z)

当 $x$ 非常接近 $z$ 时， $\hat{f}(x)$ 也非常接近 $f(z)$
$\hat{f}(x)$ 是一个关于 $x$ 的仿射函数

写成内积形式：

\hat{f}(x)=f(z)+\nabla f(z)^T(x-z) \\ \nabla f(z)=\begin{bmatrix} \frac{\partial f}{\partial x_1}(z) \\ \vdots \\ \frac{\partial f}{\partial x_n}(z) \end{bmatrix}

2.3 回归模型

\hat{y}=x^T\beta+v

$x$ 是特征向量，它的元素 $x_i$ 称为回归元
n维向量 $\beta$ 是权重向量
标量 $v$ 是偏移量
标量 $\hat{y}$ 是预测值

Chapter3

3.1 范数

向量范数：在向量空间中存在一个函数 $||\cdot||:\mathbb{R}^n\to\mathbb{R}$ ，且满足以下条件：

齐次性： $||\alpha x||=|\alpha|||x||,\alpha \in \mathbb{R}且x \in \mathbb{R}^n$
三角不等性： $||x+y|| \le ||x||+||y||,x,y \in \mathbb{R}^n$
非负性： $||x|| \ge 0,x\in \mathbb{R}^n 且 ||x||=0 \Leftrightarrow x=0$

则称 $||\cdot ||$ 为向量范数

常用的范数与不等式（抄在书上）

$\ell_1$ -范数（曼哈顿范数）

||x||_1=|x_1|+|x_2|+ \cdots +|x_n|,x,y \in \bold{R}^n,\alpha \in \bold{R}

$\ell_2$ -范数（欧几里得范数，一般的 $||\cdot||$ 也是）

||x||_2=\sqrt{(x_1^2+x_2^2+ \cdots +x_n^2)}=\sqrt{x^Tx}=(\langle x,x \rangle )^\frac{1}{2}

$\ell_p$ -范数

||x||_p=(|x_1|^p+|x_2|^p+\cdots+|x_n|^p)^\frac{1}{p},x \in \mathbb{R}^n

$\ell_\infin$ -范数

||x||_\infin = \max_{1 \le i \le n} |x_i|,x \in \bold{R}^n

$\ell_0$ -范数（非0元素的个数）

||x||_0=nnz(x)

柯西-施瓦茨不等式

可用于证明 $\ell_2$ -范数的三角不等性

|\langle x,y \rangle |^2 \le \langle x,x \rangle \langle y,y \rangle = ||x||_2^2 ||y||_2^2

Minkowshi不等式

可用于证明 $\ell_p$ -范数的三角不等性

(\sum_{i=1}^n |x_i+y_i|^p)^\frac{1}{p} \le (\sum_{i=1}^n|x_i|^p)^\frac{1}{p} + (\sum_{i=1}^n|y_i|^p)^\frac{1}{p},p \ge 1, x,y \in \bold{R}^n

Hölder不等式

\sum_{i=1}^n |x_iy_i| \le (\sum_{i=1}^n|x_i|^p)^\frac{1}{p} (\sum_{i=1}^n|y_i|^p)^\frac{1}{p},\frac{1}{p}+\frac{1}{q}=1,1<p,q<\infin

3.1.1 均方根

n维向量 $x$ 的均方值：

\frac{x_1^2+x_2^2+\cdots+x_n^2}{n}=\frac{||x||_2^2}{n}

n维向量 $x$ 的均方根：

\mathit{rms}(x)=\sqrt{\frac{x_1^2+x_2^2+\cdots+x_n^2}{n}}=\frac{||x||_2}{\sqrt n}

3.1.2 切比雪夫不等式

假设k为向量 $x$ 分量满足条件 $|x_i|\ge a$ 的个数

则： $||x||_2^2=x_1^2+x_2^2+\cdots + x_n^2 \ge ka^2$

即： $k\le \frac{||x||_2^2}{a^2}$

即满足 $|x_i|\ge a$ 的 $x_i$ 个数不会超过 $\frac{||x||_2^2}{a^2}$

使用均方根来描述即为：

\frac{k}{n}\le (\frac{\mathit{rms}(x)}{a})^2

例：不超过 $4\%$ 的项满足 $|x_i| \ge 5 \times \mathit{rms}(x)$

3.2 距离

n维向量 $a$ 和 $b$ 之间的欧氏距离：

\mathit{dist}(a,b)=||a-b||_2

3.2.1 三角不等式

顶点为 $a,b,c$
两点之间的距离大于0，如 $||a-b||_2 > 0$
第三边长度不大于另外两边之和，即三角不等式关系：

||a-c||_2=||(a-b)+(b-c)||_2\le ||a-b||_2+||b-c||_2

3.2.2 特征距离与最近邻

对于特征向量 $x$ 和 $y$ ，它们的特征距离为 $||x-y||_2$
对于向量 $x$ ，在一组向量 $z_1,z_2,\cdots,z_m$ 中找到 $z_j$ 满足： $||x-z_j||_2 \le ||x-z_i||_2,\space i=1,\cdots,m$
则 $z_j$ 是 $x$ 的最近邻

3.3 标准差

平均值：

\mathit{avg}(x)=\frac{\bold1^Tx}{n}

去均值向量：

\tilde{x}=x-\mathit{avg}(x)\bold1

标准差：

\mathit{std}(x)=\mathit{rms}(\tilde{x})=\frac{||x-(\bold1^Tx/n)\bold1||_2}{\sqrt n}

\mathit{rms}(x)^2=\mathit{avg}(x)^2+\mathit{std}(x)^2

3.4 角

\angle(a,b)=\arccos(\frac{a^Tb}{||a||_2||b||_2})

Chapter4

4.1 优化问题

假设 $N$ 个样本向量 $x_1,x_2,\cdots,x_N\in \mathbb{R}^n$ ，需要找到中心向量 $z$ 满足：

\min_{z\in \mathbb R^n}\sum_{i=1}^N ||x_i-z||_2^2

4.1.1 渐近符号

高阶无穷小记号 $o$

设 $x,y$ 是同一变化过程中的无穷小，即 $x \to 0, y\to 0$ ，如果它们极限

\lim \frac y x = 0

则称 $y$ 是 $x$ 的高阶无穷小，记作 $y=o(x)$

4.1.2 必要条件

假设函数 $f$ 在 $\hat x$ 可微，则有

\hat x = \argmin_{x \ in\mathbb{R}^n} f(x) \Rightarrow \nabla f(\hat x)=0

$\nabla f(\hat x)=0$ 是最优问题解的必要条件

\nabla f(\hat x)=0\nLeftrightarrow \hat x = \argmin_{x \in \mathbb{R}^n} f(x)

有可能意味着最大值

4.2 凸集

定义域为 $\Omega \in \mathbb{R}^n$ 成为凸的(Convex)集合，则 $\forall x,y \in \Omega, \alpha \in \mathbb{R},0 \le \alpha \le 1$ 有

\alpha x + (1-\alpha)y \in \Omega

4.2 凸函数

满足

f(\alpha x + (1-\alpha )y) \le \alpha f(x) + (1-\alpha) f(y), \\ \forall x,y \in \Omega,\alpha \in \bold R, 0\le\alpha\le 1

引理：可微函数 $f$ 是凸函数的充要条件(应该不会考)，见证明：

f(y) \ge f(x) + \langle \nabla f(x), y-x \rangle , \forall x,y

定理：如果可微函数 $f$ 是凸函数，则有：

\hat x = \argmin_{x \in \mathbb{R}^n} \Leftrightarrow \nabla f(\hat x) = 0

4.3 优化问题

向量偏导

就是求偏导

聚类中心

假设 $N$ 个样本向量 $x_1,x_2,\cdots,x_N\in \mathbb{R}^n$ ，需要找到中心向量z满足：

\min_{z\in \mathbb R^n}\sum_{i=1}^N ||x_i-z||_2^2

\begin{aligned}f(z)&= \min_{z\in \mathbb R^n}\sum_{i=1}^N ||x_i-z||_2^2 \\ &= \sum_{i=1}^N \langle x_i-z,x_i-z \rangle \\ &= \sum_{i=1}^N \{ x_i^Tx_i - 2x_i^Tz + z^Tz \} \end{aligned}

\nabla f(z)=\sum_{i=1}^N \{ -2x_i + 2z \} =0

z=\frac{1}{N} \sum_{i=1}^N x_i

标量

同上，优化问题的思路基本是求偏导，找到偏导为0的情况

4.4 聚类

分成k个集合尽量使得同一个集合中的向量彼此接近

聚类目标：找到簇 $c$ 与聚类中心 $z$ 使得

c_i=\argmin_{z_j} \sum_{j=\{ 1, \cdots, k \} } || x_i - z_j||_2^2,i=1,2,\cdots , N

4.4 k-means

懒得写了，看看实验报告吧

Chapter5

5.1 线性相关

对于向量 $a_1,\cdots,a_m\in\mathbb{R}^n$ ，如果存在不全为0的数 $\beta_1,\cdots,\beta_m\in\mathbb{R}$ ，使得

\beta_1 a_1 + \cdots + \beta_m a_m = 0

则称向量 $a_1,\cdots,a_m$ 线性相关

等价于：至少有一个向量 $a_i$ 是其他向量的线性组合

5.2 线性无关(又叫线性独立)

向量 $a_1,\cdots,a_m\in\mathbb{R}^n$ 线性无关，即

\beta_1 a_1 + \cdots + \beta_m a_m =0

当且仅当 $\beta_1=\cdots=\beta_m=0$ ，上述等式成立

等价于：不存在一个向量 $a_i$ 是其他向量的线性组合

一个n维向量集最多有n个线性无关的向量

5.2.1 线性无关向量的线性组合

线性无关向量 $a_1,\cdots,a_k$ 的线性组合的系数是唯一的

5.3 基

n个线性相关的n维向量 $a_1,\cdots,a_n$ 的集合称为基

任何一个n维向量 $b$ 都可以用它们的线性组合来表示

b=\beta_1 a_1 + \cdots + \beta_n a_n

5.4 标准正交向量

对于 $a_1,\cdots,a_m\in\mathbb{R}^n$

相互正交：

a_i^Ta_j = 0,i \ne j

标准正交(每个向量的模长都为单位长度1):

a_i^Ta_j=\begin{cases} 1 ,\ i=j \\ 0, \ i \ne j\end{cases}

当m=n时， $a_1,\cdots, a_n$ 是n维向量的一个标准正交基

5.4.2 标准正交分解

$a_1,\cdots, a_n$ 是n维向量的一个标准正交基，对于任意n维向量 $x$ ：

x=(a_1^Tx)a_1+\cdots+(a_n^Tx)a_n

验证上式两边同乘任意 $a_i$ ：

a_i^Tx=(a_1^Tx)a_i^Ta_1+\cdots+(a_i^Tx)a_i^Ta_i+\cdots+(a_n^Tx)a_i^Ta_n=a_i^Tx

5.5 Gram-Schmidt(正交化)算法

对于n维向量 $a_1,\cdots,a_k$ ，将其标准正交化。见[流程](最优化方法例题解法 - 没有秃头基因的燊的博客 (yzs020220.github.io))

时间复杂度为 $2nk^2$

Chapter6

涉及概念较多，很多不一定考，看ppt吧(题型主要是从矩阵计算分解到向量计算)

6.11 矩阵乘法

不要记混了，行(左)与列(右)元素一一对应相乘之后相加

C_{ij}=\sum_{k=1}^P A_{ik}B_{kj}

Chapter7

7.1 矩阵左逆

当一个矩阵 $X$ 满足 $XA=I$ 时， $X$ 被称为 $A$ 的左逆

7.2 矩阵右逆

当一个矩阵 $X$ 满足 $AX=I$ 时， $X$ 被称为 $A$ 的右逆

7.3 性质

一个大小为 $m × n$ 的矩阵，其左逆或右逆的维度为 $n × m$
A的左逆为X当且仅当 $X^T$ 是 $A^T$ 的右逆
A的右逆为X当且仅当 $X^T$ 是 $A^T$ 的左逆

7.4 矩阵的逆

如果矩阵A存在左逆和右逆，则左逆和右逆一定相等

XA=I,AY=I \Rightarrow X=XI=X(AY)=(XA)Y=Y

矩阵 $X$ 记作 $A^{-1}$

7.7 非奇异矩阵

对于方阵 $A \in \mathbb{R}^{n\times n}$ ，以下条件都是等价的

A可左逆
A的列向量线性无关
A可右逆
A的行向量线性无关

7.12 Gram矩阵

实矩阵：

G=A^TA

复矩阵：

G=A^HA

7.14 伪逆

矩阵 $A \in \mathbb{R}^{m\times n}$ ,当 $m\ge n$ 时，列向量线性无关，即 $A^TA$ 可逆

定义伪逆：

A^+=(A^TA)^{-1}A^T

为矩阵A的左逆：

A^+A=(A^TA)^{-1}A^TA=(A^TA)^{-1}(A^TA)=I

当A为方阵，伪逆等于矩阵的逆

矩阵 $A \in \mathbb{R}^{m\times n}$ ,当 $m\le n$ 时，行向量线性无关，即 $AA^T$ 可逆

定义伪逆：

A^\dagger=A^T(AA^T)^{-1}

伪逆 $A^\dagger$ 为A的右逆

AA^\dagger=AA^T(AA^T)^{-1}=(AA^T)^{-1}(AA^T)=I

当A为方阵，伪逆等于矩阵的逆

Chapter8

8.2 标准列正交矩阵

如果A的Gram矩阵为单位矩阵，则 $A\in \mathbb R^{m\times n}$ 具有标准正交列：

A^TA=I

8.5 正交矩阵

定义：所有列两两相互正交的方形实矩阵称为正交矩阵

如果矩阵 $A$ 正交则

$A$ 是可逆的，左逆等于右逆，且逆为 $A^T$

\left. \begin{aligned} A^TA=I \\ A是方的 \end{aligned}\right \} \Rightarrow AA^T=I

$A^T$ 也是一个正交矩阵
$A$ 的行是标准正交的，即范数为1且相互正交

8.6 置换矩阵

置换矩阵 $A$ 在每一行和每一列中都有一个等于1的元素，置换矩阵满足正交性：

$A^TA=I$
$A^T=A^{-1}$ 是逆置换矩阵

Chapter9

9.1 三角矩阵

上三角矩阵(Upper)
下三角矩阵(Lower)
对角元素都为1称为单位上三角矩阵/下三角矩阵

9.2 前向回代

$A$ 是具有非零对角元素的下三角矩阵，解 $Ax=b$

\begin{aligned} &x_1=b_1/A_{11} \\ &x_2=(b_2-A_{21}x_1)/A_{22} \\ &x_3=(b_3-A_{31}x_1-A_{32}x_2)/A_{33} \\ & \ \ \vdots \\ &x_n=(b_n-A_{n1}x_1-A_{n2}x_2-\cdots-A_{n,n-1}x_{n-1})/A_{nn} \end{aligned}

9.3 后向回代

$A$ 是具有非零对角元素的上三角矩阵，解 $Ax=b$

\begin{aligned} &x_n=b_n/A_{nn} \\ &x_{n-1}=(b_{n-1}-A_{n-1,n}x_n)/A_{n-1,n-1} \\ &x_{n-2}=(b_{n-2}-A_{n-2,n-1}x_{n-1}-A_{n-2,n}x_n)/A_{n-2,n-2} \\ & \ \ \vdots \\ &x_1=(b_1-A_{12}x_2-A_{13}x_3-\cdots-A_{1n}x_{n})/A_{11} \end{aligned}

9.4 三角矩阵的逆矩阵

矩阵 $A$ 的逆可以通过逐列解方程 $AX=I$ 来计算得到

9.5 QR分解

如果矩阵 $A\in \R^{m\times n}$ 的列向量线性无关，则可以分解为一组标准正交向量 $Q$ 与上三角矩阵 $R$

\begin{aligned} A&=\begin{bmatrix}a_1& a_2& \cdots & a_n\end{bmatrix} \\ &=\begin{bmatrix}q_1& q_2& \cdots & q_n \end{bmatrix} \begin{bmatrix} R_{11}& R_{12}& \cdots & R_{1n} \\ 0& R_{22} & \cdots & R_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & R_{nn} \end{bmatrix} \\ &= QR \end{aligned}

Gram-Schmidt正交化

\tilde{q_i}=a_i-(q_1^Ta_i)q_1-\cdots-(q_{i-1}^Ta_i)q_{i-1}

R_{ji}=(q_j^Ta_i)

一般要求 $R_{ii}>0$ 使得 $Q$ 和 $R$ 是唯一的

9.6 QR分解和伪逆

具有线性无关列向量的矩阵 $A$ 的伪逆为

A^+=(A^TA)^{-1}A^T

将 $A$ 的伪逆表示为 $QR$ 因子：

\begin{aligned} A^+ &= \left( (QR)^T(QR) \right)^{-1}(QR)^T \\ &= (R^TQ^TQR)^{-1}R^TQ^T \\ &= (R^TR)^{-1}R^TQ^T \\ &= R^{-1}R^{-T}R^TQ^T \\ &= R^{-1}Q^T \end{aligned}

对于方阵非奇异矩阵 $A$ ，其逆为：

A^{-1}=(QR)^{-1}=R^{-1}Q^T

Chapter10

10.2 应用QR分解

计算非奇异矩阵 $A\in \R^{n\times n}$ 的逆 $A^{-1}$ ，通过 $AX=I$ ，即 $QRX=I$

\begin{aligned} &X=[x_1,x_2,\cdots,x_n],x_i\in\R^n,i=1,\cdots,n \\ &I=[e_1,e_2,\cdots,e_n],e_i\in\R^n,i=1,\cdots,n \\ &QRX=I \Rightarrow RX=Q^TI \\ &Rx_1=Q^Te_1,Rx_2=Q^Te_2,\cdots,Rx_n=Q^Te_n \end{aligned}

回代法求解

10.3 LU分解

$L$ 为下三角矩阵且对角线元素全为1， $U$ 为上三角矩阵

A=LU

矩阵 $U$ 的第一行元素：

u_{1j}=a_{1j},j=1,\cdots,n

矩阵 $L$ 的第一列元素：

l_{i1}=\frac{a_{i1}}{u_{11}},i=2,3,\cdots,n

从 $r=2$ 开始直到 $r=n$

矩阵 $U$ 第r行主对角线以右元素 $u_{rj}$

u_{rj}=a_{rj}-\sum_{k=1}^{r-1}l_{rk}u_{kj},j=r,\cdots,n

矩阵 $L$ 第r列主对角线以下元素 $l_{ir}$

l_{ir}=\left(a_{ir}- \sum_{k=1}^{r-1} l_{ik}u_{kr} \right)/u_{rr},i=r+1,\cdots,n

10.4 LU求解方程

求解 $Ax=b$

对矩阵 $A$ 进行LU分解
回代法求出 $y$ ： $Ax=LUx=Ly=b$
回代法求出 $x$ ： $Ux=b$

Chapter11

11.2 最小二乘法

寻找超定方程组(方程组系数矩阵为高矩阵，可能无解)的近似解，并尽可能地逼近方程组的目标 $b$ ：

\min_x ||Ax-b||_2^2 = \min_x \sum_{i=1}^m (\sum_{j=1}^n A_{ij}x_j - b_j)^2

对 $x$ 上的 $x_i$ 求偏导，当 $\nabla f(x)=0$ 时，得到 $\hat x$ 即为近似解

当残差 $\hat r=A\hat x - b=0$ 时， $\hat x$ 是线性方程组 $Ax=b$ 的解，否则为误差最小平方和下方程组的近似解

11.5 目标求解

\nabla f(x)= 2(A^TAx-A^Tb)=0 \Rightarrow A^TAx = A^Tb

则在 $A$ 的列向量线性无关时， $\hat x=(A^TA)^{-1}A^Tb$

11.7 正规方程

A^TAx=A^Tb

若 $A$ 列向量线性无关，则

$A^TA$ 为非奇异矩阵
正规方程此时有唯一解

11.8 QR分解求解正规方程

若矩阵 $A$ 列向量线性无关，则最小二乘法问题的解：

\begin{aligned} \hat x &= (A^TA)^{-1}A^Tb \\ &= (R^TQ^TQR)^{-1} R^TQ^Tb \\ &= (R^TR)^{-1}R^TQ^Tb \\ &= R^{-1}Q^Tb \end{aligned}

流程：

对矩阵 $A$ 进行QR分解
计算矩阵向量乘积 $d=Q^Tb$
通过回代法求解 $Rx=d$

Chapter13

13.1 约束优化问题

\min_x \left \{ f(x) \right \} \quad s.t. \quad h(x)=0

引入拉格朗日函数：

L(x,\lambda)=f(x)-\lambda h(x)

对拉格朗日函数求偏导：

\begin{cases} \nabla_xL(x,\lambda)=\nabla_x f(x)-\lambda \nabla_x h(x)=0 \\ \nabla_\lambda L(x,\lambda)=-h(x)=0 \end{cases}

13.1 KKT条件：必要条件

\min_x/\max f(x) \\ \begin{aligned} s.t. \quad & h_i(x)=0, \ i\in I \triangleq \left \{ 1, \cdots,p\right \} \\ & g_j(x) \le 0, \ j\in J \triangleq \{ 1, \cdots ,q \} \end{aligned}

引入拉格朗日函数：

L(x,\lambda,\mu) = f(x)-\sum_{i\in I} \lambda_ih_i(x) - \sum_{j\in J} \mu_jg_j(x)

KKT条件：

\begin{aligned} &\nabla_xL(x,\lambda,u)=\nabla_xf(x)- \sum_{i \in I} \lambda_i \nabla_x h_i(x) -\sum_{j \in J}u_j\nabla_xg_j(x) =0 \\ &\sum_{i\in I}\lambda_ih_i(x)=0,h_i(x)=0 \\ &\sum_{j\in J}u_j g_j(x)=0,g_j(x)\le0,u_j \ge 0(不全为0) \end{aligned}