# Constrained optimization algorithm in linear regression

I am interested in the following constrained parameter estimation in linear regression, $$\min_\beta\sum_{i=1}^{n}(y_i-x_i\beta)^2 + \lambda \sum_{j}^{p}f(\beta_j)$$ where the model is $y=x\beta+e$, $e_i\sim i.i.d. N(0,\sigma^2)$ and $f$ is a penalty function. As it is obvious from the minimization problem, $f(\beta)=|\beta|$ leads to lasso problem that there are some well-developed algorithm for it, e.g. LARS. I remember in a conference a person talked about using lars for general form of $f$. So my question is about the most efficient algorithm that I can implement (hopefully in R) to get the solution path of the minimization problem.

• Do you have a specific function, $f(\beta)$ in mind? If someone in a conference talked about using lars for general form of $f$, there was probably some limitation in mind as to how general the form of $f$ was. Jul 13, 2016 at 15:29
• This is exactly what I was thinking about. I asked the person and he said any constraint! He was a member of RSS and the conference was running by RSS. Jul 13, 2016 at 15:32
• Hmm, Royal Statistical Society, not Mathematical Optimization Society - not all statisticians really understand optimization In any event, I was not there, and don't know what was said, or in what implicit or explicit context. So what $f$ do you want to use? Is there some reason you want to use something other than LASSO? Jul 13, 2016 at 15:39
• I want to test different functions to see the behaviour of different penalties on estimations. At the meantime, I use optim function in R that is slow and time-consuming. Jul 13, 2016 at 15:42
• Perhaps you should list the various penalties you are investigating. Jul 13, 2016 at 15:46

The so-called local linear approximation (LLA) algorithm described in One-step sparse estimates in nonconcave penalized likelihood models by Zou and Li solves the optimization problem for certain concave choices of $f$. Specifically, for $$f(s) = p(|s|)$$ and a concave function $p : [0,\infty) \to [0,\infty)$, which is differentiable on $(0,\infty)$.
The algorithm works by iteratively solving a weighted $\ell_1$-penalized optimization problem. In iteration $k+1$ the solution is given as $$\arg \min \sum_{i=1}^n (y_i - x_i^T \beta)^2 + \lambda \sum_{j=1}^p p'(|\beta_j^{(k)}|) |\beta_j|.$$ Each iteration can be solved using e.g. glmnet or lars in R or another standard implementation that computes the lasso solution and allows for weights.