Existencia del minimizador de una función fuertemente convexa en un conjunto convexo cerrado

Question

Sea $f : \mathbb{R}^n \to \mathbb{R}$ sea fuertemente convexa. Consideremos el problema

$$\min_{x \in A} f(x)$$

donde $A \subseteq \mathbb{R}^n$ es no vacío, convexo y cerrado. Supongamos también $\inf_{x \in A} f(x) < \infty$ (si no es el caso, entonces $f(x) = \infty$ para todos $x \in A$ que no es un escenario especialmente interesante).

Sé que si $f$ tiene un minimizador, en $A$ es única (véase este para saber por qué). Mi pregunta es si estas condiciones son suficientes para garantizar la existencia de dicho minimizador. Si no es así, ¿qué más habría que suponer para implicarlo?

EDIT: He aquí la definición de fuertemente convexo (de Wikipedia): $f$ es fuertemente convexa si existe una constante $m > 0$ tal que para todo $x$ y $y$ en el dominio y $\lambda \in [0,1]$ se cumple la siguiente desigualdad:

$$f(\lambda x + (1-\lambda)y) \leq \lambda f(x) + (1-\lambda) f(y) - \frac{1}{2} m\lambda (1-\lambda) \| x - y \|^2$$

Esto equivale a lo siguiente:

$$g := f - \frac{m}{2}\|\cdot\|^2$$

es convexo, donde $\|\cdot\|$ es inducido por un espacio producto interior. Véase este para más información sobre la equivalencia de estas definiciones.

Answer 1

Gracias a los que ya habéis respondido, habéis sido de gran ayuda. A continuación expondré la solución que he encontrado, con más detalle que en otras respuestas.

Primero necesitamos el siguiente lema:

Lema : $\lim_{\|x\| \to \infty} f(x) = \infty$ . Algunos autores lo denominan $f$ en coercitivo .

Prueba: Sea $x_0 \in \mathbb{R}^n$ y que $v$ sea un subgradiente de $g$ en $x_0$ es decir $x_0 \in \partial g(x_0)$ . Por equivalencia de normas en espacios vectoriales de dimensión finita, existe una constante $c > 0$ tal que $\|x\|_2 \leq c \|x\|$ para todos $x \in \mathbb{R}^n$ . Por Cauchy-Schwarz y la desigualdad de trinagle, para $\|x\| > 0$ tenemos

$$ \begin{align*} \frac{| v^T(x - x_0) |}{\frac{m}{2}\|x\|^2} &\leq \frac{\|v\|_2 \|x - x_0\|_2}{\frac{m}{2}\|x\|^2} \\ &\leq \frac{\|v\|_2 \|x\|_2 + \|v\|_2 \|x_0\|_2}{\frac{m}{2}\|x\|^2} \\ &\leq \frac{c\|v\|_2 \|x\| + \|v\|_2 \|x_0\|_2}{\frac{m}{2}\|x\|^2} \\ &= \frac{2c\|v\|_2 \|x\|}{m} \frac{1}{\|x\|} + \frac{2\|v\|_2 \|x_0\|_2}{m} \frac{1}{\|x\|^2} \end{align*} $$

El extremo derecho de esta desigualdad $\to 0$ como $\|x\| \to \infty$ lo que implica que $v^T(x - x_0) + \frac{m}{2} \|x\|^2 \to \infty$ como $\|x\| \to \infty$ . Ahora utilizamos la definición de subgradiente:

$$ \begin{align*} v^T(x - x_0) &\leq g(x) - g(x_0) \\ v^T(x - x_0) + \frac{m}{2}\|x\|^2 &\leq g(x) + \frac{m}{2}\|x\|^2 - g(x_0) \\ v^T(x - x_0) + \frac{m}{2}\|x\|^2 + g(x_0) &\leq f(x) \end{align*} $$

La parte izquierda de este $\to \infty$ como $\|x\| \to \infty$ por lo que concluimos que $f(x) \to \infty$ como $\|x\| \to \infty$ . $\square$

Pasemos al resultado principal. En primer lugar, supongamos que $A$ no tiene límites. Si es acotada, entonces es compacta, y el resultado se deduce inmediatamente. Hay 2 posibilidades mutuamente excluyentes:

Caso 1: $f$ tiene un minimizador en $A$ en cuyo caso es única (véase este hilo).

Caso 2: $f$ no tiene un minimizador en $A$ .

Supongamos que tenemos el caso 2. Sea $f^\star := \inf_{x \in A} f(x)$ . $f^\star < \infty$ por suposición. Sea $(x_k)$ sea una secuencia en $A$ tal que $f(x_k) \to f^\star$ . Ahora tenemos dos subcasos mutuamente excluyentes:

