Lasso ADMM con restricción positiva

Question

Estoy resolviendo el Lasso con ADMM.

El problema viene dado por:

$$ \begin{align*} \arg \min_{x} & \left\{ {\left\| A x - b \right\|}_{2}^{2} + \lambda {\left\| x \right\|}_{1} \right\} \\ \text{ s.t. } & x \succeq 0 \end{align*} $$

Estoy tratando de abordar la restricción de desigualdad por otra restricción de igualdad. $$x = \epsilon^2$$

Las preguntas son

• ¿Admite la ADMM dos restricciones de igualdad?
• ¿Existe otro enfoque para resolver el Lasso con una restricción positiva?

Answer 1

Esta es una variación bastante simple del LASSO ya que la restricción es fácil de resolver (es decir, su proyección tiene una solución de forma cerrada que es simple).

Definamos $ f \left( x \right) = \frac{1}{2} \left\| A x - b \right\|_{2}^{2} + \lambda \left\| x \right\|_{1} $ .

Lo resolví utilizando 3 métodos.

Método del subgradiente proyectado

El Sub Gradiente viene dado por:

$$ \partial f \left( x \right) = {A}^{T} \left( A x - b \right) + \lambda \operatorname{sign} \left( x \right) $$

La proyección sobre $ \mathbb{R}_{+} $ está dada por:

$$ \operatorname{Proj}_{ \mathbb{R}_{+} } \left( x \right) = \max \left\{ x, 0 \right\} $$

La iteración es sencilla:

$$ {x}^{k + 1} = \operatorname{Proj}_{ \mathbb{R}_{+} } \left( {x}^{k} - \alpha \partial f \left( x \right) \right) $$

Donde $ \alpha $ es el tamaño del paso del algoritmo.

Método del Gradiente Proximal

El El método del gradiente proximal para LASSO es bien conocido .
Se podría ver como una generalización del Método del Gradiente.
Por lo tanto, añadiendo el Paso de Proyección como arriba en su iteración resuelve el problema (más rápido) también.

ADMM

Hay un gran grado de libertad para resolver esto utilizando el marco ADMM.
El enfoque que hice fue sólo una pequeña alteración de la solución clásica para el LASSO usando ADMM. Solo apliqué la proyección sobre la variable que es el umbral.
No funciona a la perfección (la función objetivo no disminuye monótonamente), pero funciona muy bien y la idea se basó en el ADMM (descomposiciones duales).

Este es el resultado que obtuve validado contra CVX:

Observaciones

• Se puede utilizar el Método Acelerado para acelerar aún más el Método del Gradiente Proximal.
• Se podría formular el problema utilizando una función indicadora sobre el ortante no negativo. Esto dará lugar a un ADMM clásico para LASSO en el que el $ x $ iteración requerirá resolver Mínimos cuadrados lineales no negativos en lugar de Mínimos Cuadrados Lineales.
• Existen algunas otras formulaciones para el LASSO Restringido (Aunque la anterior es específica para lo anterior mientras que aquellas son más generales) como:
  • Algoritmos de ajuste del LASSO restringido (Ver SparseReg MATLAB Toolbox ).
  • Optimización convexa distribuida con muchas restricciones convexas .
  • Método de los multiplicadores de dirección alterna generalizado: Nuevos conocimientos teóricos y aplicaciones .

El código está disponible en mi StackExchange Matemáticas 2706108 Repositorio GitHub .