How can I constrain linear_least_squares to integer solutions?
Hi,
I have successfully used LinearAlgebra.linear_least_squares to estimate solutions to continuous functions. The coefficients returned in that case are of course floatingpoint values.
Now I have a problem where some of the terms are continuous but some must be constrained to integer multiples. As a simple example,
y = c1 * x^2 + c0 * x
where c1 is floatingpoint in the usual way, but c0 can only be integervalued. (The actual problem has many more terms.)
Can anyone tell me how to constrain some of the coefficients to integer values?
Thank you for any insight.
Mark
On Nov 27, 2007 9:51 PM, Mark Schmucker Mark.Schmucker@4dtechnology.com wrote:
Hi,
I have successfully used LinearAlgebra.linear_least_squares to estimate solutions to continuous functions. The coefficients returned in that case are of course floatingpoint values.
Now I have a problem where some of the terms are continuous but some must be constrained to integer multiples. As a simple example,
y = c1 * x^2 + c0 * x
where c1 is floatingpoint in the usual way, but c0 can only be integervalued. (The actual problem has many more terms.)
Can anyone tell me how to constrain some of the coefficients to integer values?
This is not a trivial problem, as you can see by googling mixed integer
least squares (MILS). Much will depend on the nature of the parameters, the number of variables you are using in the fit, and how exact the solution needs to be. One approach would be to start by rounding the coefficients that must be integer and improve the solution using annealing or genetic algorithms to jig the integer coefficients while fitting the remainder in the usual least square way, but that wouldn't have the elegance of some of the specific methods used for this sort of problem. However, I don't know of a package in scipy that implements those more sophisticated algorithms, perhaps someone else on this list who knows more about these things than I can point you in the right direction.
Chuck
On Tue, Nov 27, 2007 at 11:07:30PM 0700, Charles R Harris wrote:
This is not a trivial problem, as you can see by googling mixed integer least squares (MILS). Much will depend on the nature of the parameters, the number of variables you are using in the fit, and how exact the solution needs to be. One approach would be to start by rounding the coefficients that must be integer and improve the solution using annealing or genetic algorithms to jig the integer coefficients while fitting the remainder in the usual least square way, but that wouldn't have the elegance of some of the specific methods used for this sort of problem. However, I don't know of a package in scipy that implements those more sophisticated algorithms, perhaps someone else on this list who knows more about these things than I can point you in the right direction.
Would this be a good candidate for a genetic algorithm? I haven't used GA before, so I don't know the typical rate of convergence or its applicability to optimization problems.
Regards Stéfan
Hello everyone,
I am trying to sum points onto a 3d grid using "put" with a list of computed array indices. I am looking for a version of "put" which increments, e.g. replace:
for i in ind: a.flat[i] = v[i]
with "+=" to increment. Other operations might also be useful?
I tried using "take", then incrementing the result, but still have problems if the indices are not unique.
Thanks for any suggestions,
Jon
On Nov 28, 2007 12:59 AM, Stefan van der Walt stefan@sun.ac.za wrote:
On Tue, Nov 27, 2007 at 11:07:30PM 0700, Charles R Harris wrote:
This is not a trivial problem, as you can see by googling mixed integer
least
squares (MILS). Much will depend on the nature of the parameters, the
number of
variables you are using in the fit, and how exact the solution needs to
be. One
approach would be to start by rounding the coefficients that must be
integer
and improve the solution using annealing or genetic algorithms to jig
the
integer coefficients while fitting the remainder in the usual least
square way,
but that wouldn't have the elegance of some of the specific methods used
for
this sort of problem. However, I don't know of a package in scipy that implements those more sophisticated algorithms, perhaps someone else on
this
list who knows more about these things than I can point you in the right direction.
Would this be a good candidate for a genetic algorithm? I haven't used GA before, so I don't know the typical rate of convergence or its applicability to optimization problems.
Regards Stéfan _______________________________________________ Numpydiscussion mailing list Numpydiscussion@scipy.org http://projects.scipy.org/mailman/listinfo/numpydiscussion
If the number of terms is not huge and the function is well behaved; it might be worth trying the following simple and stupid approach:
1. Find the floating point minimum. 2. for each set of possible set of integer coefficients near the FP minimum: 1. Solve for the floating point coefficients with the integer coefficients fixed. 2. If the minimum is the best so far, stash it somewhere for later. 3. Return the best set of coefficients.
On Nov 28, 2007 12:59 AM, Stefan van der Walt stefan@sun.ac.za wrote:
On Tue, Nov 27, 2007 at 11:07:30PM 0700, Charles R Harris wrote:
This is not a trivial problem, as you can see by googling mixed integer
least
squares (MILS). Much will depend on the nature of the parameters, the
number of
variables you are using in the fit, and how exact the solution needs to
be. One
approach would be to start by rounding the coefficients that must be
integer
and improve the solution using annealing or genetic algorithms to jig
the
integer coefficients while fitting the remainder in the usual least
square way,
but that wouldn't have the elegance of some of the specific methods used
for
this sort of problem. However, I don't know of a package in scipy that implements those more sophisticated algorithms, perhaps someone else on
this
list who knows more about these things than I can point you in the right direction.
Would this be a good candidate for a genetic algorithm? I haven't used GA before, so I don't know the typical rate of convergence or its applicability to optimization problems.
It depends. Just to show the sort of problems involved, suppose you have 32 integer variables and are looking for the last bit of optimization. If the floating point optimum is at (.5, .5, ...., .5) and the error is symmetrical, then each vertex of the surrounding integer cube is a solution and there are 2**32 of them. If the error isn't symmetrical, and chances are that with that many variables it is very far from that, then you have to search a larger region. That's a lot of points. The more sophisticated algorithms try to eliminate whole regions of points and keep narrowing things down, but even so the problem can easily get out of hand. If you just need a good solution, a genetic algorithm is a good bet to find one without too much hassle. I had a similar problem in designing a digital min/max FIR filter where I needed 15 bit integer coefficients for hardware implementation. There was a narrow high rejection band in the filter and simply rounding the coefficients left spikes in the response through that band. With a GA I was able to eliminate the spikes in about 30 minutes of evolution using a python/Numeric program. In that case the performance of annealing was quite dependent on choosing the right parameters for cooling rate, etc., while the GA was quite robust and straight forward. There was no guarantee the I ended up with the best solution, but what I got was good enough.
Chuck
participants (5)

Charles R Harris

Jon Wright

Mark Schmucker

Stefan van der Walt

Timothy Hochberg