Subcaso 2.1: $\sup_k \|x_k\| = d < \infty$ . Defina $B_d := \{ x \in \mathbb{R}^n \ : \ \|x\| \leq d\}$ . Entonces para todos $k$ , $x_k \in \{ A \cap B_d \}$ que es cerrado y acotado y, por tanto, compacto. Por lo tanto $(x_k)$ converge en $A$ es decir $x_k \to x^\star$ para algunos $x^\star \in A$ . Continuidad de $f$ implica $f(x^\star) = f^\star$ lo cual es una contradicción.

Subcaso 2.2: $\sup_k \|x_k\| = \infty$ . Esto implica $\|x_k\| \to \infty$ y por el lema esto implica $f(x_k) \to \infty$ lo que implica $f^\star = \infty$ que contradice $f^\star < \infty$ .

Por lo tanto, concluimos que no puede darse el caso 2 y, por lo tanto, debe darse el caso 1.

EDIT: Después de escribir todo esto, está claro que $f$ fuertemente convexo es una suposición más fuerte de lo que requerimos. $f$ estrictamente convexa y coercitiva es suficiente para que $f$ tenga un mínimo global único en el conjunto convexo $A$ .

Answer 2

Sí, es cierto si la convexidad fuerte significa que $$f(y) \ge f(x) + \lambda^\top (y - x) + \frac m2 \, \|x-y\|^2\qquad\forall y \in A,$$ donde $x \in A$ , $\lambda \in \mathbb R^n$ (es un subgradiente) y $m > 0$ . De hecho, se puede comprobar que el minimizador tiene que pertenecer al conjunto $$B := A \cap \{y \in \mathbb R^n \mid \|y\| \le R\}$$ para algunos $R > 0$ suficientemente grande, ya que $$f(\tilde y ) \ge f(x)$$ es válido para $y \in A$ , $\|y\| > R$ (si $R$ se elige suficientemente grande). Ahora bien, la existencia se deduce de la compacidad de $B$ .

No se cumple si nos limitamos a suponer una convexidad estricta, $f(x) = \exp(x)$ para $A = \mathbb R$ .

Answer 3

La convexidad fuerte por sí sola no es suficiente para garantizar la existencia de un minizer. Para ver esto consideremos la función $f:[0,1] \to \mathbb{R}$ , $$ f(x) = \begin{cases} x^2 & \text{if $x > 0$,} \\ 1 & \text{if $x=0$.} \end{cases} $$ Esta función es $2$ -fuertemente convexa, es decir, que satisface $$ f(tx+(1−t)y) \le tf(x)+(1−t)f(y) − t(1−t)(x−y)^2 $$ para todos $x,y,t \in [0,1]$ . Sin embargo, $f(x)$ no tiene minimizador.

Esto significa que una hipótesis adicional sobre $f$ para garantizar la existencia de un minimizador.

Edición: La suposición extra estándar que se suele hacer es que la función es semicontinua inferior. En ese caso, el minimizador existe y es único. El ejemplo anterior NO es semicontinuo inferior.

Edición2: Función convexa $f:\mathbb{R}^n \to \mathbb{R}$ es necesariamente continua en todo el dominio $\mathbb{R}^n$ . Así que mi contraejemplo sólo funciona si el dominio de la función es un subconjunto estricto de $\mathbb{R}^n$ .

Answer 4

Según su definición : $f$ es fuertemente convexa significa que $g=f - \frac{m}{2}\|\cdot\|^2$ es convexa. Por lo tanto $g$ es convexa por lo que tiene al menos un subgradiente, digamos $v \in \partial g(x_0)$ así $$v.(x-x_0) \leq g(x)-g(x_0)$$ $$v.(x-x_0) +\frac{m}{2}\|x\|^2 \leq g(x)+ \frac{m}{2}\|x\|^2 -g(x_0)$$ $$v.(x-x_0) +\frac{m}{2}\|x\|^2 \leq f(x) -g(x_0)$$ Esto demuestra $\lim_{\|x\| \rightarrow\infty} f(x)= +\infty$ lo que implica que los conjuntos de niveles de $f$ son acotadas por lo que son compactas (ya que son cerradas), por lo tanto $f$ alcanza su mínimo en su conjunto de niveles, este mínimo seguro que es golobal mínimo ya que está en un conjunto de niveles.

Answer 5

Si el conjunto $A$ es compacto (ya que $A \subseteq R^{n}$ , compacto es simplemente "cerrado y acotado"), entonces una función fuertemente convexa tiene un mínimo único en $A$ . Es fácil demostrar que $f$ no puede tener varios puntos mínimos. Es un teorema estándar del análisis que una función continua alcanza su mínimo en un conjunto compacto.