# non-linear optimization problem with constraints with several constraints

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??

thanks!

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

• 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. – kkimoz Jun 1 '17 at 20:05
• Well we dont know the multipliers yet......... – Brethlosze Jun 1 '17 at 20:13
• And your solution trial is feasible but, not optimal (perhaps no, almost sure) – Brethlosze Jun 1 '17 at 20:14
• thank you sooooooo much!!! – kkimoz Jun 3 '17 at 16:03