Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.