Optimization with integers as results

  • Context: Graduate 
  • Thread starter Thread starter maistral
  • Start date Start date
  • Tags Tags
    Integers Optimization
Click For Summary

Discussion Overview

The discussion revolves around the challenge of fitting a dataset (X, Y) to a quadratic function of the form y = Ax^2 + By + Cxy, with the constraint that the coefficients A, B, and C must be integers. Participants explore various methods for achieving this, including grid search and combinatorial optimization, while addressing the complexities involved in finding integer solutions.

Discussion Character

  • Exploratory
  • Technical explanation
  • Debate/contested

Main Points Raised

  • One participant inquires about the specifics of the dataset and the definition of "best fit," questioning the domains of the data and suggesting that multiplying by denominators could be a strategy if the data consists of finite decimal numbers.
  • Another participant proposes that the problem could be framed as a diophantine minimization problem, suggesting that a minimum solution for the coefficients A, B, and C should exist and that an exhaustive search in a bounded integer space might not be overly time-consuming on a fast machine.
  • A different participant notes that combinatorial optimization is generally considered a hard problem and mentions that finding an optimum integer solution typically requires significant computational effort.
  • This participant also suggests using heuristics such as "relaxation," where the problem is first solved in real numbers before rounding to integers, acknowledging that this may not yield an optimal solution but could provide a reasonably good approximation.
  • There is some confusion expressed regarding the original problem, particularly about what it means to fit a dataset to a function and whether the goal is to find the best fitting quadratic with integer coefficients.

Areas of Agreement / Disagreement

Participants express differing views on the nature of the problem and the methods for solving it. There is no consensus on the best approach or the specifics of the dataset, indicating that the discussion remains unresolved.

Contextual Notes

Limitations include unclear definitions of "best fit," the nature of the dataset, and the assumptions underlying the proposed methods. The discussion does not resolve these ambiguities.

maistral
Messages
235
Reaction score
17
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.
 
Physics news on Phys.org
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.
 
Reply
  • Like
Likes   Reactions: pbuk
maistral said:
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.
 
Reply
  • Skeptical
Likes   Reactions: pbuk
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?
 

Similar threads

Undergrad Finding the Largest (or smallest) Value of a Function - given some constant symmetric errors
  • · Replies 3 ·
Replies
3
Views
2K
Undergrad Absolute difference between increasing sum of squares
  • · Replies 22 ·
Replies
22
Views
3K
Undergrad How Can Nested Summation Functions Be Simplified or Reversed?
  • · Replies 6 ·
Replies
6
Views
2K
MHB Optimization - Lagrange multipliers : minimum cost/maximum production
  • · Replies 3 ·
Replies
3
Views
2K
Undergrad Optimization problem: Error mitigation while using trigonometry
  • · Replies 18 ·
Replies
18
Views
3K
Undergrad Maximizing xy: Understanding Optimization Problems in Mathematics
  • · Replies 2 ·
Replies
2
Views
1K
Graduate Parameter optimization for the eignevalues of a matrix
  • · Replies 0 ·
Replies
0
Views
2K
Undergrad Multivariable optimization problem
  • · Replies 6 ·
Replies
6
Views
2K
MHB Minimize a function: Find value of x that result in lowest value of formula
  • · Replies 6 ·
Replies
6
Views
2K
Proving that an Integer lies between x and y using Set Theory
  • · Replies 15 ·
Replies
15
Views
2K