1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

How to minimise a function of integers?

  1. Jul 18, 2012 #1
    I want to find the positive integer, [itex]x[/itex], which minimises the following function:[tex]f(x) = (mn - 2(n-1)x - 1)^2[/tex]where [itex]m[/itex] and [itex]n[/itex] are positive integers. I also have the further constraint that:[tex]\frac{m}{x} = \mathrm{positive \ integer}[/tex]I guess calculus might not be a good route to take, since [itex]x[/itex] can only take certain discrete values. Indeed, computing [itex]\frac{d}{dx}f(x)[/itex] and equating to zero gives:[tex]x_{\mathrm{min}}=\frac{mn-1}{2(n-1)}[/tex]which does not necessarily lead us to the correct solution (if we round to the nearest integer factor of [itex]m[/itex]).

    Does anyone know how to solve this sort of problem?
     
    Last edited: Jul 18, 2012
  2. jcsd
  3. Jul 18, 2012 #2

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    What is the shape of the function? (as a function of real numbers)
     
  4. Jul 18, 2012 #3
    i personally don't see how you can do better than what you have.
    let's say m = 2^4*3^3 = 432
    if n is a low value, say 5, i get...
    (432*5-1)/(2*(5-1)) = 269; closest factor being 216.

    (432*5-2*4*216-1)^2 = 431^2.
    no other factor of 432 give a smaller value.
    if n is large, say 7^3 = 343...
    (432*343-1)/(2*(343-1)) = 216.
    again, plugging 216 in we see no factor of m gives a better result.
     
  5. Jul 18, 2012 #4
    I'm not sure if I fully understand the question... I have attached a graph showing an example where the minimum value of [itex]f(x)[/itex] (where fractional/non-integer quantities are allowed) does not fall closest to the minimum allowable discrete value.

    http://desmond.imageshack.us/Himg801/scaled.php?server=801&filename=shapeu.jpg&res=landing [Broken]

    In this case, the minimum is at [itex]\frac{m}{x}=1.8865[/itex], which is closer to 1 than the optimal value 3. I could probably find more extreme failures, but the shape is generally something like this.
     

    Attached Files:

    Last edited by a moderator: May 6, 2017
  6. Jul 18, 2012 #5

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    I was asking for the shape of f(x) (being a well-known shape), but if you know the shape of f(m/x), then that's good enough.

    The broad shape of the graph is it starts at some value, it decreases until it reaches a minimum, and then increases until it reaches a final value.

    So, if you know the graph has this overall shape and you know where the true minimum occurs, and you know which values of x are allowed, do you see how to combine that information?
     
  7. Jul 18, 2012 #6
    I don't think I do. Perhaps it would be easier for me to think about [itex]f(x)[/itex] because that would be a parabola, which at least is symmetrical about the minimum...?
     
  8. Jul 18, 2012 #7
    No matter how I look at it, I can't see how to restrict the solution to the allowable discrete values (to give some sort of closed-form expression). Although I can evaluate any example numerically, doing that doesn't really give me much real insight into the nature of the problem.

    Any more ideas?
     
  9. Jul 18, 2012 #8

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    The solution has to be either the closest factor of m to the left of the minimum, or the closest one on the right. Which one can easily be distinguished by direct computation. Because of the geometry of the parabola, your original guess (nearest factor of m to the real minimum) is correct.
     
  10. Jul 18, 2012 #9
    Of course... how stupid of me! I don't know how I missed that.

    If the function to be minimised is not symmetrical about the minimum, then I guess I'd be in trouble (?)... but my problem here is straightforward.

    Many thanks for the help!
     
  11. Jul 18, 2012 #10

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    In this case, you can compare both function values there, as mentioned before. As long as you have the shape "falling, minimum, rising", this works. If there are additional minima and maxima hanging around, it can become tricky.
     
  12. Jul 18, 2012 #11
    Yeah, I guess you know that one or the other must be the minimum... but I just feel that computing the values and comparing them seems a bit inelegant. I suppose I'm just used to the simple continuous case where I end up with a nice expression in [itex]x[/itex].

    I've heard some talk about convex/non-convex optimisation. Is my problem a simple example of a convex problem?
     
  13. Jul 18, 2012 #12

    uart

    User Avatar
    Science Advisor

    Harry you havd the right idea when you said that you should use the value of x as close as possible to [itex]x_{min}=\frac{mn-1}{2(n-1)}[/itex]

    But you should have expressed it as,

    [itex]\frac{m}{k}[/itex] as close as possible to [itex]\frac{mn-1}{2(n-1)}[/itex]

    which gives,

    [itex]\frac{1}{k}[/itex] as close as possible to [itex]\frac{mn-1}{2m(n-1)}[/itex]

    Where "k" is one of the factors of "m".
     
  14. Jul 18, 2012 #13

    uart

    User Avatar
    Science Advisor

    ^ ... continued

    So in your numerical example above. Instead of solving for possible values of "x" that made 27/x as close as possible to the ideal value of 1.8865. You should instead have been solving for the value of k (where x = 27/k) such that 1/k is as close as possible to 1/1.8865. This would lead you directly to k=3 rather than k=1.
     
  15. Jul 18, 2012 #14
    I would say that the minimum (for the constraints you gave us) should always occur when x = 1. I am not absolutely sure, but I'll show you what I did:

    Suppose the minimum is [itex] k^2 [/itex]. Then we want the x for which

    [itex] f(x) = (mn - 2(n-1)x - 1)^2 = k^2 [/itex].

    Now all numbers are required to be positive integers so k must be an integer. (by the way, I put k^2 because the left side is a perfect square).

    so [itex] mn - 2(n-1)x - 1 = ± k [/itex].

    so [itex] x = \frac {1 - mn ± k} {2(1-n)} [/itex]

    since x is a positive integer, 1 - mn ± k must be divisible by 2(1-n).
    the smallest value of k for which 1 - mn + k is divisible by 2(1-n) is when 1 - mn + k = 2(1-n) (this is the smallest possible multiple of itself). so k = 2(1-n)-1+mn = 1 + mn - 2n.

    This will be a positive integer whenever m ≥ 2 (and if m = 1 then x must be 1 anyways because x divides m). So x is 2(1-n) / 2(1 - n) = 1 which divides m.

    (and so we can't use 1 - mn - k because in this case, x would be less than 1, but there are no positive integers less than 1).


    So the minimum respecting your constraints should always occur at x = 1
     
    Last edited: Jul 18, 2012
  16. Jul 18, 2012 #15

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Think of it this way: it's a simple solution to a simple problem. And simple solutions are usually better than complicated solutions for any problem.

    There is definitely value in considering alternative ways to solve problems, looking for new things to learn and new ideas that can be applied in general.

    However, there is the danger of getting in the habit of being "too clever", and wind up making problems many, many times harder because you overlook a straightforward method.

    Worse, it can even prevent you from solving problems: if you aren't in the habit of recognizing "oh, there are only two possibilities, I can just try them both out", then that will lead to a failure to look for -- or even recognize -- solutions to hard problems that begin with"do something clever to reduce the problem to one of two possibilities...."
     
  17. Jul 19, 2012 #16

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    You construct the minimal x, not the minimal k.
    We already have counterexamples in the thread.
     
  18. Jul 19, 2012 #17
    oops I guess I messed up haha :P sorry for that

    EDIT: ahhh forget it I think I see it. the denominator is 2(1-n) which is negative, so what I did was nonsense.
     
    Last edited: Jul 19, 2012
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: How to minimise a function of integers?
Loading...