Optimization with integers as results

[maistral]

Say for example I have a dataset (X, Y) which I need to fit to the function y = Ax^2 + By + Cxy.

How do I retrieve values of A, B, and C such that they can only be integers? As of now I'm doing grid search which is so taxing.

 

[fresh_42]

What does "I have" mean? Do you have a data set you already know, it satisfies such an equation? Do you want the best fit, and if, what is your measure for "best"? Which domains are we talking about? E.g. if all data are some finite decimal numbers, then you could simply multiply with all denominators.

 

[aheight]

Say for example I have a dataset (X, Y) which I need to fit to the function y = Ax^2 + By + Cxy.

How do I retrieve values of A, B, and C such that they can only be integers? As of now I'm doing grid search which is so taxing.

Could perhaps be an interesting (diophantine) minimization problem: Given a set of points $\{x_i,y_i\}$,
find $(A,B,C)\in\mathbb{Z}$ such that some error metric such as:
$$
\int_a^b \big|g(x)-h(x)\big|dx
$$
is minimum where say $g(x)$ is a (relatively) good or good enough fit of the data and $h(x)=Ax^2+Bx+C$? Seems to me there would always exist a minimum solution to such a problem. Wouldn't think such an exhaustive search of a reasonably-bounded integer 3D space (n,m,p) would take very long on a fast machine.

 

[RPinPA]

You've just discovered by combinatorial optimization is considered a "hard" problem. In general searching for an optimum integer solution takes a very long time as you have discovered.

If you can accept merely a pretty-good solution, there are heuristics you can apply. One of them is "relaxation". Solve the problem in real numbers, then round the resulting values to integers. This will in general not give an optimal solution but in many cases you can prove that it is within some bound relative of the optimum solution (for instance, no more than 30% worse).

These are general comments. I can't quite understand what your particular problem is. I don't know what it means to fit a dataset to a function. Do you just mean you have a bunch of (x, y) values and you're trying to find the best fitting quadratic with integer coefficients?