Si $(\nabla f(x)-\nabla f(y))\cdot(x-y)\geq m(x-y)\cdot(x-y)$, ¿por qué es $f$ convexo?

Question

Yo estaba leyendo en la wikipedia que un fuertemente convexa función también es estrictamente convexa.

Yo digo que una función $f\colon\mathbb{R}^n\to\mathbb{R}$ es convexa si $$f(\lambda x+(1-\lambda)y)\leq\lambda f(x)+(1-\lambda)f(y)$$ para todos los $x,y\in\mathbb{R}^n$, e $\lambda\in[0,1]$. Si $f$ es continuamente diferenciable, y fuertemente convexa, por lo que no existe $m>0$ tal que $$(\nabla f(x)-\nabla f(y))\cdot(x-y)\geq m(x-y)\cdot(x-y)$$ para todos los $x,y\in\mathbb{R}^n$, ¿cómo se puede recuperar ese $f$ es convexo?

Escrito $x=(x_1,\dots,x_n)$$y=(y_1,\dots,y_n)$, sólo podía interpretar la desigualdad anterior como $$\sum_{i=1}^n\frac{\partial f}{\partial e_i}(x-y)(x_i-y_i)\geq m\sum_{i=1}^n(x_i-y_i)^2.$$

Hay una forma explícita para deducir la convexidad de fuerte convexidad?

Answer 1

$$f(\lambda x + (1-\lambda)y)\le \lambda f(x)+(1-\lambda)f(y)$$ es equivalente a $$\lambda \,\a la izquierda( f(\lambda x + (1-\lambda)y) - f(x)\right) \le (1-\lambda)\,\a la izquierda( f(y)-f(\lambda x + (1-\lambda)y) \right)$$ Esta desigualdad se puede escribir como

$$\lambda \int_0^1\nabla f(x+s(1-\lambda)(y-x))\cdot(y-x) (1-\lambda) ds\le \\ \le(1-\lambda)\int_0^1 \nabla f(y+s\,\lambda (x-y))\cdot(y-x)\lambda ds$$ O, equivalentemente, $$\lambda (1-\lambda)\int_0^1\left(\nabla f(u)-\nabla f(v)\right)\cdot(y-x)\,ds \le 0$$

donde$u=x+s(1-\lambda)(y-x)$$v=y+s\,\lambda (x-y)$. Ahora tenga en cuenta que $$u-v=x+s(1-\lambda)(y-x) - y-s\,\lambda (x-y)=(x-y)(1-s)$$ Por lo que la anterior desigualdad puede ser escrito como $$\lambda (1-\lambda)\int_0^1\left(\nabla f(u)-\nabla f(v)\right)\cdot(v-u)\,\frac{1}{1-s}ds \le 0$$ lo cual es cierto porque $f$ es fuertemente convexo.

Answer 2

Aquí le damos algunos intuición. Supongo que es de $f$ $C^2$ y $Hf(x)$ sea el hessian de $f$ en x. Si $y$ es cerca de $x$, entonces el $\nabla f(y) - \nabla f(x) \approx Hf(x)(y-x)$,\begin{align} \langle Hf(x) (y-x),y-x\rangle &\approx \langle \nabla f(y) - \nabla f(x),y-x \rangle \ & \geq m | y - x |_2^2. \end {alinee el}

Esto sugiere que el $Hf(x) \succeq mI$ y en particular que $Hf(x) \succeq 0$ (para todos los $x$).

Sabemos que esta última condición implica $f$ es convexo.

Answer 3

En mi opinión, fuerte convexidad implica convexidad debido a su definición. De hecho, cabe recordar que la $f:\mathbb{R}^n\rightarrow\mathbb{R}$ es fuertemente convexo si existe $m>0$ tal que $$f (tx+(1-t)y]\leq tf(x)+(1-t)f(y)-\frac{mt(1-t)}{2}\|x-y\|^2$$ para todos los $t\in[0, 1]$ $x, y\in\mathbb{R}^n$ (definición de fuertemente convexa). Desde $$\frac{mt(1-t)}{2}\|x-y\|^2\geq 0,$$ de ello se sigue que $$f (tx+(1-t)y]\leq tf(x)+(1-t)f(y)$$ y por lo $f$ es convexa.

Observación. El hecho de que un fuerte convexidad implica la convexidad no necesita la diferenciabilidad de $f$ como en la prueba de @Pocho la pantera y @littleO.