向量范数
向量一范数：$||X||_1=\sum\limits_{i=1}^n|x_i|$
向量二范数：$||X||_2=(\sum\limits_{i=1}^nx_i^2)^{\frac{1}{2}}=\sqrt{\sum\limits_{i=1}^nx_i^2}$
向量无穷范数：$||X||_{\infty}=\max\limits_{i\le i\le n}|x_i|$
不等式
柯西不等式
对于实数：$|\sum\limits_{i=1}^{n}a_i|\le \sum\limits_{i=1}^n|a_i|,a_i\in \mathbb{R}$
对于向量形式：$(\sum\limits_{i=1}^na_ib_i)^2\le \sum\limits_{i=1}^na_i^2 \sum\limits_{i=1}^nb_i^2\leftrightarrow| \lt a,b \gt|\le ||a|| \cdot ||b||$
证明：
右边-左边$=\sum\limits_{ij}(a_ib_j-a_jb_i)^2\ge0$
??：
$\forall \lambda \ge 0,\sum\limits_{i=1}^n(a_i-\lambda b_i)^2\ge0$
$\sum\limits_{i=1}^n(a_i^2-2a_ib_i\lambda+b_i^2\lambda^2) \ge 0 \\ (\sum\limits_{i=1}^{n}b_i^2)\lambda^2-2(\sum\limits_{i=1}^na_ib_i)\lambda+\sum\limits_{i=1}^na_i^2\ge 0$
这是关于$\lambda$的二次函数
算数几何平均不等式
$(a_1,a_2,…a_n)$
算数平均值：$\frac{\sum\limits_{i=1}^na_i}{n}$
几何平均值：$(\prod\limits_{i=1}^na_i)^\frac{1}{n}$
算数平均值大于等于几何平均值
$\frac{\sum\limits_{i=1}^na_i}{n} \ge (\prod\limits_{i=1}^na_i)^\frac{1}{n}$
证明
$n=2$时：
$\frac{1}{2}(a_1+a_2)\ge \sqrt{a_1a_2}\\ \leftrightarrow(a_1+a_2)^2\ge4a_1a_2\\ \leftrightarrow (a_1-a_2)^2 \ge 0$
$n=3$时：
$\frac{1}{2}(a_1+a_2+a_3)\ge (a_1a_2a_3)^{\frac{1}{3}}\\ \leftrightarrow x^3+y^3+z^3 \ge 3xyz\\ \leftrightarrow (x+y+z)((x-y)^2+(y-z)^2+(z-x)^2) \ge 0$
极限
序列$a_n$收敛跟$a_n$时柯西列等价
单调有界序列一定有极限
- $\lim\limits_{n\to\infty}(1+\frac{1}{n})^n=e$
- $|a_n| \le b_n$， $\sum\limits_{n\ge 1}b_n$收敛那么$\sum\limits_{n\ge 1}a_n$收敛
- 上极限：$\lim\limits_{n\to \infty}\sup a_n \triangleq \lim\limits_{n\to \infty}(\sup\limits_{m\ge n}a_m) = \inf\limits_{n\ge 1}(\sup\limits_{m\ge n} a_m)$
- 下极限：$\lim\limits_{n\to \infty}\inf a_n \triangleq \lim\limits_{n\to \infty}(\inf\limits_{m\ge n}a_m) = \sup\limits_{n\ge 1}(\inf\limits_{m\ge n} a_m)$
- $\sum\limits_{n\ge 1}\frac{1}{n^s}$收敛$\iff\ s>1$，$\sum\limits_{n\ge 1}\frac{1}{n}$发散
- $\sum\limits_{n\ge 2}\frac{1}{n(\log n)^s}$收敛$\iff\ s>1$，$\sum\limits_{n\ge 2}\frac{1}{n(\log n)}$发散
- $\sum\limits_{n\ge0}\frac{(-1)^n}{2n+1}=\frac{\pi}{4}$
点集
开集，闭集，紧集
开集
定义： $A \subset \mathbb{R}^n, \forall x \in A$都存在以$x$为中心，$r>0$为半径的一个球$\{y\in\mathbb{R}^n: ||y-x|| < r\}$叫做$B(x,r)$ 然后$B(x,r)\subset A$。
性质：
- 任意个开集并，那么也是开集$\cup A_i$
- 有限个开集交，那么也是开集 $\cap^NA_i$
闭集
$A$闭集 $\iff A^C$开集
$\{ x_k\}_{k\ge 1} \subset A, \lim\limits_{k\to \infty}x_k = x \in A$
$x_k$序列属于$A$，并且$x_k$的极限在$A$中，那么$x$也属于$A$
紧集
$A$称为紧集，如果$A$是有界闭集，即$A$是闭集并且存在开球$B(x,r)$使得$A\subset B(x,r)$
空集和实数集
空集：是开集，是闭集，是紧集
实数集：是开集，是闭集，不是紧集
连续
连续函数： $\lim\limits_{x\to a}f(x)=f(a)$
- $\forall \gt 0, \exists\delta\gt0$使得对于任何满足条件$||x-a||\lt\delta$的$x$都成立$|f(x)-f(a)|<\epsilon$
若$f:D\subset \mathbb{R}^n \to \mathbb{R}$，那么$|f(x)-f(y)|\le k||x-y||$对于任何属于$D$的$x,y$都成立
若$f:D\subset \mathbb{R}^n \to \mathbb{R}$在$D$中任何点都连续，则称其在$D$上连续
- $f$在开集$D$上连续，等价于，对于任何开集$U\subset \mathbb{R}$，其逆像$f^{-1}(U)=\{x\in\mathbb{R}^n : f(x)\in U\}\subset \mathbb{R}^n$仍是开集
常用函数(幂指对，三角函数，多项式)都是连续函数
两个重要函数极限
- $\lim\limits_{x\to 0}\frac{sinx}{x}=1$
- $0\lt x \lt \frac{\pi}{2} \Longrightarrow cosx \lt \frac{sinx}{x} \lt 1$
- 因此，函数$\frac{sinx}{x}$可看作定义在$\mathbb{R}$上的连续函数
- $\lim\limits_{x\to +\infty}(1+\frac{1}{x})^x=e$
- $n\le x \le n+1 \Longrightarrow (1+\frac{1}{n+1})^n \lt (1+\frac{1}{x})^x \lt (1+\frac{1}{n})^{n+1}$
介值定理
函数$f:[a,b]\to \mathbb{R}$连续，且$f(a)\not= f(b)$,则对于任何$f(a)$和$f(b)$之间的值$s$,都存在$x\in (a,b)$使得$f(x)=s$
导数
可导$\Longrightarrow$连续,可导$\not\Longleftarrow$连续
$(fg)’=f’g+fg’,(af+bg)’=af’+bg’,(\frac{f}{g})’=\frac{f’g-fg’}{g^2}$
- 链式法则：$(f(g(x)))’=f’(g(x))g’(x)$
- $f(x) = det(I+xA),f’(0)=tr(A)$
- $f:[a,b]\to\mathbb{R}$,$f$在$x\in (a,b)$取得局部最小值$\Longrightarrow f’(x)=0$
微分中值定理
$f$在$[a,b]$上连续，并在$(a,b)$上可微，则存在$x\in (a,b)$使得$f’(x)=\frac{f(b)-f(a)}{b-a}$
$Rlolle$定理：如果$f(a)=f(b)$，则存在$x\in(a,b)$使得$f’(x)=0$
洛必达法则
假设$f$和$g$在$(a,b)$上可微，并且对于任何$x\in (a,b)$都有$g’(x)\not=0$,如果下述条件满足
- $\lim\limits_{x-\to a}f(x)=\lim\limits_{x\to a}g(x)=0$或者$\lim\limits_{x\to a}g(x)=+\infty$
- $\lim\limits_{x\to a}\frac{f’(x)}{g’(x)}=A$
则有$\lim\limits_{x\to a}\frac{f(x)}{g(x)}=A$
$\frac{f(x)}{g(x)}\approx \frac{f’(x)}{g’(x)}=\lim\limits_{x\to a}\frac{f’(x)}{g’(x)}$
$[a,b]$上的单调函数几乎处处可微
泰勒展开
若$f$在$x_0$的一个邻域内$(n+1)$次可微，则对于该邻域内的任意$x$都成立
$f(x)=\sum\limits_{k=0}^n\frac{f^{(k)}(x_0)}{k!}(x-x_0)^k+R_n(x)$
其中余项$R_n(x)$满足
- 无穷小量形式：$R_n(x)=o((x-x_0)^n)$
- 微分形式：存在$\theta\in(x,x_0)$使得$R_n(x)=\frac{f^{(n+1)}(\theta)}{(n+1)!}(x-x_0)^{(n+1)}$
- 积分形式：$R_n(x)=\frac{1}{n!}\int_{x_0}^x(x-t)^nf^{(n+1)}(t)dt $
- $e^x=\sum\limits_{k=0}^n\frac{x^k}{k!}+o(x^n)$
- $\log(1+x)=\sum\limits_{k=1}^n(-1)^{(k+1)}\frac{x^k}{k}+o(x^n)$
- $\log(1-x)=-\sum\limits_{k=1}^n\frac{x^k}{k}+o(x^n)$
多元微分
一元微分
$f$在点$x$处可微$\iff f(y)=f(x)+a(y-x)+o(y-x),f(x)$是固定的$a(y-x)$可以看成增量$\Delta x,$$o(y-x)$ 是无穷小量
不考虑无穷小量时，$f(y)$可近似看成$f(y)\approx f(x)+a(y-x)$,这个就是关于增量$\Delta x=y-x$的线性函数
这样一元微分就在$x$出展开成了一个线性函数
多元微分
什么是多元函数
多元函数就是在定义域$D\subset\mathbb{R}^n$ 通过某些规则达到$f(x)$
比如$f(x)=||x||_2^2=\sum\limits_{i=1}^nx_i^2$这就是一个多元函数
如果$f:D\subset \mathbb{R}^n \to \mathbb{R}$ 这就代表$f(x)$是一个单值多元函数
如果：$f:D\subset\mathbb{R}^n\to\mathbb{R}^m$,这就代表$f(x)$是一个多值多元函数
关于多值多元函数，可以看成$x\to(f_1(x),\cdots,f_m(x))$其中每个$f$都是一个单值多元函数$f:D\subset\mathbb{R}^n \to \mathbb{R}$
$f(x_1,x_2)=(x_1+x_2, x_1x_2)$这个就是一个$\mathbb{R}^2\to\mathbb{R}^2$的多元函数
多元微分
对多元函数$f:D\subset\mathbb{R}^n\to\mathbb{R}^m$求微分可以借鉴一元微分的方法，在$x$处将微分展开成一个线性函数
$f(y)\approx f(x)+L(y-x)$
$L$是一个线性映射，将$n$维的向量映射成$m$为的向量，也可以说是一个矩阵，$L(y-x)$是作用在$y-x$之上的
$L(y-x)$也可写成$L(y-x)=A(y-x)$,$L(y-x)$是$n\times m$形式的， $y-x$是一个$n\times1$的向量，$A$是一个$m\times$n的矩阵，线性映射可以唯一的写成矩阵形式
对于$f:D\subset \mathbb{R}^n\to \mathbb{R}^m$，如果存在一个矩阵$A$，使得$f(y)=f(x)+A(y-x)+o(||y-x||)$成立，那么就称$f$在点$x\subset D$处可微,$A$记作微分$A=Df(x)$
也可以写成$\exists A \ \ st. \ \ \lim\limits_{y\to x} \frac{||f(y)-f(x)-A(y-x)||}{||y-x||}=0$
例子： $f(x)=Ax+b, A_{m\times n},b\in \mathbb{R}^m$
此时$Df(x)=?$
证明： $f(y)-f(x)\\=Ay+b-(Ax+b)\\=A(y-x)$
所以$f(y)-f(x)=A(y-x)$
那么$\lim\limits_{y\to x} \frac{||f(y)-f(x)-A(y-x)||}{||y-x||}=0$成立，所以$Df(x)=A$
偏导
$f:D\subset\mathbb{R}^n\to\mathbb{R}$,对于这样一个映射，其多元微分可以写成$f(y)=f(x)+Df(x)(y-x)+o(||y-x||)$
其中$Df(x)$是$1\times n$的，所以$Df(x)$也可以看成$v^t$
即$f(y)=f(x)+v^t(y-x)+o(||y-x||)\\f(y)=f(x)+\sum\limits_{i=1}^nv_i(y_i-x_i)+o(||y-x||)$
将$i$固定，$\forall j\not= i,y_j=x_j$，保留一个$i$将其他方向的变量全部固定，这样$x,y$就可以看成处于同一条轴上
此时$f(x_1,\cdots,x_{i-1},y_i,x_{i+1},\cdots,x_n)=f(x_1,\cdots,x_n)+v_i(y_i-x_i)+o(|y_i-x_i|)$
因为$f$函数的所有其他变量全部都固定成了$x_i$,$f(x_1,\cdots,x_{i-1},y_i,x_{i+1},\cdots,x_n)$相当于只有一个自变量$y_i$这样$f(x_1,\cdots,x_{i-1},y_i,x_{i+1},\cdots,x_n)$可以看成是一个关于$y_i$的函数$g(y_i)$,此时$g(y_i)=g(x_1)+v_i(y_i-x_i)+o(|y_i-x_i|)$在这个一元函数中，可以明显发现$g$的微分就是$v_i=g’(x_i)$
其他的$i$都被固定住，求出的这个$g’_i(x_i)$就叫做$f$在$x$处第$i$个方向的偏导数，$g’_i(x_i)$可以写成$\partial_if(x)$
如果偏导存在,那么$Df(x)=(g’_1(x_i),g’_2(x_i),\cdots,g’_n(x_n))=(\partial_1if(x),\cdots,\partial_nif(x))$
将$Df(x)$竖起来的话，就叫做梯度
梯度和偏导
如果$f$在点$x$处可维$\Longrightarrow Df(x)=(\triangledown f(x))^t$，梯度是多元微分的转置，也能推出$f(y)=f(x)+\triangledown f(x)(y-x)+o(||y-x||)$
可微$\Longrightarrow $梯度存在，梯度存在$\not\Longrightarrow$ 可微
当$f:D\in\mathbb{R}^n\to \mathbb{R}，D是开集$，向量每个方向的偏导数$\partial_if(x)$都存在并且连续，此时可以推出来$\Longrightarrow $$f$在$D$上可微
$f$在$D$上偏导存在并且连续，我们记作$f\in C^1(D)$
计算微分
1
对于$A\in \mathbb{R}^{m\times n},b\in \mathbb{R}^m$
计算一个函数$f(x)=||AX-b||^2$的微分
$f(x)$ $ =||AX-b||^2$
$=(AX-b)^t(AX-b)$
$=(X^tA^t-b^t)(AX-b) $
$ = X^tA^tAX-b^tAX-X^tA^tb+b^tb $
$=X^t(A^tA)X-2(A^tb)^tX+b^tb$
这个就是关于$X$的二次函数
$f(x)=\frac{1}{2}X^tpX+q^tX+r,p=2A^tA,q=-2(A^tb)$
此时对$X$微分，梯度就等于$\triangledown f(x)=pX=q=2A^tAX+2A^tb$
梯度转置一下就是微分了
2
$f(x)=e^{w^tx},w,x\in \mathbb{R}^n$求微分
$f(x)$可以看成$f(x)=e^{w_1x_1+w_2x_2+\cdots+w_nx_n}$
求偏导时$\partial_1f(x)=w_1e^{w_1x_1+\cdots+w_nx_n} \\ \partial_if(x)=w_ie^{w_1x_1+\cdots+w_nx_n}$
$\triangledown f(x) = (w_1e^{w_1x_1+\cdots+w_nx_n},\cdots, w_ne^{w_1x_1+\cdots+w_nx_n})^t=f(x)w$
计算出来的梯度为$wf(x)$，因为$f(x)$是连续的，所以梯度也是连续的，那么就可以推出$\triangledown f(x)=(Df(x))^t, Df(x)=f(x)w^t$
复合函数求导
一元函数求导: $g(f(x))’=g’(f(x))f’(x)$
多元函数: $D(g\circ f(x))=D g(f(x))Df(x)$
$g\circ f(x)=g(f(x))$
其中$f:\mathbb{R}^n\to \mathbb{R}^m \\g:\mathbb{R}^m\to \mathbb{R}^k$
$g\circ f(x): \mathbb{R}^n\to \mathbb{R}^k$
一元函数：$(fg)’(x)=f(x)g’(x)+f’(x)=g(x)$
多元函数：$D(fg)(x)=f(x)Dg(x)+g(x)Df(x)$
矩阵微分
$f: D\in \mathbb{R}^{m\times n}\to \mathbb{R}, f(A),A_{m\times n}$
多元函数参数是矩阵时求偏导，实际上$f(A)$的参数是一个$m\times n$的行向量，但是写的时候还是当作矩阵来写
$(Df(A))_{i,j}=\partial_{a_{ij}}f(A)$,对矩阵的第$i,j$位置求偏导
例子：$f(A)=tr(AB),A:m\times n,B: n\times m$，求$Df(A)$
$f(A) = tr(AB)=\sum\limits_{i=1}^m(AB)_{ii}\\ =\sum\limits_{i=1}^m\sum\limits_{j=1}^na_{i,j}b_{j,i}=\sum\limits_{i.j}a_{j,i}b_{i,j}$
此时$f(A)=\sum a_{i,j}b_{j,i}$
$\partial_{a_{i,j}}f(A)=b_{j,i}\\ (Df(A))_{i,j}=b_{j,i}=(B^t)_{i,j}$
$f(A)=tr(AB) \Longrightarrow D(f(A))=B^t$
例子：$f(A)=tr(ABA^t),A:m\times n,B: n\times n$求$Df(A)$
$f(A)$$=tr(ABA^t) \\ =\sum(ABA^t)_{i,i}\\ = \sum (A)_{i,j}(B)_{j,k}(A^t)_{k.i} \\ = \sum (A)_{i,j}(B)_{j,k}(A)_{i,k}\\ =\sum a_{i,j}b_{j,k}a_{i,k}$
此时，为了区分$\partial a_{i,j}f$中的$i,j$,我们将$f(A)$中的$i,j,k$转换成$i’,j’,k’$
$f(A)=\sum a_{i’,j’}b_{j’,k’}a_{i’,k’}\\ \partial_{a_{i,j}}f=\sum \partial_{a_{i,j}}(a_{i’,j’}a_{i’k’})b_{j’,k’}$
在$\partial_{a_{i,j}}$中是两个函数相乘的形式$(fg)’=f’g+g’f$
所以$\partial_{a_{i,j}}f=\sum \partial_{a_{i,j}}(a_{i’,j’})a_{i’k’}b_{j’,k’}+\partial_{a_{i,j}}(a_{i’,k’})a_{i’j’}b_{j’,k’}$
前一项中的$\partial_{a_{i,j}}(a_{i’,j’})$只有在$i’=i,j’=j$是才不为0，所以第一项可以写成$\sum a_{i,k’}b_{j,k’}$
后一项同理$i’=i,k’=j$时才为1，$\sum a_{i,j’}b_{j’,k}$,整理一下$\partial_{a_{i,j}}f=\sum\limits_{k}a_{i,k}b_{j,k}+\sum\limits_{k}a_{i,k}b_{k,j}\\=(AB^t)_{i,j}+(AB)_{i,j}=(AB^t+AB)_{i,j}$
所以$f(A)=tr(ABA^t)\Longrightarrow Df(A)=A(B+B^t)$
$tr(A)=tr(A^t) \\ f(A)=tr(ABA^t)\Longrightarrow A(B+B^t)$
$||A||^2=tr(AA^t)=tr(AIA^t)\\Df(A)=A(I+I^t)=2AI=2A$
例子：$f(A)=x^tA^{-1}x,$ $A$是可逆的$n$阶对称方阵，$x\in \mathbb{R}^n$,求$Df(X0)$
$f(A+ \epsilon) - f(A)\\ =x^t(A+\epsilon)^{-1}x-x^tA^{-1}x \\ = x^t((A+\epsilon)^{-1}-A^{-1})x$
因为$x^t,x$都是常量，所以关键就是$(A+\epsilon)^{-1}-A^{-1}$
$(A+\epsilon)^{-1}-A^{-1}\\ =(I+A^{-1}\epsilon)^{-1}-A^{-1}$
因为$\epsilon$是一个小值，而一个小值可以写成$(I-X)^{-1}=I+X+X^2+X^3+\cdots$
所以，原式=$(I-A^{-1}\epsilon+(A^{-1}\epsilon)^2-(A^{-1}\epsilon)^3+\cdots)A^{-1}-A^{-1} \\ =A^{-1}-A^{-1}\epsilon A^{-1}+(A^{-1}\epsilon)^2 A^{-1}-(A^{-1}\epsilon)^3 A^{-1} + \cdots - A^{-1}\\ = -A^{-1}\epsilon A^{-1} + o(\epsilon)$
后面那些小值可以看成一个关于$\epsilon$的无穷小量
$f(A+\epsilon)-f(A)=x^t(-A^{-1}\epsilon A^{-1} + o(\epsilon))x \\ = -x^tA^{-1}\epsilon A^{-1}x + o(\epsilon) $
$x^tA^{-1}$和$A^{-1}x$都是向量，所以$-x^tA^{-1}\epsilon A^{-1}x$是关于$\epsilon$分量的线性组合
设$A^{-1}x = y,y^t=x^t(A^{-1})^t=x^tA^{-1}$
原式=$-y^t\epsilon y + o(\epsilon)$
$f(A+\epsilon)-f(A) = -\sum\limits_{i,j}y_iy_j\epsilon_{i,j}+o(\epsilon)$
偏微分就为：$\partial_{a_{i,j}}f(A)=-y_iy_j = -(yy^t)_{i,j}$
导数就为：$Df(A)=-yy^t=-A^{-1}x(A^{-1}x)^t=-A^{-1}xx^tA^{-1}$
矩阵二阶展开
多元函数：$\partial_j(\partial_if(x))$等价于$\partial_{i,j}f(x)$
对于$f:D\in \mathbb{R}^n \to \mathbb{R}$,如果$\partial_{i,j}f$都存在且连续，称$f$是$D$上二次连续可微的函数$f \in C^2(D)$
$(\partial_{i,j}f)_{1\le i,j \le n}$是一个$n\times n$矩阵 ，称为$Hessian$矩阵，
梯度可以看成是一阶导数，对每个向量求偏导，$Hessian$可以看成是二阶导数，对已经求出的导数再对每个向量求偏导，最终得到的是一个$n\times n$的矩阵
二阶展开： $f(y)=f(x)+Df(x)(y-x)+\frac{1}{2}(y-x)^t(\partial_{i,j}f)(y-x)+D(||y-x||^2)$
因为$Df(x)$是梯度的转置，而$\partial_{i,j}f$可以写成$\triangledown^2f$
所以也可以写成：$f(y)=f(x)+\triangledown f(x)(y-x)+\frac{1}{2}(y-x)^t\triangledown^2f(x)(y-x)+o(||y-x||^2)$
如果$f(y)=f(x)+q^t(y-x)+\frac{1}{2}(y-x)^tp(y-x)+o(||y-x||^2),$其中$q=\triangledown f(x),p=\triangledown ^2 f(x)$
优化
对于定义域在$D$上的函数$f$找极小值
如果存在$x’$，在$x’$的邻域$B(x’,r)$内，所有值都小于$f(x’)$的$f(x’)\le f(x)$，那么$x’$就是这个函数在$B(x’,r)$的局部极小值
局部极小值必要条件
$x’$是局部极小值$\Longrightarrow$ $Df(x^{})=0,\triangledown^2f(x^{})\ge 0$
半正定矩阵: $P \Longleftrightarrow x^tPx \ge 0, \forall x \in \mathbb{R}^n$
正定矩阵: $P \Longleftrightarrow x^tPx > 0, \forall x \in \mathbb{R}^n-\{0\}$
局部极小值充分条件
$Df(x’)=0,\triangledown^2f(x^{*}) > 0$ $\Longrightarrow$ $x’$是局部极小值
无约束优化问题
例子： $f(x)=\frac{1}{2}||Ax-b||^2,A$是$m\times n, rank(A)=m \le n, b\in \mathbb{R}^m$,求局部极小值$x’$
$f(x)$ $ = \frac{1}{2}(Ax-b)^t(Ax-b)\\ = \frac{1}{2}(x^tA^t-b^t)(Ax-b) \\ = \frac{1}{2}x^t(A^tA)x - (A^tb)^tx+\frac{1}{2}b^tb$
令$p = A^tA,q = -A^tb$
原式=$\frac{1}{2}x^tpx+q^tx+r$
那么这是一个关于$x$的二次函数，所以$\triangledown f(x)=A^tAx-A^tb,\triangledown^2f(x)=A^tA$
如果$x’$是局部极小值点，那么$\triangle f(x) = 0 , \triangledown^2f(x) \ge 0$
即$A^tAx = A^tb,A^tA \ge 0$
如果$A^tAx = A^tb,A^tA > 0$那么就能推出$x’$是局部极小
因为$rank(A)$等于$m$,所以$A$是可逆的，那么$x’$就可以用$(A^tA)^{-1}A^tb$求出
例子： $f(x)= \frac{1}{2}||Ax-b||^2 + \frac{\lambda}{2}||x||^2$,求局部最优解$x’$
$x’$ 局部极小值可以推出 $\triangledown f(x’)=A^tAx’-A^tb+\lambda x’=0, \triangledown^2 f(x’)=A^tAI+\lambda \ge 0$
$A^tA+\lambda I\ge0$永远成立，因为$A^tA+\lambda I$可以左右加上$x$，可以写成$x^t(A^tA+\lambda I)x \Longrightarrow ||Ax||^2 + \lambda ||x||^2 \ge 0$
$\triangledown f(x’)=0, \triangledown^2f(x’) > 0$可以推出$x’$是局部极小，当$x$不为零时，$\triangledown^2f(x’)$永远成立
所以$x’$是局部极小值等价于$\triangledown f(x’) = 0 \Longleftrightarrow A^tAx’+\lambda x’=A^tb$
因为$A^A+\lambda I$是正定矩阵，所以是$A^A+\lambda I$可逆的
$A^tAx’+\lambda x’=A^tb \Longleftrightarrow (A^tA+\lambda I)x’ = A^tb \Longleftrightarrow x’ = (A^tA+\lambda I)^{-1}A^tb$
有约束优化问题
线性约束
例子： $\begin{equation} \left\{ \begin{array}{lr} minimize_{x\in D}\ f(x) \\ sub\ to\ Ax = b & A_{p \times n}, rank(A) = p, b\in \mathbb{R}^p \end{array} \right. \end{equation}$
$x$满足线性约束条件，在这个线性约束条件下来找最小值
$x’$满足$Ax’=b$,如果存在$Ax=b$,那么可以推导到$A(x-x’)=0$，此时，$x-x’$是$Ay=0$的解
$\{x: Ax=b\}=x’+\{y: Ay= 0\}$,所有的$y$构成的集合被称为矩阵$A$的零空间$N(A)$，矩阵的零空间是一个线性空间
$N(A):A$的零空间，是一个线性空间
$dim(N(A)) = n-p$
假设$\{\alpha_1,\cdots,\alpha_{n-p} \}$是$N(A)$的一组基，其中$\alpha_1,\cdots,\alpha_{n-p}$线性无关
那么$N(A)=\{ u_1\alpha_1+u_2\alpha_2+\cdots+u_{n-p}\alpha_{n-p}： u_i \in \mathbb{R} \}$，零空间中的所有元素都可以通过基来构造出来
$\alpha_i$是$n\times 1$的向量， 因为 $Ax=b$,$b$ 是$p \times 1$的向量
所以$\{x:Ax=b \}=x’+N(A)$
如果$x$使得$Ax-b=0$，那么可以等价于$x=x’+\sum\limits_{i=1}^{n-p}u_i\alpha_i = x’ + (\alpha_1,\cdots,\alpha_{n-p})\begin{equation} \left( \begin{array}{lr} u_1 \\ \vdots \\ u_{n-p} \end{array} \right) \end{equation}$
将$(\alpha_1,\cdots,\alpha_{n-p})$写成矩阵形式得到一个$n\times (n-p)$的矩阵$B$
$Ax=b \Longleftrightarrow x = x’ + By,B:n\times (n-p), y\in \mathbb{R}^{n-p} \\ \{ x\in \mathbb{R}^n: Ax=b \}=\{ y\in \mathbb{R}^{n-p} \} \Longleftrightarrow x = x’ + By$
$Ax =b$的解就相当于$x = x’ + By$,在$f(x)$中将$x$替换成$x’+By$，即$\min\limits_{y\in \mathbb{R}^{n-p}}f(x’+By)$。
有约束问题通过将约束条件的解求出来，写成一个$x’$加零空间的形式将有约束问题转化成无约束的优化问题
将$f(x’)$做二阶的泰勒展开后得到
$f(x’+\epsilon)=f(x’)+\triangledown f(x’)^t\epsilon + \frac{1}{2}\epsilon^t\triangledown^2f(x’)\epsilon+o(||\epsilon||^2)$
将$\epsilon =By$代入
$f(x’+By)=f(x’)+(B^t\triangledown f(x))^t y + \frac{1}{2}y^t(B^t\triangledown^2f(x’)B)y+o(||y||^2)$
设$f(x’+By)$ 写成一个关于$y$的函数 $g(y)$
则：$g(y)=g(0)+(B^t\triangledown f(x))^t y + \frac{1}{2}y^t(B^t\triangledown^2f(x’)B)y+o(||y||^2)$
那么：$\triangledown g(0)=B^t \triangledown f(x’)\\ \triangledown^2g(0)=B^t\triangledown^2f(x’)B$
$g(y)=f(x’+By)$，如果$x’$是$f$的局部极小，那么等价于$0$是$g$的局部极小，而$g$的一阶微分和二阶微分都已经求出来了，那么其解也就确定了
$\begin{equation} \left\{ \begin{array}{lr} minimize_{x\in D}\ f(x) \\ sub\ to\ Ax = b \end{array} \right. \end{equation}$
- $x’$是局部极小$\Longrightarrow$ $\triangledown g(0)=0， \triangledown^2g(0) \ge 0$
- 如果$B^t \triangledown f(x’) = 0,B^t\triangledown^2f(x’)B > 0 \Longrightarrow x’$是局部极小
拉格朗日乘子法
$N(A)=\{x:Ax=0\} $ 零空间
$ R(A)=\{Ax: x\in \mathbb{R}^n\}$ 矩阵$A$的像空间
$(N(A))^{\bot}=R(A^t)$ 零空间的正交补时$A^t$的像空间
正交补的定义：$V^{\bot}=\{y\in\mathbb{R}^n : y^tx = 0, \forall x \in V\}$
因为$B^t=\begin{equation} \left( \begin{array}{lr} \alpha^t_1 \\ \vdots \\ \alpha^t_{n-p} \end{array} \right) \end{equation}$
所以$B^t\triangledown f(x’)=0$ $\Longleftrightarrow \alpha_i^t\triangledown f(x’)=0,\forall i\in \{1,\cdots,n-p\}\\ \Longleftrightarrow \triangledown f(x’) \in N(A)^{\bot} \\ \Longleftrightarrow \triangledown f(x’) \in R(A^t) , R(A^t)=\{A^ty: y\in \mathbb{R}^p \} \\ \Longleftrightarrow \exists \mu \in \mathbb{R}^p st.\ \triangledown f(x’)+A^t\mu=0 $
关于$B^t\triangledown f(x’)=0$ 经过一些看不懂的变换可以等价于$\exists \mu \in \mathbb{R}^p$,使得$\triangledown f(x’)+A^t\mu=0$
而在拉格朗日乘子法中针对一开始的优化问题，可以写成$L(x,\mu) = f(x)+\mu^t(Ax-b)$
而$L(x,\mu)$对$x$求导就可得 $\triangledown f(x’) + A^t\mu$
拉格朗日乘子
对于$\begin{equation} \left\{ \begin{array}{lr} minimize_{x\in D}\ f(x) \\ sub\ to\ Ax = b \end{array} \right. \end{equation}$
$x’$局部极小$\Longrightarrow\partial_x L(x’,\mu)=0$，其中$L(x,\mu)=f(x)+\mu^t(Ax-b)$
例子 $\begin{equation} \left\{ \begin{array}{lr} minimize\ \sum\limits_{i=1}^nx_i\log x_i \\ sub\ to\ \sum\limits_{i=1}^nx_i=1 \end{array} \right. \end{equation}$
$L(x,\mu)=\sum\limits_{i=1}^nx_i\log x_i + \mu(\sum\limits_{i=1}^nx_i-1)$
$x$局部最小$\Longrightarrow \partial_xL=0,\Longrightarrow \forall i,\partial_{xi}L=0 \\ \Longrightarrow 1+ \log x_i + \mu = 0, \forall i\\ \Longrightarrow \log x_i = -(1+\mu) \Longrightarrow x_i = e^{-(1+\mu)}, \forall i \\ \Longrightarrow x_1 = x_2=…=x_n=\frac{1}{n}$
考虑$B^t\triangledown^2f(x)B$,其中$\partial_{x,i}f = 1+\log x_i$，那么$\triangledown ^2f(x)=\begin{equation} \left( \begin{array}{lr} \frac{1}{x_1} && && \\ && \frac{1}{x_2} \\ && && \ddots && \\ && && && \frac{1}{x_n} \end{array} \right) \end{equation} > 0$
$\triangledown ^2f(x)$是正定矩阵，而$B$又是满秩的所以$B^t\triangledown^2f(x)B$是正定矩阵
所以$x=(\frac{1}{n},\cdots,\frac{1}{n})^t$是局部极小
非线性约束
$\begin{equation} \left\{ \begin{array}{lr} minimize\ f(x) \\ sub\ to\ h_i(x)=0 \end{array} \right. \end{equation}$
解局部参数化
$g:(-1,1)\to \mathbb{R}^n,g(0)=x^{*}$
$R(g)\subset D$，$D$是$f(x)$的定义域
同时符合$h_i(g)=0$
$x’$是局部极小$\Longrightarrow 0$是$f \circ g$的局部极小 $\Longrightarrow (f \circ g)’(0)= 0, f(f \circ g)’’(0)\ge 0$
$h_i \circ g=0 \Longrightarrow (h_i \circ g)’(0) = 0, (h_i \circ g)’’(0) = 0$
根据上面的4个导数和$g$的任意性可以得到解$x’$的必要条件
