函数沿着梯度方向下降的定量问题

问题0：CMC非数A

非负函数$f\in C^1(\mathbb{R}\to \mathbb{R})$并且存在正实数$M$使得$|f^{\prime }(x)-f^{\prime }(y)|\le M|x-y|,\forall x,y\in \mathbb{R}$证明$(f^{\prime }(x){)}^2\le 2Mf(x),\forall x\in \mathbb{R}$

1. 问题来源与推广

1.1 问题0的证明

引理1.1.1:Descent lemma,一维情况

设开区间$I\subseteq \mathbb{R}$，函数$f:I\to \mathbb{R}$可微，并且导数满足Lipschitz条件$|f^{\prime }(x)-f^{\prime }(y)|\le M|x-y|,\forall x,y\in I$那么对任意$x,y\in I$都有$f(y)=f(x)+f^{\prime }(x)(y-x)+R(x,y),|R(x,y)|\le \frac{M}{2}(x-y{)}^2$

• 这个结果也可以写成

以及

• 根据一个朴素的想法：“如果x处函数导数为负，那么x的某个右邻域上函数值更小，如果x处函数导数非负，那么x的某个左邻域上的函数值更小。”这句话抽象一点来看就是，取一个合适的正实数$\alpha$就做到$f(x-\alpha f^{\prime }(x))\le f(x)$接下来又会想$-\alpha f^{\prime }(x)$这种小位移能保证让函数至少减小多少？我们可以带入$(1)$当中尝试得到一个定量估计$f(x-\alpha f^{\prime }(x))\le f(x)-\left(\alpha -\frac{M}{2}{\alpha }^2\right)f^{\prime }(x{)}^2$也就是说只要$0<\alpha \le \frac{2}{M}$那么这种位移就一定可以保证下降。那么进一步，一个自然的问题是：移动多少，保证的下降最多？很简单，优化关于$\alpha$的二次函数告诉我们$\alpha =\frac{1}{M}$，这能达到最优。于是

• 当然同样的情况我们也可以思考，关于位移-上升的估计：$f\left(x+\frac{1}{M}{f}^{\prime }(x)\right)\ge f(x)+\frac{1}{2M}{f}^{\prime }(x{)}^2$ 于是在此基础上只要添加一个非负性，正如“问题0”当中给出的条件一样，然后结合$(3)$便得到了$f(x)-\frac{1}{2M}{f}^{\prime }(x{)}^2\ge 0⟹f^{\prime }(x{)}^2\le 2Mf(x)$

我们还可以把“问题0”的非负条件说的更为精确一些，在$(3)$当中利用$f\left(x-\frac{1}{M}{f}^{\prime }(x)\right)\ge \inf f$从而得到结论：

命题1.1.2

$f\in C^1(\mathbb{R}\to \mathbb{R})$，函数存在有限的下确界$\inf f$并且存在正实数$M$使得$|f^{\prime }(x)-f^{\prime }(y)|\le M|x-y|,\forall x,y\in \mathbb{R}$证明$(f^{\prime }(x){)}^2\le 2M(f(x)-\inf f),\forall x\in \mathbb{R}$

1.2 高维推广

问题1.2.1

非负函数$f\in C^1({\mathbb{R}}^n\to \mathbb{R})$并且存在正实数$M$使得$||\nabla f(x)-\nabla f(y)||\le M||x-y||,\forall x,y\in {\mathbb{R}}^n$证明$||\nabla f(x)|{|}^2\le 2Mf(x),\forall x\in {\mathbb{R}}^n$

引理1.2.2:Descent lemma,一般情形

设凸开集$D\subseteq {\mathbb{R}}^n$上考虑函数$f:D\to \mathbb{R}$可微，并且函数梯度满足Lipschitz条件$||\nabla f(x)-\nabla f(y)||\le M||x-y||,\forall x,y\in D$那么对任意$x,y\in D$都有$f(y)=f(x)+⟨\nabla f(x),y-x⟩+R(x,y),|R(x,y)|\le \frac{M}{2}||x-y|{|}^2$

类似地，根据这个结果我们可以得到

然后接下来的问题是：从点$x$出发，向哪个方向做任意小的位移一定能使得函数下降？哪个方向下降最快？

答案是，朝着与函数梯度$\nabla f$相反的方向，下降最快。因为$D_{u}f(x):={\lim }_{t\to 0}\frac{f(x+tu)-f(x)}{t}=⟨\nabla f(x),u⟩$根据柯西不等式的取等条件，使得这个式子最小的单位向量$u=-\frac{\nabla f(x)}{||\nabla f(x)||}$。

那么加下来是定量问题，位移$-\alpha \nabla f(x)$至少能保证下降多少？我们可以把$x-\alpha \nabla f(x)$带入到$(4)$当中得到$f(x-\alpha \nabla f(x))\le f(x)-\left(\alpha -\frac{M}{2}{\alpha }^2\right)||\nabla f(x)|{|}^2$令$\alpha =\frac{1}{M}$能优化此式的上界，得到

