Debilitando las condiciones de unicidad para el descenso de gradiente

Question

Sea $f : \mathbb{R}^n \to \mathbb{R}$ una función coercitiva y estrictamente convexa.

Sé que si $f \in \mathcal{C}^1$ (i.e., las primeras derivadas de $f$ son continuas), entonces para cualquier conjetura inicial $x_0 \in \mathbb{R}^n$, el algoritmo de descenso de gradiente converge al mínimo global único $x^*$ de $f$. Sin embargo, es posible que el descenso de gradiente converja a mínimos globales de funciones que no son $\mathcal{C}^1$ (e.g., $f = \|\cdot\|_1$).

¿Existen condiciones más generales sobre $f$ que garanticen la convergencia única del descenso de gradiente cuando las primeras derivadas de $f$ son discontinuas en a lo sumo un conjunto de medida cero (para que $f$ aún admita subgradientes en estos puntos)?

Answer 1

Teorema:
Sea $f$ una función coercitiva, estrictamente convexa y $L$-Lipschitz, $L > 0$. Denotemos por $\partial f(x)$ el subdiferencial de $f$ en el punto $x \in \mathbb R^n$. Para todo $x^0 \in \mathbb R^n$, existe $(\alpha_k)_{k\geq 0}\subseteq \mathbb R$ con $\forall k, \alpha_k \geq 0$; $\sum_k \alpha_k^2 < \infty$; y $\sum_k \alpha_k = \infty$, tal que el algoritmo de descenso de subgradiente, $$ x^{k+1} := x^k - \alpha_k g^k, \qquad g^k \in \partial f(x^k) $$ converge a la solución óptima $x^*$ en el sentido de que $x^k_\mathrm{best} \xrightarrow{k\to \infty} x^*$ donde $$ x^k_\mathrm{best} := \arg\min \{ f(w) : w = x_j, 0\leq j \leq k \}. $$

Prueba.
La prueba sigue un material similar al libro de Optimización Convexa de Boyd y Vandenberghe. Por definición, \begin{align*} \|x^* - x^{k+1}\|_2^2 &= \|x^k - x^*\|_2^2 - 2\alpha_k \langle g^k , x^k - x^*\rangle + \alpha_k^2 \|g^k\|_2^2 \\ &\leq \|x^k - x^*\|_2^2 - 2\alpha_k (f(x^k) - f(x^*)) + \alpha_k^2 \|g^k\|_2^2 \\ &\leq \|x^0 - x^*\|_2^2 - \sum_{j\leq k} \alpha_j (f(x^j) - f(x^*)) + \sum_{j \leq k} \alpha_j^2 \|g_j\|_2^2 \end{align*} Ahora, $\|x^{k+1} - x^*\|_2^2 \geq 0$ y $\|x^0 - x^*\|_2^2 = R$ para algún $ R> 0$. Por lo tanto, para $x^j_\mathrm{best}$ como se define arriba, se sigue que \begin{align*} 2 (f(x^k_\mathrm{best}) - f(x^*)) \sum_{j\leq k} \alpha_j \leq 2 \sum_{j\leq k} (f(x^j) - f(x^*)) \leq R^2 + \sum_{j\leq k} \alpha_j^2 \|g^j\|_2^2 \end{align*} Para $g \in \partial f(x)$ y $y \in \mathbb R^n$ con $f$ siendo $L$-Lipschitz, $|\langle g, x-y\rangle| \leq |f(x) - f(y)| \leq L \|x-y\|_2$. Esto, por definición de la norma del operador para $\langle g, \cdot \rangle$ implica que $\|g\|_2 \leq L$. Por lo tanto, la expresión anterior se puede reorganizar como \begin{align*} f(x^k_\mathrm{best}) - f(x^*) \leq \frac{R^2 + L^2 \sum_{j\leq k} \alpha_j^2}{2\sum_{j\leq k} \alpha_j} \xrightarrow{k\to\infty} 0. \end{align*> Se sigue de la convexidad estricta y coercitividad de $f$ que $x^k_\mathrm{best} \xrightarrow{k\to\infty} x^*.