Oh, claro que sí, hay un montón de herramientas. Haga una búsqueda para proximal gradiente de métodos en su motor de búsqueda favorito; estas son generalizaciones de la proyectada gradiente de métodos. Para herramientas específicas, búsqueda de TFOCS (divulgación de abajo), FISTA, NESTA, SPGL1, GPSR, SpaRSA, L1LS... y la bibliografía para estos va a llevar aún más opciones. Aún mejor, ver a esta extensa lista de primer orden de métodos compilado por Esteban Becker como parte de su más dispersas y de baja rango de aproximación de la wiki.
Un básico proximal método de gradiente considera que su función como la suma de una suave plazo $f(x)=\tfrac{1}{2}x^TAx+b^Tx$ y no liso sino que "prox-capaz de términos"$g(x)=\lambda\|x\|_1$. En cada iteración, se utiliza el gradiente de la lisa
plazo $v=\nabla f(x)=Ax+b$ y calcula el siguiente paso utilizando un proximal de minimización de
$$x^{+} = \mathop{\textrm{arg min}}_z ~ \lambda \|z\|_1 + \tfrac{1}{2t} \|x-tv-z\|_2^2$$
donde $t$ es de un tamaño de paso. Muchas de las presentaciones de estos métodos suponen un paso fijo tamaño determinado por una de Lipschitz de la continuidad de la medida, pero tal tamaños de paso son siempre muy conservador. Así, un simple paso el tamaño de la estrategia de adaptación es esencial para un buen rendimiento.
Métodos más avanzados utilizan el mismo gradiente y proximal de minimización de los cálculos, pero la mezcla de esa información en diferentes formas para lograr una demostrable de mejora en el peor de los casos el rendimiento. Pero resulta que para que su función es fuertemente convexo, debido a su afirmación de que $A$ es positiva definida. Así que una proximal algoritmo de gradiente estructura es probablemente una muy buena elección.
Yo co-escribió TFOCS con Esteban Becker y Emmanuel Candes. TFOCS es una de MATLAB basado en la caja de herramientas que le permite construir personalizado de primer orden solucionadores de problemas utilizando una variedad de algoritmos, suave funciones, operadores lineales, y de proximidad funciones. Se escribió un acompañamiento de artículo de revista . Nuestro objetivo era estructurar el código de tal manera que es fácil de probar una variedad de primer orden a los métodos de sus modelos, y para hacer que el código que implementa las iteraciones en sí, fácil de leer. Pero en realidad, es sólo uno de los muchos paquetes de software, y por supuesto, si usted no desea utilizar MATLAB, vas a tener que intentar algo más!
Si usted está dispuesto y es capaz de factorizar $A=R^TR$, entonces también puede utilizar el estándar de herramientas de LAZO:
$$\min_x \tfrac{1}{2} \| R x - \bar{b} \|_2^2 + \lambda \|x\|_1 - \tfrac{1}{2} \bar{b}^T\bar{b}, \qquad
\bar{b}\triangleq - R^{-T} b$$
No se limite a LARS; hay un montón de enfoques alternativos, y de ahí muchos de los paquetes de arriba específicamente a apoyar el LAZO. Pero la cosa buena acerca de muchas (pero no todas) de las herramientas mencionadas anteriormente, incluyendo TFOCS, es que no necesariamente tienes que hacer la factorización si usted prefiere no.
Por último, esto es, por supuesto, un problema de optimización convexa, por lo que cualquier propósito general convexa marco de optimización será capaz de manejar esto con aplomo, aunque de forma menos eficaz que en estos métodos especializados. Normalmente se repartirán $x$ en positivo y negativo partes:
$$x=x^{+} - x^{-}, \quad x^{+}, x^{-} \succeq 0$$
Esto permite la sustitución de $\|x\|_1=\vec{1}^T(x^{+}+x^{-})$, en cuyo caso el problema se convierte en un estándar de la QP.
Edición principal de la historia:
- Aclaró que el OP función es fuertemente convexo, debido a la
positiva la certeza de $A$.
- Añadida una nota sobre la importancia de
el tamaño de paso de la adaptación en la práctica; gracias littleO.
- Añadido enlaces a
Esteban Becker escasa aproximación wiki; gracias icurays1.
