# Minimizing a cubic polynomial over $\Bbb N$ [closed]

Let the polynomial function $$f : \Bbb N \to \Bbb N$$ be defined by

$$f (M) := 2M^3N + 2M^3 - M^2N^2 - 3M^2N + 2M^2 - MN^3 + MN^2 - 2MN + \frac{N^4}{2} + \frac{N^2}{2}$$

where $$N$$ is given natural number. I am interested in finding the value (or values) of $$M$$ that minimizes $$f$$. Could anyone please provide guidance on how to approach this problem?

Code

I've written a code that calculates the minimum, over $$\Bbb N$$ and the limit tends to be approximately $$0.608$$:

import numpy as np
import matplotlib.pyplot as plt

def theory(N):
M = np.arange(1, N)
r = 2 * np.power(M, 3) * N + 2 * np.power(M, 3) - np.power(M, 2) * np.power(N, 2) - 3 * np.power(M, 2) * N + 2 * np.power(M, 2) - M * np.power(N, 3) + M * np.power(N, 2) - 2 * M * N + np.power(N, 4) / 2 + np.power(N, 2) / 2
return M[np.argmin(r)]

if __name__ == '__main__':
N = 200
series_theory = [theory(i)/i for i in range(2, N+1)]
plt.plot(series_theory,'b')
plt.show()



• With $N$ fixed, you just have a cubic in $M$. You've restricted to $M$ and $N$ being natural numbers, so the leading coefficient of this cubic is positive. This should be enough for you to find the value of $M$ that minimises the expression. Commented Jan 1 at 23:40
• @ChrisLewis do you mean take this function as a continues function and calculate its derivative? If so, that's not what I'm looking for. I'm trying to find an exact, integer solution. Commented Jan 1 at 23:48
• That's (almost) exactly what I mean. You know the shape of the cubic, so the minimum is found in one of three places: either at $M=1$, or at the largest integer below a real-valued minimum, or the least integer above it. Unless the expression factorises (which I assume you checked), there's not likely to be a simpler way Commented Jan 2 at 0:18
• (This approach is pretty common for integer optimisation; you relax conditions to allow real values so that you can calculate exact, analytical results, then bring the integer conditions back after.) Commented Jan 2 at 0:19
• What do you mean by "taking the limit over $N$"? You specified that $N$ was fixed. Commented Jan 2 at 0:27

\begin{align} f(M,N) &\equiv 2M^3N + 2M^3 - M^2N^2 - 3M^2N + 2M^2 - MN^3 + MN^2 - 2MN + \frac{N^4}{2} + \frac{N^2}{2} \\ f(p,N) &= N^4 \left((2 + \frac{2}{N})p^3 + (-1 -\frac{3}{N} + \frac{2}{N^2})p^2 + (-1 + \frac{1}{N} - \frac{2}{N^2})p + (\frac{1}{2} + \frac{1}{2N^2})\right), \quad p \equiv \frac{M}{N} \\ g(p) &\equiv \lim_{N \to \infty} \frac{f}{N^4} = 2 p^3 - p^2 - p + \frac{1}{2} \\ \frac{dg}{dp} &= 6 p^2 - 2p - 1 \\ \frac{dg}{dp} &= 0 \; \Rightarrow \; p = \frac{1 \pm \sqrt{7}}{6} = -0.274, 0.607 \end{align}
Since $$M$$ has to be positive, then the above analysis implies that the ratio of optimal $$M$$ for a given $$N$$ should approach 0.607 as $$N$$ grows, which matches the simulated results from the OP's plot.
• Thank you for your answer. I only have one question, I'm a bit confused where you have taken the limit of $\frac{f}{N^4}$. Can you provide more explanation? Commented Jan 2 at 7:01
• In the limit of large $N$, $f$ gets dominated by the highest order of $N$. After the $M=pN$ substitution (since you're interested in the ratio), $N^4$ is the highest order. So minimising $f$ becomes equivalent to minimising the coefficient of $N^4$. $\frac{f}{N^4}$ allows us to focus on just the coefficient. Commented Jan 2 at 10:20
In general, to minimize a polynomial $$p(x)$$ over integer values $$x \in \mathbb{Z}$$, find all critical points of $$p(x)$$, i.e., all values of $$x$$ where $$p'(x)=0$$. Let $$a_1,\dots,a_k$$ be those values, in increasing order. Then evaluate $$p(\cdot)$$ at each of the $$2k$$ points $$\lfloor a_1 \rfloor, \lceil a_1 \rceil, \lfloor a_2 \rfloor, \dots, \lceil a_k \rceil$$. Whichever one yields the smallest value of $$p(x)$$, is the global minimum of $$p(x)$$ over all integers, assuming a minimum exists. (Or, to make this more elegant, also evaluate $$p(\cdot)$$ at $$-\infty$$ and $$+\infty$$ as well as the above $$2k$$ values, and take the minimum of all of these values. This gives the global infimum. Then you don't have to worry about whether a global infimum exists.)
Why does this work? In each interval $$(a_i,a_{i+1})$$, $$p'(x)$$ is either always positive or always negative, so $$p(x)$$ is either monotonically increasing or monotonically decreasing. It follows that the local minimum, among the integers, within that interval must be at either $$\lceil a_i \rceil$$ or $$\lfloor a_{i+1} \rfloor$$. The global minimum must exist within one of these intervals, hence is covered by the above procedure.
Since $$N$$ is fixed, your expression is a cubic polynomial of $$M$$ with known coefficients, so you can apply the above procedure to it. This amounts to computing the derivative of it (a quadratic polynomial), then finding its roots (which can be done using the quadratic formula), then rounding each root both up and down, and evaluating your polynomial at each such candidate value.