I want to find the maximum of following \begin{align} f(X,Y)=\max_{x_k, y_k} \sum_{k=1}^L log(1+{x_k}\frac{py_k}{1+py_k}) \\s.t. \sum_{k=1}^L x_k=La, \\ \sum_{k=1}^L y_k=Lb \\ a>0, ~\ b>0, ~\ p>0, \\ x_1\ge x_2\ge ... \ge x_L \ge 0\text{ and } y_1\ge y_2\ge ... \ge y_L \ge 0 \end{align}

I have some intuition it might be upper bounded by \begin{align} Llog(1+\frac{pab}{1+pb}) \end{align} where \begin{align} x_1=x_2=...x_L=a ~\ and ~\ y_1=y_2=...=y_L=b \end{align}

is it right? if so how can I prove this rigorously? or how can I find upper bound and the condition satisfying maximum??


  • $\begingroup$ Put a bounty and i will reply $\endgroup$ – Brethlosze May 25 '17 at 0:19
  • $\begingroup$ it said 48 hours later and I will do $\endgroup$ – kkimoz May 25 '17 at 4:39
  • $\begingroup$ where is bounty button? I couldn't find it @hyprfrco $\endgroup$ – kkimoz May 28 '17 at 3:27
  • $\begingroup$ Whatever LOL. What did you tried. What do you know about optimization? $\endgroup$ – Brethlosze May 28 '17 at 14:40
  • $\begingroup$ Unfortunately, I have no reputation and can't put bounty... I would really appreciate if you answer just for your kindness @hyprfco $\endgroup$ – kkimoz May 31 '17 at 18:06

Now we can.

Hence, the objective function:

$$ f=\sum_{i=1}^N log (1+x_i\frac{py_i}{1+py_i}) $$

With the constraints:

$$ g^1=\sum_{i=1}^N x_i-La\\ g^2=\sum_{i=1}^N y_i-Lb $$

Hence the 2L dimension gradients for these functions both for $x_i$ and $y_i$ are (check it!!):

$$ \nabla f_{x_i}=\frac{1}{1+x_i\frac{py_i}{1+py_i}}\frac{py_i}{1+py_i}\\ \nabla f_{y_i}=\frac{1}{1+x_i\frac{py_i}{1+py_i}}\frac{x_i}{(1+py_i)^2}\\ \nabla g^1_{x_i}=1\\ \nabla g^1_{y_i}=0\\ \nabla g^2_{x_i}=0\\ \nabla g^2_{y_i}=1 $$

Hence the optimal condition is the void sum of all that 2L vectors:

$$ -\nabla f_{x_i}+\lambda^1\nabla g^1_{x_i}+\lambda^2\nabla g^2_{x_i}=0\\ -\nabla f_{y_i}+\lambda^1\nabla g^1_{y_i}+\lambda^2\nabla g^2_{y_i}=0 $$

Which is:

$$ \frac{1}{1+x_i\frac{py_i}{1+py_i}}\frac{py_i}{1+py_i}=\lambda^1\\ \frac{1}{1+x_i\frac{py_i}{1+py_i}}\frac{x_i}{(1+py_i)^2}=\lambda^2\\ $$

Hence we have 2L gradient equations, and 2 constraints equations, for 2L coordinates and 2 lagrange multipliers.

If we assume any $\lambda$ is zero, any of the constraints will not hold. Thus both multipliers are nonzero, hence both constraints are active.

As a helper, by dividing both gradient equations, we isolate the $x_i$:

$$ x_i=\frac{\lambda^2}{\lambda^1}py_i(1+py_i) $$

And back in the gradient now we isolate $y_i$:

$$ \frac{1}{\lambda^1+\lambda^2py_i^2}\frac{py_i}{1+py_i}=1 $$

Both of these sets of equations, together eith the constraints, at this point, un-isolatable:

$$ \sum_{i=1}^N x_i=La\\ \sum_{i=1}^N y_i=Lb $$

If everything was right, these expressions are for a 2-D simplex in a 2L-D space, following the non linear ecuations we have just obtained.

Because of the constraints, as far as this points indicates,a closed solution is not possible, leaving this problem as is for a CAS (solver), depending on the actual values of the constants

  • $\begingroup$ I really appreciate for your kindness and taking your time but I wonder why we can't say that $y_{i}$ should be equal from \begin{align} \frac{1}{\lambda^1+\lambda^2py_i^2}\frac{py_i}{1+py_i}=1 \end{align} since the other parameters, i.e. $\lambda^1$, $\lambda^2$ and p is constant. $\endgroup$ – kkimoz Jun 1 '17 at 20:05
  • $\begingroup$ Well we dont know the multipliers yet......... $\endgroup$ – Brethlosze Jun 1 '17 at 20:13
  • $\begingroup$ And your solution trial is feasible but, not optimal (perhaps no, almost sure) $\endgroup$ – Brethlosze Jun 1 '17 at 20:14
  • $\begingroup$ thank you sooooooo much!!! $\endgroup$ – kkimoz Jun 3 '17 at 16:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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