如果此时我们加入”问题1.2.1”当中的函数非负的条件便能得到$||\nabla f(x)|{|}^2\le 2Mf(x)$

我们还可以把“问题1.2.1”的非负条件说的更为精确一些，在$(6)$当中利用$f\left(x-\frac{1}{M}\nabla f(x)\right)\ge \inf f$从而得到

命题1.2.3

$f\in C^1({\mathbb{R}}^n\to \mathbb{R})$并且函数存在有限下确界$\inf f$并且存在正实数$M$使得$||\nabla f(x)-\nabla f(y)||\le M||x-y||,\forall x,y\in {\mathbb{R}}^n$证明$||\nabla f(x)|{|}^2\le 2M(f(x)-\inf f),\forall x\in {\mathbb{R}}^n$

2. descent lemma的证明

令$v=y-x$定义$g(t):=f(x+tv)$,那么$g^{\prime }(t)=⟨\nabla f(x+tv),v⟩$ 所以证明“引理1.2.2”的descent lemma的本质就是估计余项

此处我们稍微遇到一点麻烦。如果我们有${\nabla }^{2}f$的信息，那么一切都会很简单。因为$\begin{array}{rl}|g^{\prime \prime }(t)|& =\underset{r\to 0}{\lim }\frac{|g^{\prime }(t+r)-g^{\prime }(t)|}{r}\\ & =\underset{r\to 0}{\lim }⟨\frac{\nabla f(x+(t+r)v)-\nabla f(x+tv)}{r},v⟩\\ & \le M||v|{|}^2\end{array}$所以如果${\nabla }^{2}f$处处存在，那么根据一元情况的Taylor展开的Lagrange余项$(7)$可以写成,存在一个$\theta \in (0,1)$使得$g(1)=g(0)+g^{\prime }(0)+\frac{1}{2}{g}^{\prime \prime }(\theta )$然后根据关于$g^{\prime \prime }$的估计，我们就能得到引理的结论。但问题出在$g^{\prime \prime }(t)$未必处处存在，于是上述推导存在漏洞。

不过实际上$g^{\prime \prime }(t)$处处存在在此引理的证明中并不是必须的，我们有多种办法可以绕过它。

2.1 利用积分放缩绕过

$\begin{array}{rl}|R(x,y)|& =|g(1)-g(0)-g^{\prime }(0)|\\ & \le {\int }_0^1|g^{\prime }(t)-g^{\prime }(0)|dt\\ & \le {\int }_0^{1}M||v|{|}^{2}tdt\\ & =\frac{M}{2}||v|{|}^2=\frac{M}{2}||x-y|{|}^2\end{array}$

2.2 利用光滑逼近

想法2.2.1

根据前面的分析，在“引理1.2.2:Descent lemma”的基本假设下，如果函数还是$C^2$的，那么Descent lemma的结论直接成立。那么只要我们可以找到一种能能光滑逼近引理假设中的函数，并且保持梯度的Lipschitz条件不变，并且能保证极限函数可以继承Descent lemma结论中的性质，$f(y)=f(x)+⟨\nabla f(x),y-x⟩+R(x,y),|R(x,y)|\le \frac{M}{2}||x-y|{|}^2$那么整个证明就可以完成。

但是如果我们参考1.1 让函数与Mollifier做卷积，我们可以取$C_c^{\infty }({\mathbb{R}}^n\to \mathbb{R})$中的一族$\{{\psi }_{\lambda }{\}}_{\lambda >0}$Mollifier，然后$f$是满足“引理1.2.2:Descent lemma”中假设的函数，令$f_{\lambda }(w):={\psi }_{\lambda }\ast f(w)=\int f(w-z){\psi }_{\lambda }(z)dz$这会出现一个问题：$f$只是定义在凸开集$D$上而不是${\mathbb{R}}^n$上。

为了处理这个问题，我们可以针对任意$x,y\in D$的固定两点来考虑基于Mollifier的逼近的命题。反正只要对任意固定两点结论成立，那么命题就可以被证明。考虑闭线段$K:=[x,y]:=\{x+t(y-x):t\in [0,1]\}$由于$D$的凸性，因此$K\subset D$。由于$K$是紧集，设$\delta :=\text{dist}(K,\partial D)>0$要使得整个证明成立，我们需要做到任意$w\in [x,y]$卷积$f_{\lambda }(w)$都有意义。因为别忘了，我们会用到$f_{\lambda }$是$C^2$的函数，然后运行一遍第二节一开头的证明，所以必须整条闭线段上的点$f_{\lambda }$都有定义，并且光滑。

要做到这一点，我们需要保证$\forall w\in K$都有$\forall z\in \text{supp }{\psi }_{\lambda }\subset B(0,1/\lambda )⟹w-z\in D$这等价于$\text{dist}(w,\partial D)>\frac{1}{\lambda }$为了后需证明，我们需要保证$K\subset D_{\lambda }:=\{w\in D:\text{dist}(w,\partial D)>\frac{1}{\lambda }\}$那么我们可以让$\lambda$足够大以至于$\frac{1}{\lambda }<\delta$如此一来定义问题就可以解决。

