本文是关于本人研究生期间优化方法课程的学习笔记，仅仅是为了方便自己整理和记忆知识点，不能保证所提到知识点全部正确，并且文章结构可能会比较零碎和杂乱，尽量在一段时间后定期整理笔记。
伪逆：
$$
\begin{equation}
A^+=\left{
\begin{aligned}
AA^+A&=&A \
A^+AA^+&=&A^+ \
(AA^+)^T&=&AA^+ \
(A^+A)^T & = & A^+A \
\end{aligned}
\right.
\end{equation}
$$
奇异值：$A^+A$ 的特征值再取根号
任何物体都可以看作是一个函数，灰度图可看作是从定义域 $\Omega$ 到值域 R 的函数，值域的取值范围是 [0,255]。而RGB图像可以看作是三个函数。
$R^n$ 是 n 维线性空间，$R^+$ 是正整数
线性空间 C ：对 $x_1,x_2\in C,\quad k\in R$ 满足8条性质，则称 C 为想向量空间。
内积 <,> 满足：1. $<y,x>=<x,y>$；2. $k<x,y>=k<x,y>$；3. $<x,y>^2\leq<x,x><y,y>$
距离有多种方式，其中欧式距离可以表示为：$d(x,y)=\sqrt{<x-y,x-y>}$
$L^p$ 范数：$||x||_p=\sqrt[p]{||x_1||^p+||x_2||^p+…+||x_n||^p}$
$||u_p^p||=\int |u(x)|^pdx$
诱导范数：$||A||_1=sup{\frac{||Ax||_1}{||x||_1}}，x\in R^n$
变分法
Banach 空间：完备的线性赋范空间
完备：柯西序列${x_n}$收敛，即对于序列 $x_1,x_2,…,x_n$，对于任意大的数 N，若 $n,m > N$，则 $|x_n-x_m|<\epsilon$
线性：$x_1,x_2\in A\Rightarrow k_1x_1+k_2x_2\in A$
赋范：范数 $||\cdot||$ 满足：
- 正定性：$||x||\geq0$；
- 齐次性：$||kx||=k||x||，当且仅当（iff）x=0时取”=”$;
- 三角不等式：$||x+y||\leq ||x||+||y||$。
当为矩阵范数时，还应该额外满足：$||x\cdot y||\leq||x||\cdot||y||$
Hilbert（希尔伯特）空间：当为内积导出的 Banach 空间时为希尔伯特空间
函数的范数：$||f(x)||_p=(\int |f(x)|^p dx)^{\frac{1}{p}}$
$L^p$ 空间：$L^p(\Omega)={f(x)\quad|\quad||f(x)||_p<+\infty}$，有 $L^1(\Omega)>L^2(\Omega)>L^3(\Omega)>…$
弱导数
导数：$f’(x)=\lim_{x\rightarrow x_0}{\frac{f(x)-f(x_0)}{x-x_0}}$，连续光滑函数一定可导。
积分意义下的弱导数：若函数 u 连续但不光滑，并且对 $\forall \varphi\in C_c^1(\Omega)$ 有 $\int_{\Omega}{u\frac{\partial\varphi}{\partial x_0}dx=-\int_\Omega{v\varphi dx}}$，则称 $v\in L^1(\Omega)$ 是函数 u 沿 $x_i$ 方向的弱导数。
其中 $C_c^1(\Omega)$ 是一阶可导的连续紧致集（紧集）,紧致集是指在边界（端点）上为0
$\int_\Omega u\frac{\partial\varphi}{\partial x_i}dx=-\int_\Omega v\varphi dx$，记 $v=\frac{\partial u}{\partial x_i}$
$\int_\Omega u\nabla\varphi dx=-\int_\Omega v\varphi dx$，记 $v=\nabla u$（多元情况）（$\nabla\varphi\rightarrow\frac{\partial\varphi}{\partial x_1},…,\frac{\partial\varphi}{\partial x_n}$）
$\int_\Omega u\varphi’dx=-\int_\Omega v\varphi dx$，记 $v=u’$，即 v 是 u 的弱导数。
a.e. （almost everywhere）
弱导数如果存在，则唯一。
对于某个点来说，导数存在则弱导数一定存在，并且弱导数等于导数，而弱导数存在导数不一定存在。
例：
$f(x)=|x|,x\in[-1,1]$ 则 $\begin{equation}
f’(x)=\left{
\begin{aligned}
-1 & , & x\in[-1,0] \
1 & , & x\in(0,1]
\end{aligned}
\right.
\end{equation}$ 在不可导点的弱导数一般可以取任意值。
测度意义下的弱导数：当函数是不光滑且不连续时，如
$$
\begin{equation}
f(x)=\left{
\begin{aligned}
0 & , & x\in(-1,0) \
1 & , & x\in(0,1)
\end{aligned}
\right.
\end{equation}
$$
$D_u=\nabla udx+\delta x_0$ 有弱导数的地方取弱导数 $\nabla udx$，反之取 $\delta x_0$（间断点之间的高度）。
向前、向后差分
对偶空间
对偶（dual）空间 x’：X 上有界线性泛函的全体（泛函数是函数的函数，即广义的函数）
Banach 空间：（X $||\cdot||_X$）
线性：$f(\alpha x+\beta y)=\alpha f(x)+\beta f(y)$
若 $L^p(\Omega)={u|\int|u|^pdx<+\infty}$， $L^q(\Omega)={u|\int|u|^q dx<+\infty}$，且 $\frac{1}{p}+\frac{1}{q}=1$，则称 $L^q(\Omega)$是 $L^p(\Omega)$的对偶。
Holder 不等式：$\int_\Omega f(x)g(x)dx\leq(\int_\Omega|f(x)|^p)^{\frac{1}{p}}(\int_\Omega|f(x)|^q)^{\frac{1}{q}}$，$\frac{1}{p}+\frac{1}{q}=1$
$L^1(\Omega)$的对偶是 $L^{\infty}(\Omega)$，$L^2(\Omega)$的对偶是 $l^2(\Omega)$。
(1) 强收敛：$x_n\xrightarrow[X]{} x\Leftrightarrow ||x_n-x||_X\rightarrow 0$
(2) 弱收敛：$x_n\xrightarrow[X]{}x\Leftrightarrow \forall l\in X’$ ，有 $l(x_n)-l(x)\rightarrow0$
强收敛 $\Rightarrow$ 弱收敛，反之不可
能量函数 $E(u)=\int_\Omega|u|^2dx+\int_\Omega|u-f_0|^2dx$，其中 u 是关于x 的函数。（泛函数的值为能量）
$min_u E(u)$ 的存在性：
(1) $E(u)\not\equiv\infty$（不恒等），$u_n\subset X,\lim_{n\rightarrow\infty}E(u_n)=\inf_{u\in X}E(u)$，其中 X 是 Banach 空间，inf 是下界函数。
(2) E(u) 具有强制性，即 $||u||_x\rightarrow \infty\Rightarrow E(u)\rightarrow\infty$
(3) $E(u_0)\leq\lim_{j\rightarrow\infty}E(u_{n_j})=\inf E(u)$
判断一个函数是否为凸函数：$\nabla^2E\geq 0$，若 $\nabla^2E\geq 0$，则Hessian矩阵半正定。
下半连续性 $l.s.c.$：若对 $x_n\xrightarrow[X]{} x_0$ 有 $E(x_0)\leq lim_{n\rightarrow+\infty}E(x_n)$，则称 E 为 $l.s.c.$。
弱下半连续性（$w.l.s.c.$）：若对 $x_n\xrightarrow[X]{} x_0$ 有 $E(x_0)\leq \lim_{n\rightarrow+\infty}E(x_n)$，则称 E 为 $w.l.s.c.$。
如果 E 是凸函数，则 $l.s.c.$ 和 $w.l.s.c.$ 等价。
$\forall \xi>0,\exists x_0$ 开邻域 V，使得 $\forall x\in V$，有 $f(x)>f(x_0)-\xi\Rightarrow f$ 为 $l.s.c.$
最优条件（Optimal condition）
Gateaux derivative：$E:x\rightarrow R$，若 $E’(u,v)=\frac{E(u+tv)-E(u)}{t}$ 存在，则称 $E’(u,v)$ 为 $E(u)$ 在 u 处沿 v 方向的导数。
若 $\exists \tilde u\in X’$，使得（s.t.）$\tilde u(v)=E’(u,v)$ 对任意 v 都成立，则称 E 在 u 处 Gateaux 可导，记为 $E’(u)=\tilde u$ 或 $\frac{\delta E(u)}{\delta u}=\tilde u$
$\tilde u(v)=\int_\Omega\tilde uvdx$是线性的。
$$
E’(u,v)=\lim_{t\rightarrow0}\frac{E(u+tv)-E(u)}{t}
$$
$$
=\lim_{t\rightarrow0}\frac{\int_\Omega|u+tv|^2+|u+tv-f|^2dx-\int_\Omega|u|^2+|u-f|^2dx}{t}
$$
$$
=\lim_{t\rightarrow0}\frac{2\int_\Omega(u+tv)v+(u+tv-f)vdx}{1}
$$
$$
=2\int_\Omega[uv+(u-f)v]dx=2\int_\Omega[u+u-f]vdx
$$
$$
E’(u)=4u-2f
$$
$$
E’(u,v)=\frac{d E(u+tv)}{dt}|_{t=0}
$$
$$
E(u)=\int_\Omega|\nabla u|dx+\frac{\lambda}{2}\int_\Omega|u-f|^2dx
$$
$$
E’(u,v)=\frac{d E(u+tv)}{dt}|_{t=0}
$$
$$
=\frac{\int_\Omega|\nabla (u+tv)|+\frac{\lambda}{2}\int_\Omega|u+tv-f|^2dx}{dt}|_{t=0}
$$
$$
=\int_\Omega<\frac{(\nabla u+t\nabla v)}{|\nabla(u+tv)|’},\nabla v>+\lambda(u+tv-f)vdx|_{t=0}
$$
$$
\int_\Omega<\frac{\nabla u}{|\nabla u|},\nabla v>+\lambda(u-f)vdx=\int_\Omega[\nabla^T(\frac{\nabla u}{|\nabla u|})+\lambda(u-f)]vdx
$$
$<AB,C>=<B,A^TC>$
$<\nabla u,\phi>=<u,-\nabla^T\phi>$，其中 $\nabla^T=-div$ ，即散度。
最优性条件
给定 f(x) 求 f’(x)=0
E(u)， u, v 是关于 x 的函数
- $E(u,v)=E(u+tv)$
- 方向导数 $E’(u,v)=\frac{dE(u+tv)}{dt}|_{t=0}$
- $E’(u,v)=\int_\Omega E’(u)vdx$
求 E’(u)=0
例：
$$
E(u)=\int_\Omega|\nabla u|dx+\int_\Omega(u-f)^2dx
$$
$$
=\int_\Omega{|\nabla u|+(u-f)^2}dx
$$
$$
E(u,v)=E(u+tv)=\int_\Omega{|\nabla(u+tv)|+((u+tv)-f)^2}dx
$$
$$
\frac{dE(u+tv)}{dt}|{t=0}=\frac{\int_\Omega d {|\nabla(u+tv)|+((u+tv)-f)^2}dx}{dt}|{t=0}
$$
求导和积分可以互换
$$
\frac{\int_\Omega{|\nabla(u+tv)|+((u+tv)-f)^2}dx}{dt}|_{t=0}dx
$$
$$
=\int_\Omega<\frac{\nabla u+t\nabla v}{|\nabla u+t\nabla v|},\nabla v>+2v(u+tv-f)|_{t=0}dx
$$
$$
=\int_\Omega<\frac{\nabla u}{|\nabla u|},\nabla v>+2v(u-f)dx
$$
因 $<a,bc>=b^Tac$ ，其中 b 可以是 $\nabla，\nabla^T$ 等，故 $<\frac{\nabla u}{|\nabla u|},\nabla v>=\nabla^T\frac{\nabla u}{|\nabla u|}v$
$$
=\int_\Omega[\nabla^T(\frac{\nabla u}{|\nabla u|})+2(u-f)]vdx
$$
故
$$
E’(u)=\nabla^T(\frac{\nabla u}{|\nabla u|})+2(u-f)=-div(\frac{\nabla u}{|\nabla u|})+2(u-f)
$$
线性算子满足： $\nabla(f+g)=\nabla f+\nabla g$
$\nabla(u+tv)=\nabla u+\nabla(tv)=\nabla u+t\nabla v$
$$
\frac{d|x|}{dx}=\frac{x}{|x|}
$$
$<AB,C>=<B,A^TC>=<C^TAB,I>$
$<\nabla u,v>=<u,\nabla^Tv>$
$\nabla^T=-dw$ ，即梯度等于负的散度
例：
$$
E(u)=\int_\Omega f(x,u,\nabla u)dx
$$
$$
E(u,v)=E(u+tv)=\int_\Omega f[x,u+tv,\nabla(u+tv)]dx
$$
$$
\frac{dE(u+tv)}{dt}|{t=0}=\frac{d\int_\Omega f[x,u+tv,\nabla(u+tv)]dx}{dt}|{t=0}
$$
$$
=\frac{\int_\Omega d f[x,u+tv,\nabla(u+tv)]}{dt}|_{t=0}dx
$$
$$
=\int_{\Omega}(f_1’\cdot0+f_2’\cdot v+<f_3’\cdot\nabla v>)|_{t=0}dx
$$
$$
=\int_\Omega f_2’\cdot v+\nabla^Tf_3’\cdot vdx
$$
$$
E’(u)=f_2’+\nabla^Tf_3’
$$
$|\nabla u|$ 是平方和开根号，$\nabla^2 u$ 是线性的，$\Delta=-\nabla^T\nabla=div(\nabla)$ ，$\Delta$ 表示拉普拉斯
$$
\nabla^2 u=\begin{bmatrix} \nabla_{ww}u& &\nabla_{wh}u \ \nabla_{hw}u& &\nabla_{hh}u\end{bmatrix}
$$
$$
|\nabla^2u|=\sqrt{\nabla_{ww}^2u+\nabla_{wh}^2u+\nabla_{hw}^2u+\nabla_{hh}^2u}
$$
例：
$$
E(u)=\int_\Omega\sqrt{1+|\nabla u|^2}+|\nabla^2u|dx
$$
$$
E(u,v)=E(u+tv)=\int_\Omega\sqrt{1+|\nabla(u+tv)|^2}+|\nabla^2(u+tv)|dx
$$
$$
E’(u,v)=\frac{dE(u,v)}{dt}|{t=0}=\frac{\int_\Omega d\sqrt{1+|\nabla(u+tv)|^2}+|\nabla^2(u+tv)|}{dt}|{t=0}dx
$$
$$
=\int_\Omega\frac{2|\nabla(u+tv)|}{2\sqrt{1+|\nabla(u+tv)|^2}}\cdot<\frac{\nabla(u+tv)}{|\nabla(u+tv)|},\nabla v>+<\frac{\nabla^2(u+tv)}{|\nabla^2(u+tv)|},\nabla^2v>|_{t=0}dx
$$
$$
=\int_\Omega[\frac{\nabla^T\nabla u}{\sqrt{1+|\nabla u|^2}}+\frac{(\nabla^2)^T\nabla^2 u}{|\nabla^2 u|}]\cdot vdx
$$
$$
=\int_\Omega[\frac{\Delta u}{\sqrt{1+|\nabla u|^2}}+\frac{(\nabla^2)^T\nabla^2 u}{|\nabla^2 u|}]\cdot vdx
$$
$$
E’(u)=-\frac{\Delta u}{\sqrt{1+|\nabla u|^2}}+(\nabla^2)^T\frac{\nabla^2 u}{|\nabla^2 u|}
$$
$\Delta=diw(\nabla)$ 貌似矛盾！！！！！！！！！！！！！！！！！！！！！！
例：
$$
E(u)=\int_\Omega|\nabla u|^2dx
$$
$$
E(u,v)=E(u+tv)=\int_\Omega|\nabla(u+tv)|^2dx
$$
$$
\frac{dE(u+tv)}{dt}|{t=0}=\frac{\int_\Omega d|\nabla(u+tv)|^2}{dt}|{t=0}dx
$$
$$
=\int_\Omega2<\nabla(u+tv),\nabla v>|_{t=0}dx
$$
$$
=\int_\Omega2<\nabla(u),\nabla v>dx
$$
$$
=\int_\Omega2\nabla^T\nabla u\cdot vdx
$$
$$
E’(u)=2\nabla^T\nabla u=-2div\nabla u=-2\Delta u
$$
例：
$$
E(u)=\int_\Omega|\nabla^2u|+\frac{\lambda}{2}(u-f)^2dx
$$
$$
E(u,v)=E(u+tv)=\int_\Omega|\nabla^2(u+tv)|+\frac{\lambda}{2}(u+tv-f)^2dx
$$
$$
\frac{dE(u+tv)}{dt}|{t=0}=\frac{\int_\Omega d|\nabla^2(u+tv)|+\frac{\lambda}{2}(u+tv-f)^2}{dt}|{t=0}dx
$$
$$
=\int_\Omega<\frac{\nabla^2(u+tv)}{|\nabla^2(u+tv)|},\nabla^2v>+\lambda v(u+tv-f)|_{t=0}dx
$$
$$
=\int_\Omega<\frac{\nabla^2u}{|\nabla^2u|},\nabla^2v>+\lambda v(u-f)|_{t=0}dx
$$
$$
=\int_\Omega[(\nabla^2)^T\frac{\nabla^2u}{|\nabla^2u|}+\lambda(u-f)]vdx
$$
$$
E’(u)=(\nabla^2)^T\frac{\nabla^2u}{|\nabla^2u|}+\lambda(u-f)
$$
$\nabla^T\nabla=-\Delta$
若 $E(u)=\int|u-f|^2dx=||u-f||_2^2$
去积分求导： $2(u-f)=2(u-f)$
若去掉平分，求导 $\frac{u-f}{|u-f|}$
若 $E(u)=\int|\nabla u-f|dx=||\nabla u-f||_2$
不看积分求导（对u求导）：$\nabla^T\frac{\nabla u-f}{|\nabla u-f|}$
以上结论不可直接用！！！
$\nabla u$ 可对 u 求导，求导结果为 $\nabla^T$，$\nabla^T$ 写到前面
无 $\nabla$ 正常求，有 $\nabla$ 则按 $<AB,C>=<C^TAB,I>=<B,A^TA>=<B^TA^T,C^T>=<A^T,BC^T>$ 求
$$
\nabla^T(\frac{\nabla u}{|\nabla u|})\neq-\frac{\Delta u}{|\nabla u|}
$$
$|\nabla u|$ 不是常数
BV 空间
$$
V_u(x_0,…,x_n)=\sum_{i=1}^n|u(x_i)-u(x_{i-1})|
$$
称 u 为关于 $x_0,…,x_n$ 的变差（variation）
若 $\exists M$ s.t. 关于 [a,b] 分割的上界 $\sup V_u(x_0,…,x_n)<M$，则称 u 具有有界变差（Bounded Variation，BV），称关于 [a,b] 分割的 $\sup V_u(x_0,…,x_n)$ 为 u 的全变差（Total variation, TV）（所有分段单调函数端点的高度差）。函数不一定有 TV
有界变差函数的集合为 BV 空间
$$
\int_\Omega|Du|=\sup{\int_\Omega u\cdot div\varphi dx,\varphi\in C_0^1(\Omega)^n,||\varphi||{\infty}\leq1}
$$
其中 $\varphi\in C_0^1(\Omega)^n$ 的含义是 $\varphi={\varphi_1,…,\varphi_n}$，$div\varphi=\sum{i=1}\frac{\partial\varphi_i}{\partial X_i}$，$||\varphi||\infty=\sup_X\sqrt{\sum{i=1}\varphi^2_i(x)}$
$$
\int_\Omega u\cdot div\varphi dx=<u,div\varphi>=-<u,\nabla^T\varphi>=-<\nabla u,\varphi>
$$
$<u,v>=\int_\Omega uvdx$，$\nabla^T=-di$v
$<\alpha,x>$ 且 $||x||_\infty\leq1$，则 $<\alpha,x>$ 最大值为 $|\alpha|$，最小值为 $-|\alpha|$，$-<\nabla u,\varphi>$ 的最大值为 $|\nabla u|$，前提是 $\nabla u\quad\exists$
若 $\int_\Omega|\nabla u|<\infty$，则 u 具有 BV，$\int_\Omega|\nabla u|$ 为 TV
$BV={u\in L’(\Omega)|\int_\Omega|Du|<\infty}$，$u\in L’,\nabla u\quad\exists$ 且 $\int |Du|dx<\infty$，则属于 W’ 空间
- 本文作者： 俎志昂
- 本文链接： zuzhiang.cn/2019/09/24/optimization/
- 版权声明： 本博客所有文章除特别声明外，均采用 Apache License 2.0 许可协议。转载请注明出处！