Is there a closed form solution to the following optimization problem?

231 Views Asked by At

Find $\operatorname*{arg max}_{i,j_n} f(i,j_n) := \sum_{n=1}^N{(j_n-\lambda i)}$

subject to

$ 0<\lambda<1 $ ($\lambda$ is known)
$ j_n\leq m_n $ ($m_n$ are known $\forall n$ )
$ j_n \leq i $
$i,j_n,m_n$ are non-negative integers.

A possible solution will be $i$ and $j_n$ in terms of $m_n$ and $\lambda$. It is acceptable to have a non-unique solution.

2

There are 2 best solutions below

2
On BEST ANSWER

First note that the objective can be simplified to $\sum_{n=1}^N j_n -\lambda N i$. Now sort the $m_j$ into ascending order ($m_1\le m_2 \le \dots \le m_N$). Observe that, for fixed $i$ (and subject to the bound on $j_n$), larger values of $j_n$ are preferable. Similarly, for fixed $j_n$ smaller values of $i$ are preferable. So if $m_K\le i\le m_{K+1}$, we can assume that $i=m_K$ and the solution will be $$ j_{n}=\begin{cases} m_{n} & n\le K\\ m_K & n>k \end{cases} $$with objective value $$\sum_{n=1}^K m_n + (N-K) m_K - \lambda N m_K = \sum_{n=1}^K m_n + \left[\left(1-\lambda\right)N-K\right]m_K.$$

Now consider the change $\Delta$ in objective value if we bump $i$ from $m_K$ to $m_{K+1}$. If my algebra is correct (you should definitely check it), $$\begin{align*} \Delta & =m_{K+1}+\left(1-\lambda\right)N\left(m_{K+1}-m_{K}\right)-(K+1)m_{K+1}+Km_{K}\\ & =\left(m_{K+1}-m_{K}\right)\left[\left(1-\lambda\right)N-K\right] \end{align*}.$$ The left factor is nonnegative courtesy of the sort. The right factor is nonnegative for smaller $K$ (so keep increasing) and nonpositive for larger $K$ (oops, overshot). So $K = \left\lfloor \left(1-\lambda\right)N\right\rfloor $ looks like a winner to me.

4
On

This is my attempt, hopefully of some use. We want to maximise $$ f(i,j_n) = \sum _{n=1}^{N} (j_n - \lambda i) $$ subject to the constraints you mentioned.

First, we consider the case $ i > \max{m_j}$. In this case the target function is maximised to $$ f(i,j_n) = \sum _{n=1}^{N} (m_n - \lambda i) $$ (as $j_n \leq m_n$ and we want the first term to be as large as possible). In this case, increasing $i$ is clearly deleterious, as the second, negative addend in the target function grows. If on the other hand $ i < \min{m_n}$, the target function is maximised to $$ f(i,j_n) = \sum _{n=1}^{N} (i - \lambda i) = \sum _{n=1}^{N} (i (1- \lambda )) $$ Further decreasing $i$ is also reducing the target function.

Let us then consider the case $ i = \min{m_n}$. Let us also relax for a moment the constraint that $i$ must be an integer, and also consider a “variation”, $\hat{i} = i + \epsilon$, where $\epsilon$ is a positive constant such that $ \hat{i} $ is smaller than the next to the smallest ${m_n}$. The difference between the optimised target function computed for $i$ and $\hat{i}$ equals $$ f(\hat{i},j_n) - f(i,j_n) = \sum _{n=1}^{N-1} ((i +\epsilon)(1- \lambda )) + \min{(m_n)} -\lambda \hat{i} - \sum _{n=1}^{N} (i (1- \lambda )) $$ which equals $$\sum _{n=1}^{N-1} \epsilon (1-\lambda) -\lambda \epsilon $$ (recalling we took $i = \min{m_n}$), which is positive if $$\frac{N-1}{N} > \lambda$$ If were the case, increasing $\epsilon$ increases the target function value, and the argument can be iterated taking $i$ as the second smallest ${m_j}$, the $j-$th, and so forth, as long as $\frac{N-j}{N-j+1}$ is positive This indicates that the target function is maximised for $i = m_k$ (which is an integer by definition), where $k$ is the last index for which $\frac{N-j}{N-j+1}$ is positive. One of your constraints then forces the condition $j_k = m_k $.