How to minimise a function of integers?

weetabixharry

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?

Hurkyl

What is the shape of the function? (as a function of real numbers)

phillip1882

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.

weetabixharry

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.



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 Thumbnails

 

Hurkyl

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?

weetabixharry

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...?

weetabixharry

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?

Hurkyl

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.

weetabixharry

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!

mfb

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.

weetabixharry

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?

uart

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".

uart

^ ... 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.

Boorglar

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

Hurkyl

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...."

mfb

You construct the minimal x, not the minimal k.
We already have counterexamples in the thread.

Boorglar

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.