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

Question

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()

Answer 1

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

Answer 2

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.