Given $y \in \mathbb{R}^{n \times 1}, X \in \mathbb{R}^{n \times p}$, $p > n$, assume a LASSO-type optimization problem in the form of

$$ \hat\beta=\underset{\beta}{\operatorname{argmin}}\frac{1}{2}\left\|y - X \beta \right\|_{2}^{2} + \sum_{i}p(|\beta_i|; \gamma; \lambda)$$

where $p(|\beta_i|; \gamma; \lambda)$ is a non-convex function in $\beta$ with $\gamma$ and $\lambda$ denoting the degree of regularization and non-convexity. Typically known examples are SCAD, MCP penalties, among probably many others.

My question: I want to implement solutions for known penalties and test out some custom penalties. What are currently the faster known solvers that would be able to adequately tackle such problems? Which family of solvers should I be looking at for quick/feasible computations? Are there any general solvers, or do they highly depend on the specific penalty function?

My initial approach was to start from Augmented Lagrangian for every $\lambda, \gamma$ throughout the solution path, which seem to work for small $n$ and $p$ values, given $p < n$, but doesn't seem to scale well into bigger problems.

  • $\begingroup$ Are you interested in computing the optimal $\hat{\beta}$, or are you okay with computing some locally optimal solution to your problem? If it is the former, then since you have not provided the functional form of $p$, it is hard to recommend a particular solver, otherwise you can try using a generic Non convex solver like Baron. If you are interested in a locally optimal solution and $\beta$ is unconstrained in its domain, then I would recommend looking at Coordinate descent methods and Proximal methods. $\endgroup$
    – batwing
    Aug 19, 2020 at 15:48
  • $\begingroup$ @batwing Thanks, will look into these. Local solutions would be a great start. One question about Baron though -- is it a proprietary paid software, or are there any existing free realizations available in R/Python/Matlab etc? $\endgroup$
    – runr
    Aug 20, 2020 at 12:44
  • $\begingroup$ To the best of my knowledge there is a free academic license for Baron. I have never really used this software myself, but there are plenty of contributors on this stack exchange who will be able to guide you about Baron and other non-convex solvers, their licenses and other miscellaneous informaton. $\endgroup$
    – batwing
    Aug 20, 2020 at 14:58
  • $\begingroup$ There is a free "demo" version of BARON which handles up to 10 variables, 10 constraints, and 50 total nonlinear operations (the latter is usually the most constraining limitation). BARON can be called from MATLAB, or from YALMIP under MATLAB, or from PYOMO, JUMP, AMPL, or GAMS, among others. See minlp.com/baron . You can also use the "free" BMIBNB branch and bound global optimization solver under YALMIP, but you will generally need to have available a local nonlinear solver for ti to call,such as FMINCON or IPOPT (under OPTI-toolbox) and a MILP solver for it to call. $\endgroup$ Sep 7, 2020 at 14:35


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.