3
$\begingroup$

My question is similar to: How do I fit a constrained regression in R so that coefficients total = 1? except that I am interested in a solution to the following constraints on the parameters:

All $\pi_i$ should be -1, 0 or 1.

Basically: How do I fit a regression when the only allowed weights are -1, 0 or 1?

Improve this question
$\endgroup$
4
  • $\begingroup$ Canned software packages and modules don't always offer such options. On the other hand, SEMs and/or nonlinear models typically offer the most flexibility in this regard. Of course, both assume that an explicit model of some type has been formulated. In other words, these are not exploratory, variable selection procedures. $\endgroup$
    – user78229
    Commented Jul 8, 2016 at 15:56
  • 4
    $\begingroup$ How many $\pi_i$ 's are there? Are the $\pi_i$'s the only parameters to be estimated, or are there also continuous parameters? This should be solvable by use of (mixed) integer quadratic programming, for which there are many off the shelf solvers, both free and commercial. The actual computational difficulty for the solver to find the optimal solution depends on the size and difficulty of the problem. Another option would be to solve this as a (mixed) integer Second Order Cone Problem (SOCP), which may or may not be easier (faster) to solve, but requires more knowledge to formulate. $\endgroup$
    – Mark L. Stone
    Commented Jul 8, 2016 at 16:01
  • 2
    $\begingroup$ As per @hxd1011 's answer, if the number of integer parameters to be estimated s sufficiently small, brute force evaluation of the sum square of residuals for all possible combinations of parameter values is another option. The methods I mentioned in the preceding comment can be many times faster than brute force evaluation, because they are able to intelligently prune out possibilities, as the algorithm proceeds, which must be inferior to already evaluated parameter value combinations. $\endgroup$
    – Mark L. Stone
    Commented Jul 8, 2016 at 16:05
  • 1
    $\begingroup$ I just came across this ready to go MATLAB package which explicitly deals with (mixed0 integer least squares problems cs.mcgill.ca/~chang/software/MILES.php . $\endgroup$
    – Mark L. Stone
    Commented Jul 18, 2016 at 16:59

1 Answer 1

Reset to default
3
$\begingroup$

This seems to be a discrete optimization problem, where you have integer (some of the decision variables / parameters are discrete) constrains on the decision parameters. Comparing to continuous optimization, discrete optimization is much harder to solve: many continuous optimization problems can be solved in $P$ time but most real world discrete optimization problems are $NP$.

If your problem is not in large scale, you can run a brute-force search. For example, if you have $10$ parameters and each parameter has $3$ possible values, the search space is $3^{10}=59049$, which can be done in seconds with modern computer. On the other hand, please note, the search space grows exponentially, if you have $20$ parameters, the brute force is not feasible.

When I say search, I mean, try different configurations of parameters and calculate the loss/objective function. (for example, squared loss in regression). Check for the configurations with lowest loss. Here is an example on mtcars data with $2$ parameters, each of them takes $\{-1,0,1\}$. In this toy example, the optimal solution is $(0,0)$, and has minimal loss of $14042.31$.

enter image description here

As mentioned earlier, if you have more parameters, then, such approach is not feasible. You may want to do two things.

Integer programming one will give you exact answer with high computation cost, and local search is fast, but may give you sub-optimal answer. Each one is a huge topic you can explore and I think it is hard to explain them in detail here.

Edit: as Mark mentioned in the comment, comparing to general discrete optimization problem, the problem has a special structure: the problem is the objective function is quadratic, therefore Mixed Integer Quadratic Programming (MIQP) software can be used. In addition,

Another option would be to solve this as a (mixed) integer Second Order Cone Problem (SOCP), which may or may not be easier (faster) to solve, but requires more knowledge to formulate.

Improve this answer
$\endgroup$
10
  • 1
    $\begingroup$ I don't think constraint programming is going to do the trick here. $\endgroup$
    – Mark L. Stone
    Commented Jul 8, 2016 at 16:07
  • $\begingroup$ I also think your "Local Search" link will just confuse matters. $\endgroup$
    – Mark L. Stone
    Commented Jul 8, 2016 at 16:43
  • $\begingroup$ replaced with wikipeida link $\endgroup$
    – Haitao Du
    Commented Jul 8, 2016 at 16:51
  • $\begingroup$ I think the better solution is to fit the normal regression without any constraint. Then to do the search only on the voisinage of the continuous solution! $\endgroup$
    – Metariat
    Commented Jul 8, 2016 at 21:08
  • $\begingroup$ Thank you very much hxd1011 and @MarkL.Stone -- there are many $\pi_i$. Nevertheless a good idea to do brute force for small cases. Can you elaborate a bit more for integer programming? Are there readily available tools which achieve that? Mattemattica: That's an interesting idea too, does it work? $\endgroup$
    – dreamflasher
    Commented Jul 11, 2016 at 8:15

Your Answer

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

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