# Minimization with asymptotic assumption

Given the function

$$g(n,m)=\min\Big\{f(a,b)+f(n-a,c)+f(n,m-bc)\Big|\\a,b,c\ \ \text{with} \left\{\begin{matrix} a,\ b,\ n-a,\ c,\ m-bc \geq 0 \\ b\leq a! \\ c\leq (n-a)! \\ \end{matrix}\right. \Big\}$$

Assuming that $$n,m\geq 0,\ ((\lceil n/2\rceil)!)^2\leq m\leq n!,\ f(n,m)=\Omega (n)$$,

is it true that $$g(n,m) \geq 2f(\lfloor n/2\rfloor ,(\lfloor n/2\rfloor)!)+f(n,m-((\lceil n/2\rceil)!)^2)$$ ?

I tried KKT conditions, but can't derive this (as it contains factorial).

Also, it seems that the condition $$f(n,m)=\Omega (n)$$ implies that $$f$$ is convex on our domain (and thus, satisfies the regularity condition for using KKT), but I managed to prove it only if $$f$$ is polynomial.

So I am fully stuck in this...

Any help would be highly appreciated!

• I'm not sure whether it makes sense to write for $f(n,m) = \Omega(n)$ for $n,m$ in some range; asymptotic analysis relates to what happens if we let $n$ and $m$ go to infinity, and your range upper-bounds $m$ so it can't go to infinity independent of $n$, and so $n$ can't go to infinity independent of $m$. Also, asymptotic notation with respect to two variables is not entirely well-defined; I don't know if that introduces any issues here. See cs.stackexchange.com/q/3149/755. – D.W. May 3 at 15:37
• The Gamma function extends factorial to a real analytic function (which in particular has derivatives of all order). – Yuval Filmus May 3 at 23:58