• 集合$\{w-z:z\in B(0,1/\lambda )\}=B(w,1/\lambda )$。这是因为假设$u=w-z$那么$||u-w||=||z||<\frac{1}{\lambda }$然后既然任意$w$都需要满足$B(w,1/\lambda )\subset D$自然需要保证$\text{dist}(w,\partial D)>\frac{1}{\lambda }$
• 关于最后的几何问题：首先$\delta :={\inf }_{w\in K}\text{dist}(w,\partial D)$所以必须要保证$\delta >\frac{1}{\lambda }$才可以保证$K\subset D_{\lambda }$。然后由于$D_{\lambda }$本身是一个开集，于是$f_{\lambda }(w)$在这样一个包含$D_{\lambda }$的开集上成立，完全可以满足后续在闭线段$K$上考虑问题，以及在$K$上的开邻域上定义微分的要求。
• 此处相当于是选定$x,y\in D$以后，由于$K=[x,y]$所以确定了$\lambda$的范围，之后再定义$f_{\lambda }$。

对任意固定的$x,y\in D$根据上面的讨论，只对足够大的满足$\frac{1}{\lambda }<\delta$的正实数$\lambda$定义$f_{\lambda }(w):={\psi }_{\lambda }\ast f(w),w\in D_{\lambda }$

那么根据^56234c中的说明$f_{\lambda }$满足：

1. 无限光滑性：$f_{\lambda }\in C^{\infty }(D_{\lambda }\to \mathbb{R})$
2. 梯度保持Lipschiz性：首先根据卷积的基本运算性质^787915${\partial }_{x_i}{f}_{\lambda }(w)={\partial }_{x_i}({\psi }_{\lambda }\ast f)(w)={\psi }_{\lambda }\ast {\partial }_{x_i}f(w)$于是$\begin{array}{rl}\nabla f_{\lambda }(w)& =({\partial }_{x_1}{f}_{\lambda }(w),\cdots ,{\partial }_{x_n}{f}_{\lambda }(w))\\ & =({\psi }_{\lambda }\ast {\partial }_{x_1}f(w),\cdots ,{\psi }_{\lambda }\ast {\partial }_{x_n}f(w))\\ & ={\int }_{{\mathbb{R}}^n}{\psi }_{\lambda }(z)\nabla f(w-z)dz\end{array}$在此基础上对任意的$w_1,w_2\in D_{\lambda }$都有$\begin{array}{rl}||\nabla f_{\lambda }(w_1)-\nabla f_{\lambda }(w_2)||& =\Vert {\int }_{{\mathbb{R}}^n}{\psi }_{\lambda }(z)(\nabla f(w_1-z)-\nabla f(w_2-z))dz\Vert \\ & \le {\int }_{{\mathbb{R}}^n}{\psi }_{\lambda }(z)\Vert \nabla f(w_1-z)-\nabla f(w_2-z)\Vert dz\\ & \le M||w_1-w_2||{\int }_{{\mathbb{R}}^n}{\psi }_{\lambda }(z)dz\\ & =M||w_1-w_2||\end{array}$所以$\nabla f_{\lambda }$同样保持Lipschitz性，并且Lipschitz系数相同。于是根据第二节一开始的分析，我们可以在$D_{\lambda }$上验证$f_{\lambda }(w)$可以成立Descent lemma的结论。因为在闭线段$K$上$f_{\lambda }$光滑，并且梯度$\nabla f_{\lambda }$具有Lipschitz性，并且Lipschitz系数为$M$。
3. 点态收敛：参考^56234c由于$f$的连续性，所以$f_{\lambda }(w)\to f(w)$处处成立。此外由于$f\in C^1$，自然${\partial }_{x_i}f(w)$都是连续的，从而${\psi }_{\lambda }\ast {\partial }_{x_i}f(w)\to {\partial }_{x_i}f(w)$处处成立，那么自然有$\nabla f_{\lambda }(w)\to \nabla f(w)$处处成立。

于是根据上面所说，首先对于函数$f_{\lambda }$满足$\forall x,y$都有$f_{\lambda }(y)=f_{\lambda }(x)+⟨\nabla f_{\lambda }(x),y-x⟩+R_{\lambda }(x,y),|R_{\lambda }(x,y)|\le \frac{M}{2}||x-y|{|}^2$那么由于$|R(x,y)|=|{\lim }_{\lambda \to \infty }{R}_{\lambda }(x,y)|={\lim }_{\lambda \to \infty }|R_{\lambda }(x,y)|\le \frac{M}{2}||x-y|{|}^2$因此对于任意固定的$x,y\in D$，$f$也成立“引理1.2.2:Descent lemma”的结论。于是命题得证。