Teorema del valor medio para un gradiente de función convexa

Question

Esto es de un artículo página 19. Deja que $J(u)=\sum \sqrt {u_i^2+\epsilon}$ y $p^{k+1}=\nabla J(u^{k+1})$ , $p^{k}=\nabla J(u^{k})$ . Desde $J$ es convexo, el teorema del valor medio nos dice que $$p^{k+1}-p^{k} = D^{k+\frac{1}{2}}(u^{k+1}-u^k) $$ donde $D^{k+\frac{1}{2}}$ es una matriz diagonal tal que $$D^{k+\frac{1}{2}}_{i,i} = \epsilon ((u_i^{k+\frac{1}{2}})^2+\epsilon)^{-3/2}$$ para algunos $u^{k+\frac{1}{2}}$ entre $u^k$ y $u^{k+1}$ .

Pero no puedo entender por qué hay tal $D^{k+\frac{1}{2}}$ . Dejemos que $f(u)=\sqrt {u^2+\epsilon}$ entonces $f'(u)=u/\sqrt{u^2+\epsilon}$ , $f''(u)=\epsilon/\sqrt{u^2+\epsilon}^3$ . Pensé que 2 implementación de MVT:

Método1: Si utilizamos el MVT para los componentes de $p^{k+1}-p^{k}$ entonces obtenemos por separado $u_i^{k+\frac{1}{2}}$ que está en el segmento $[u_i^{k},u_i^{k+1}]$ pero el conjunto $u^{k+\frac{1}{2}}$ puede no estar en el segmento $[u^{k},u^{k+1}]$ . No estoy seguro de que el autor haya querido decir esto.

Método2: Si utilizamos el MVT para $g(t)=\nabla J (u^{k+1}t + u^k (1-t))\cdot(u^{k+1}-u^k) = \sum \frac{u_i}{\sqrt{u_i^2+\epsilon}} (u_i^{k+1}-u_i^k)$ , donde $u_i=u_i^{k+1}t + u_i^k (1-t)$ entonces tenemos $g(1)-g(0)=g'(c) \Rightarrow (p^{k+1}-p^{k}) \cdot (u^{k+1}-u^k)= \sum \frac{\epsilon}{\sqrt{(u_i^{k+\frac{1}{2}})^2+\epsilon}^3}(u_i^{k+1}-u_i^k)^2$ donde $u^{k+\frac 1 2}=u_i^{k+1}c + u_i^k (1-c)$ está en el segmento $[u^{k},u^{k+1}]$ . Pero, ¿cómo podemos concluir que $p^{k+1}-p^{k} = D^{k+\frac{1}{2}}(u^{k+1}-u^k)$ ? ¿Podemos utilizar la convexidad?

Resumen: Quiero saber dónde utilizar el MVT, y la convexidad.

Answer 1

Así que puede haber más contexto necesario, pero creo que esto es falso en general, incluso para una función separable convexa. Tomemos el ejemplo de $f(x,y) = x^4 + y^6$ . Tenemos

\begin {align*} \nabla f(x,y) &= \begin {bmatrix} 4x^3 \\ 6y^5 \end {bmatrix} \\ \nabla ^2 f(x,y) &= \begin {bmatrix} 12x^2 & 0 \\ 0 & 30y^4 \end {bmatrix} \\ \end {align*}

Ahora toma los dos puntos $(0,0)$ y $(x,y)$ y aplicar este "teorema del valor medio" que generará algún punto $(tx,ty)$ para $t\in [0,1]$ en la línea entre $(0,0)$ y $(x,y)$ :

\begin {align*} \nabla f(x,y) - \nabla f(0,0) &= \begin {bmatrix} 4x^3 \\ 6y^5 \end {bmatrix} \\ \begin {bmatrix} 4x^3 \\ 6y^5 \end {bmatrix} &= \begin {bmatrix} 12t^2x^2 & 0 \\ 0 & 30t^4y^4 \end {bmatrix} \left ( \begin {bmatriz} x \\ y \end {bmatrix} - \begin {bmatrix} 0 \\ 0 \end {bmatrix} \right ) \\ &= \begin {bmatrix} 12t^2x^3 \\ 30t^4y^5 \end {bmatrix} \end {align*}

Ahora bien, para que este teorema del valor medio sea cierto, necesitamos tanto $t^2 = 1/3$ y $t^4 = 1/5$ . Evidentemente, esto no puede ser nunca así.

Hay otros teoremas de valor medio que el de 1D que son posibles ( https://en.wikipedia.org/wiki/Mean_value_theorem#Mean_value_theorem_for_vector-valued_functions ), pero ninguno como éste.

Si se aplica la MVT a los componentes, el resultado será un punto que no está necesariamente en la línea, sino en la caja que se extiende entre los dos puntos (esto es lo que creo que los autores tenían en mente). Leyendo el documento, este punto que está en la línea entre los dos iterados no es realmente importante para la prueba. Lo importante es la proximidad de este punto al origen, que determina cómo se compara con $\epsilon$ .

Answer 2

Dada la $J$ tiene, nota $$ \nabla J_i = \frac{u_i}{\sqrt{u_i^2 +\epsilon}} $$ Así, $$ \nabla^2 J_{ij} = \frac{\partial^2 J}{\partial u_i \partial u_j}= \delta_{ij} \left ( \frac{1}{\sqrt{u_i^2 +\epsilon}} - \frac{u_i^2}{(u_i^2 +\epsilon)^{3/2}}\right)=\frac{\delta_{ij} \epsilon}{(u_i^2 + \epsilon)^{3/2}}$$ El teorema del valor medio viene dado aquí por para $\nabla J_i$ viene dada por $$ \nabla J_i (x) - \nabla J_i (y) = \nabla (\nabla J_i(u_i))\cdot (x-y) $$ con $u_i$ entre $x_i$ y $y_i$ . Así, $$ \nabla J (x) - \nabla J (y) = \nabla^2J(u)\cdot ( x-y) $$ NOTA que $u$ puede no estar en la línea entre $x$ y $y$ . La convexidad no juega realmente un papel directo aquí, ya que tienes una fórmula para $J$ . Pero probablemente se podría argumentar en el caso general utilizando la convexidad $\iff \nabla^2 J \geq 0$ (semidefinido positivo).