如何构造新函数

当原本的已知条件看不出思路, 就要尝试对于原本的式子变形, 找思路构造新函数

或者, 如果已经有了基本的一些定理, 可以尝试创造些新函数, 看看有没有更好的性质可以玩, 说不定能发现一些不显然的东西

1.

Equations

已知

\[ 0 \leq f(y) - f(x) - \langle \nabla f(x), y - x \rangle \leq \frac{L}{2} \|x - y\|^2, \tag{15} \]

求证

\[ f(x) + \langle \nabla f(x), y - x \rangle + \frac{1}{2L} \|\nabla f(x) - \nabla f(y)\|^2 \leq f(y), \tag{16} \]

Proof

注意 \(f(y) - f(x) - \langle \nabla f(x), y - x \rangle\) 可以看成 \(f(y)-\langle \nabla f(x), y\rangle-(f(x)-\langle \nabla f(x), x \rangle)\)

构造 \(\phi(y) = f(y) - \langle \nabla f(x), y \rangle\in \mathcal{F}_L^{1,1}(\mathbb{R}^n)\), 极值点 \(y^*=x\)

可以得到 \(\nabla \phi(y)=\nabla f(y)-\nabla f(x),\nabla \phi(x)=0\)

即证

\[\phi(y)-\phi(x)\geq \frac 1{2L}||\nabla \phi(y)||^2\]

我们利用 \(\phi(x)\leq \phi(t)\) 中 \(t\) 的任意性搞事

由于

\[ \boxed{\phi(x)} \underbrace{\leq}_{x} \phi\left(t\right) \underbrace{\leq}_{(15)} \phi(y) + \langle \nabla \phi(y), t - y \rangle + \frac{L}{2} \|t-y\|^2 \]

有 \(\phi(x),\phi(y)\), 我们希望凑出 \(\|\nabla \phi(y)\|^2\)

看右边第二项, 如果 \(t-y=\nabla \phi(y)\) 就有 \(\|\nabla \phi(y)\|^2\) 了

具体地, 上式可以写成:

\[ \boxed{\phi(x)} = \min_t\phi\left(t\right) \underbrace{\leq}_{(15)} \min_t\Big( \phi(y) + \langle \nabla \phi(y), t - y \rangle + \frac{L}{2} \|t-y\|^2\Big ) \]

右边对 \(t\) 求导:

\[\text{RHS}=\nabla \phi(y) +L||t-y||=0\]

则取 \(t=y-\frac 1L \nabla \phi(y)\) 时有最小

则

\[ \boxed{\phi(x)} \underbrace{\leq}_{x} \phi\left(y - \frac{1}{L} \nabla \phi(y)\right) \underbrace{\leq}_{(15)} \phi(y) + \langle \nabla \phi(y), y - \frac{1}{L} \nabla \phi(y) - y \rangle + \frac{1}{2L} \|\nabla \phi(y)\|^2=\boxed{\phi(y) - \frac{1}{2L} \|\nabla \phi(y)\|^2}. \]

原式得证

2.

\(f\in \mathcal S^{\infty,1}_{\mu,L}(\mathbb R^n)\), 有

\[\mu I_n\preceq \nabla^2 f(x)\preceq LI_n\]

有这个和条件数 \(Q_f=L/\mu\), 我们想研究一下 \(L/\mu\) 和 \(L-\mu\) 的函数的一些性质

看到这个就想构造一个 \(\phi(x)\) 使得 \(0\preceq \nabla^2 \phi(x)\preceq (L-\mu)I_n\) (这个式子凸函数也有, 所以我们希望 \(\phi(x)\) 也可以是凸函数, 与这个式子对齐)

上面 \(\nabla^2 \phi(x)=\nabla^2 f(x)-\mu I_n\)

一个自然的想法是 \(\phi(x)=f(x)-\frac 12 \mu||x||^2\)

我们来研究这个函数的性质

具体地, 我们检查其凸性:

\[ \begin{aligned} &\phi(x) - \phi(z) - \langle \nabla \phi(z), x - z \rangle \\ &= f(x) - \frac{1}{2}\mu \|x\|^2 - \left(f(z) - \frac{1}{2}\mu \|z\|^2\right) - \langle \nabla f(z) - \mu z, x - z \rangle \\ &= \underbrace{f(x) - f(z) - \langle \nabla f(z), x - z \rangle}_{\leq \frac{L}{2} \|x - z\|^2} - \frac{\mu}{2} \underbrace{\left\{ \|x\|^2 - \|z\|^2 + 2\langle z, z - x \rangle \right\}}_{= \|x - z\|^2} \\ &\leq \frac{L}{2} \|x - z\|^2 - \frac{\mu}{2} \|x - z\|^2 = \frac{L - \mu}{2} \|x - z\|^2. \end{aligned} \]

即 \(\phi \in \mathcal{F}_{L - \mu}^{1,1}(\mathbb{R}^n)\)

后面可以看到, 用这个函数可以证明一些复杂的, 不易证的定理

Theorem

If \(f \in \mathcal{S}_{\mu,L}^{1,1}(\mathbb{R}^n)\), then for any \(x, y \in \mathbb{R}^n\) we have

\[ \begin{aligned} \langle \nabla f(x) - \nabla f(y), x - y \rangle &\geq \frac{\mu L}{\mu + L} \|x - y\|^2 \\ &\quad + \frac{1}{\mu + L} \|\nabla f(x) - \nabla f(y)\|^2. \tag{29} \end{aligned} \]

Proof.

定义 \(\phi(x) = f(x) - \frac{1}{2}\mu \|x\|^2\), 有 $$ \nabla \phi(x) = \nabla f(x) - \mu x. $$

已知

\[ \langle \nabla f(x) - \nabla f(y), x - y \rangle \geq \frac{1}{L} \|\nabla f(x) - \nabla f(y)\|^2. \tag{17} \]

If \(\mu=L\), add \((26)\) and \((17)\) gets \((29)\)

If \(\mu < L\), then by (17), we have

\[ \langle \nabla \phi(x) - \nabla \phi(y), x - y \rangle \geq \frac{1}{L - \mu} \|\nabla \phi(x) - \nabla \phi(y)\|^2. \tag{30} \]

and that is exactly (29).