$ {L}_{1} $ Problema de optimización regularizada sin restricciones

Question

Me encuentro con un problema de minimización sin restricciones. El problema es de la forma

$$\min_x \frac{\|x-a\|_2^2}{2}+\lambda\|x\|_1$$

donde $x,a \in R^n$ y $x$ es la variable de optimización. $\lambda \in R$ . El problema se puede separar en cada coordenada como sigue,

$$\min_{x_i} \frac{(x_i-a_i)^2}{2}+\lambda|x_i|$$

Encontré en algún recurso que el óptimo $x_i^*$ tiene la forma $ x_i^* = \operatorname{sign}(a_i)\max(0,|a_i|-\lambda)$ . Me cuesta entender porque es la solución óptima para el problema. Espero que alguien me ayude.

Gracias.

Answer 1

Hay una forma geométrica clara de ver por qué esto debe ser así, pero he olvidado algunos de los detalles. Algunos documentos de Daubeches, Dohono, etc. contienen estos detalles. Lamentablemente, también he olvidado estas referencias. Así que os daré la solución un poco perezosa (probablemente ya os habréis dado cuenta de que soy una persona muy perezosa), basada en operadores proximales y en la identidad de Mureau...

Para una función convexa $f: \mathbb R^n \rightarrow (-\infty, +\infty]$ definir su operador próximo

$$\text{prox}_{\lambda f}(a) := \underset{x \in \mathbb R^n}{\text{argmin }} \frac{1}{2}\|x-a\|_2^2 + \lambda f(x),$$

donde $\lambda > 0$ es un parámetro variable. Piensa en esto como una generalización de la noción de proyección sobre un conjunto convexo, donde el función de indicador se sustituye por una más general $f$ . Su problema consiste en calcular el operador proximal del $\ell_1$ -normas.

Definir el (Legendre) conjugado convexo de $f$ por

$$f^*(a) := \max_{x \in \mathbb R^n}\langle a, x\rangle - f(x).$$

Ahora, si $f := \|.\|_1$ y definimos el cubo $C^{(n)} := \{z \in \mathbb R^n|\|z\|_\infty \le \lambda\} = C^{(1)} \times \ldots \times C^{(1)}$ entonces $f^*\left(\frac{a}{\lambda}\right) = i_{C^{(n)}}(a)$ (ver por qué aquí ), y así $$\text{prox}_{\frac{1}{\lambda} f^*}\left(\frac{a}{\lambda}\right) = \ldots = P_{C^{(n)}}(a) = (P_{C^{(1)}}(a_1),\ldots,P_{C^{(1)}}(a_n)) = (\lambda \text{sgn}(a_1), \ldots,\lambda\text{sgn}(a_n)),$$ la proyección euclidiana de $a$ en el cubo $C$ . Así, por la identidad de Mureau, obtenemos $$ \text{prox}_{\lambda f}(a) = a - \text{prox}_{\frac{1}{\lambda} f^*}\left(\frac{a}{\lambda}\right) = a - P_{C^{(n)}}(a) = (a_1 - \lambda \text{sgn}(a_1), \ldots, a_n - \lambda \text{sgn}(a_n)) = (S_\lambda(a_1),\ldots, S_\lambda(a_n)),$$ donde $S_\lambda: t \mapsto \text{sgn}(t)(t - \lambda)_+$ El soft-thresholder .

N.B: $\text{sgn}(0) := 0$ . Además, tenga en cuenta que $t = |t|\text{sgn}(t)$ para todos $t \in \mathbb R$ .

Espero que esto ayude. Puedo proporcionar detalles más finos si es necesario.

Answer 2

Dado que sólo hay una variable en su problema reducido, puede encontrar la mejor opción de $x_i$ sólo utilizando técnicas de pre-cálculo. (Considera por separado los casos $x_i \geq 0$ y $x_i \leq 0$ y visualiza la gráfica de una función cuadrática en cada caso).

He aquí un punto de vista diferente (resumido muy brevemente). Dejemos que $f(x) = \|x\|$ , donde $\| \cdot \|$ es cualquier norma. Nótese que el conjugado convexo de $f$ es la función indicadora de la bola unitaria de norma dual $B$ . De la descomposición de Moreau se deduce que \begin{equation} \text{prox}_{tf}(x) = x - P_{tB}(x), \end{equation} donde $P_{tB}(x)$ es la proyección de $x$ en $tB$ .

En el caso especial de que $f(x) = \| x \|_1$ la norma dual es la $\ell_\infty$ -norma, por lo que $tB = \{ z \mid -t \leq z_i \leq t \text{ for all }i\}$ . En este caso, la proyección sobre $P_{tB}$ es particularmente simple, y se puede ver (cuando se resuelve) que su fórmula para $\text{prox}_{tf}(x)$ sigue.

Answer 3

El problema de optimización dado por el operador Prox:

$$ \operatorname{Prox}_{\lambda {\left\| \cdot \right\|}_{1}} \left( x \right) = \arg \min_{u} \left\{ \frac{1}{2} {\left\| u - x \right\|}^{2} + \lambda {\left\| u \right\|}_{1} \right\} $$

Este problema es separable con respecto a ambos $ u $ y $ x $ por lo que se podría resolver el siguiente problema:

$$ \arg \min_{ {u}_{i} } \left\{ \frac{1}{2} {\left( {u}_{i} - {x}_{i} \right)}^{2} + \lambda \left| {u}_{i} \right| \right\} $$

Ahora, se puede proceder utilizando la condición de optimalidad de primer orden y el subgradiente de la $ \operatorname{abs} \left( \cdot \right) $ o puedes emplear un simple truco.

El truco está en entender que $ {u}_{i} $ puede ser positivo, cero o negativo.

Suponiendo que $ {u}_{i} > 0 $ la derivada viene dada por $ {u}_{i} - {x}_{i} + \lambda $ que desaparece para $ {u}_{i} = {x}_{i} - \lambda $ y se mantiene para $ {x}_{i} > \lambda $ .
El mismo procedimiento para el caso $ {u}_{i} < 0 $ produce $ {u}_{i} = {x}_{i} + \lambda $ para $ {x}_{i} < -\lambda $ .
Para los valores de $ {x}_{i} $ en el medio, ya que ${u}_{i} = 0 $ y por lo tanto la derivada (Sub Gradiente) de $ {u}_{i} $ puede elegirse libremente en la gama $ \left[ -1, 1 \right] $ el valor de $ {u}_{i} = 0 $ se mantiene.

En resumen:

$$ \operatorname{Prox}_{\lambda {\left\| \cdot \right\|}_{1}} \left( x \right)_{i} = \operatorname{sign} \left( {x}_{i} \right) \max \left( \left| {x}_{i} \right| - \lambda, 0 \right) $$