I would like to run a lasso regression (L1 penalisation) with a twist: there are different constraints on my problem.

The coefficients for my features (predictors) are $\beta_i$.

I want to find the $\beta_i$ such that $\sum_{i = 1}^n X_i \beta_i = Y + \epsilon$

under the constraints:

  • $\beta_i \ge 0$ $\forall i$
  • $\sum_{i=1}^K \beta_i = 1$
  • $\sum_{i = K+1}^n \beta_i \le c$

How can I achieve this? I am using python2.7, so any solution using sckit-learn or scipy would be greatly appreciated!

  • 1
    $\begingroup$ Asking for code is off-topic, but I'm pretty sure this is a linear program. $\endgroup$ – Sycorax Mar 10 '16 at 15:35

I don't see anything in the documentation of scikit learn that could help you doing this:

 class sklearn.linear_model.Lasso(alpha=1.0, fit_intercept=True,
     normalize=False, precompute=False, copy_X=True, max_iter=1000, tol=0.0001,
     warm_start=False, positive=False, random_state=None, selection='cyclic')

However, CVXOPT would be a perfect starting point for writing this specific optimization problem. Here is an example with regularized least square: RLS.

  • $\begingroup$ (+1) The problem is simply a quadratic program--an interior point method will work. Of course, another method could be faster. $\endgroup$ – user795305 May 26 '17 at 15:48

You can initialize the model parameters randomly to fit the constraints, and then run a form of gradient descent where you project the resulting coefficients onto the nearest plane that satisfies the constraints, as well. Since this is done with smaller steps at a time (ideally smaller steps as the number of iterations grows), it should converge.

A simpler(?) solution would be to construct a "wall" function that heavily penalizes constraint violations, and then project the final solution onto the constraints if you need an exact match.

I would recommend theano for this, since it makes iterative models relatively easy and compiles the code in C for faster performance.

Note that projecting on a convex hull is a bit more complicated than just a plane, but this paper outlines the algorithm. Because your constraints are a bit different than the one in the paper, I would impose the constraints on the two cutoff points ( i < K, i >= K) separately. The second constraint is not exact, so I think you can just omit points from the algorithm that already satisfy the constraints. Someone please correct me if I am wrong on this.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.