## Convex function

### 定义

$f$ is convex if

1. dom $f$ is convex and
2. (Jensen's inequality) $\alpha f(x) + \beta f(y) \geq f(\alpha x + \beta y)$ for all $x, y$, for all $\alpha, \beta \geq 0$ s.t. $\alpha + \beta = 1$.

### 一阶等价条件

For differentiable $f$, $f$ is convex $\iff$

1. dom $f$ is convex and
2. $f(y) \geq f(x) + \nabla f(x)^T (y-x)$ for all $x, y$.

### 二阶等价条件

For twice differentiable $f$, $f$ is convex $\iff$

1. dom $f$ is convex and
2. $\nabla^2 f(x) \succeq 0$ for all $x$.

### 单调梯度等价条件

For differentiable $f$, $f$ is convex $\iff$

1. dom $f$ is convex and
2. $\big (\nabla f(x) - \nabla f(y)\big )^T (x-y) \geq 0$.

$\implies$:

$f(y) \geq f(x) + \nabla f(x)^T (y-x)$

$f(x) \geq f(y) + \nabla f(y)^T (x-y)$

$\impliedby$:

$f(y) \geq f(x) + \nabla f(x)^T (y-x)$ for all $x, y$.

## Lipschitz smooth

### 定义

$f$ is L-smooth if $|| \nabla f(x) -\nabla f(y) || _2 \leq L || x-y || _2$ for all $x, y$.

L-smooth 表明一个函数的梯度的变化不会太突兀，或者说这个函数比较平滑。

### 等价条件

1. $f$ is convex and L-smooth.
2. $\big(\nabla f(x) -\nabla f(y)\big)^T(x-y) \leq L || x-y || _2^2$ for all $x, y$.
3. $g(x)=\frac{L}{2} x^T x - f(x)$ is convex.
4. (quadratic upper bound) $0 \leq f(y) - f(x) - \nabla f(x)^T (y-x) \leq \frac{L}{2} || x-y || _2^2$
5. $f(y) \geq f(x) + \nabla f(x)^T (y-x) + \frac{1}{2L} || \nabla f(x) - \nabla f(y) || _2^2$
6. (co-coercivity) $\big (\nabla f(x) - \nabla f(y)\big )^T (x-y) \geq \frac{1}{L} || \nabla f(x) - \nabla f(y) || _2^2$.

$1 \implies 2$:

\begin{aligned} || \nabla f(x) -\nabla f(y) || _2 &\leq L || x-y || _2\\ ||\nabla f(x) -\nabla f(y) || _2 \cdot || x-y || _2 &\leq L || x-y || _2^2 \\ \text{(Cauchy-Schwartz)} \quad \big(\nabla f(x) -\nabla f(y)\big)^T(x-y) &\leq L || x-y || _2^2 \end{aligned}

$2 \iff 3$:

$\big(\nabla f(x) -\nabla f(y)\big)^T(x-y) \leq L || x-y || _2^2 = L (x-y)^T (x-y)$

$\big(Lx-\nabla f(x) - Ly+\nabla f(y) \big)^T(x-y) \geq 0$

$\big (\nabla g(x) - \nabla g(y)\big )^T (x-y) \geq 0$,

$3 \iff 4$: 利用 $g$ 为 convex 的一阶条件。

$4 \implies 5$:
$z=y+\frac{1}{L}(\nabla f(x)-\nabla f(y))$.

\begin{aligned} f(y)-f(x) &= f(y) - f(z) + f(z) - f(x) \\ \href{./# 等价条件}{\text{(quadratic upper bound)}} \quad &\geq -\nabla f(y)^T(z-y) - \frac{L}{2} ||y-z||_2^2 + \nabla f(x)^T (z-x) \\ \text{(substitute z)} \quad &\geq -\frac{1}{L}\nabla f(y)^T (\nabla f(x)-\nabla f(y)) \\ & \qquad - \frac{1}{2L} ||\nabla f(x)-\nabla f(y)||_2^2 + \nabla f(x)^T (y-x) \\ & \qquad + \frac{1}{L}\nabla f(x)^T (\nabla f(x)-\nabla f(y)) \\ &= \nabla f(x)^T (y-x) + \frac{1}{2L} ||\nabla f(x)-\nabla f(y)||_2^2 \end{aligned}

$5 \implies 6$:

$f(y) \geq f(x) + \nabla f(x)^T (y-x) + \frac{1}{2L} || \nabla f(x) - \nabla f(y) || _2^2$

$f(x) \geq f(y) + \nabla f(y)^T (x-y) + \frac{1}{2L} || \nabla f(x) - \nabla f(y) || _2^2$

$6 \implies 1$:

6 的右边 $\geq 0$， 使用单调梯度可得 convex.

L-smooth 函数

## Strongly convex

### 定义

$f$ is $\mu$-strongly convex if $f(x)-\frac{\mu}{2}x^T x$ is convex.

Strong convex 函数

### 等价条件

1. $f​$ is differentiable and $\mu​$-strongly convex.
2. $f$ is differentiable and $f(\alpha x +\beta y) \leq \alpha f(x) + \beta f(y) - \frac{\mu \alpha \beta}{2} ||x-y||_2^2$ for all $x, y$, for all $\alpha, \beta \geq 0$ s.t. $\alpha + \beta = 1$.
3. (quadratic lower bound) $f(y)\geq f(x) + \nabla f(x)^T (y-x) + \frac{\mu}{2} ||y-x||_2^2$.
4. (strong monotonicity or coercivity) $\big (\nabla f(x) - \nabla f(y)\big )^T (x-y) \geq \mu|| x - y || _2^2$.

$1 \iff 2$: 使用 convex 函数定义.
$1 \iff 3$: 使用 convex 函数的一阶条件.
$1 \iff 4$: 使用 convex 函数的单调梯度条件.

## References

1. Lecture notes: Gradient method. EE236C - Optimization Methods for Large-Scale Systems (Spring 2016). Vandenberghe, UCLA.

2. Zhou, X. (2018). On the Fenchel Duality between Strong Convexity and Lipschitz Continuous Gradient. arXiv preprint arXiv:1803.06573.