# Reference request, discrete optimization problem

i am not an expert in optimization. I have stumbled across an interesting problem which looks to me like there should already exist literature about it. The problem can be phrased as follows: given $n$ functions $\phi_1$, ..., $\phi_n$. Each of these functions is from the positive integers into non-negative real numbers between 0 and 1, and each function is (strict) monotonically increasing. I would like to maximize $\sum_{i=1}^n \phi_i(k_i)$ such that all $k_i$ are non-negative integers and $\sum_{i=1}^n k_i = N$ for some fixed integer $N \ge n$. Does this problem have a name? What is known about it?

-

I doubt this has a name more specific than "constrained optimization". The maximum is attained since the search space is finite. To locate it, consider the discrete analog of one-sided derivatives: $\partial_+\phi_i(k)=\phi_i(k+1)-\phi_i(k)$ and $\partial_-\phi_i(k)=\phi_i(k)-\phi_i(k-1)$. A necessary condition for a point $(k_1^*,\dots,k_n^*)$ to be a point of maximum is the following: $$\max_{1\le i\le n} \partial_+ \phi_i(k_i^*)\le \min_{k_j^*>0} \partial_- \phi_j(k_j^*) \tag{1}$$ Indeed, if (1) fails, then we have $\partial_+ \phi_i(k_i^*)>\partial_- \phi_j(k_j^*)$ for some $i,j$; adding $1$ to $k_i^*$ and subtracting $1$ from $k_j^*$ we would increase the target function.
Monotonicity of $\phi_i$ does not help much. Indeed, any function $\psi: \{0,\dots,N\}\to \mathbb R$ can be written as $\psi(k)=\psi_1(k)+\psi_2(N-k)$ where both $\psi_1$ and $\psi_2$ are increasing. The maximization problem for $\sum_{i=1}^2 \psi_i(k_i)$ under the constraint $k_1+k_2=N$ is equivalent to the maximization of $\psi$.