curve fitting with integer inputs Python 3.3

Question

I am using scipy's curvefit module to fit a function and wanted to know if there is a way to tell it the the only possible entries are integers not real numbers? Any ideas as to another way of doing this?

Answer 1

In its general form, an integer programming problem is NP-hard ( see here ). There are some efficient heuristic or approximate algorithm to solve this problem, but none guarantee an exact optimal solution.

In scipy you may implement a grid search over the integer coefficients and use, say, curve_fit over the real parameters for the given integer coefficients. As for grid search. scipy has brute function.

For example if y = a * x + b * x^2 + some-noise where a has to be integer this may work:

1. Generate some test data with a = 5 and b = -1.5:

   coef, n = [5, - 1.5], 50
   xs = np.linspace(0, 10, n)[:,np.newaxis]
   xs = np.hstack([xs, xs**2])
   noise = 2 * np.random.randn(n)
   ys = np.dot(xs, coef) + noise
   

2. A function which given the integer coefficients fits the real coefficient using curve_fit method:

   def optfloat(intcoef, xs, ys):
       from scipy.optimize import curve_fit
       def poly(xs, floatcoef):
           return np.dot(xs, [intcoef, floatcoef])
       popt, pcov = curve_fit(poly, xs, ys)
       errsqr = np.linalg.norm(poly(xs, popt) - ys)
       return dict(errsqr=errsqr, floatcoef=popt)
   

3. A function which given the integer coefficients, uses the above function to optimize the float coefficient and returns the error:

   def errfun(intcoef, *args):
       xs, ys = args
       return optfloat(intcoef, xs, ys)['errsqr']
   

4. Minimize errfun using scipy.optimize.brute to find optimal integer coefficient and call optfloat with the optimized integer coefficient to find the optimal real coefficient:

   from scipy.optimize import brute
   grid = [slice(1, 10, 1)]  # grid search over 1, 2, ..., 9
   # it is important to specify finish=None in below
   intcoef = brute(errfun, grid, args=(xs, ys,), finish=None)
   floatcoef = optfloat(intcoef, xs, ys)['floatcoef'][0]
   

Using this method I obtain [5.0, -1.50577] for the optimal coefficients, which is exact for the integer coefficient, and close enough for the real coefficient.