I have this optimization function

1/2au^2 + bu + lambda |c+ u|

This paper says that the solution is given by

enter image description here

where enter image description here

Can anyone please tell me how it was derived?

asked Oct 16 '13 at 17:02

Jason%20Tyler's gravatar image

Jason Tyler
16131315


One Answer:

This is derived by doing a proximal gradient algorithm, where you at each step minimize a convex upper bound on the lasso problem. If the function you're minimizing looks like f(x) + lambda |x|_1, where f is smooth (has a lipschitz continuous gradient), you can upper bound this function by

f(x) + lambda |x|\_1 <= f(x\_0) + grad f(x\_0)^T(x - x\_0) + C ||x - x\_0||^2 + lambda |x|\_1.

Minimizing this upper bound leads to a gradient-and-thresholding algorithm, which can also be implemented as doing a gradient step with learning rate 1/C and then applying a proximal operator. See how to derive the tresholding operation in this previous answer.

answered Oct 17 '13 at 10:33

Alexandre%20Passos's gravatar image

Alexandre Passos ♦
2554154278421

edited Oct 17 '13 at 10:33

Your answer
toggle preview

powered by OSQA

User submitted content is under Creative Commons: Attribution - Share Alike; Other things copyright (C) 2010, MetaOptimize LLC.