1
$\begingroup$

I want to solve the following optimization problem

$\text{min.}_{x,y}\ \sum_{i=1}^{N} x_i+\sum_{i=1}^{N} y_i$
subject to
$\sum_{i=1}^{N}\log_2(1+a_{i}x_{i}) \geq A$
$\sum_{i=1}^{N} a_{i}y_{i}\geq B$
$x_{i}+y_{i}\leq c_{i}$
$x_{i} \geq0$
$y_{i}\geq 0$
where $(A,B,c_i\text{and}\ a_i) \in \mathbb{R}^{+}$. Knowing that $a_1\geq a_{2} \geq \ldots,\geq a_N$ and assume that $c_1=c_2=\ldots,=c_N$. Note that $a_{i}$ are constants.

The given optimization problem is convex because the objectiveis linear and all the constraints are convex (except the log-function which is concave). The problem I think can be solve using the Lagrange multipliers so the problem will be as follows

$\text{min}_{x_i,y_i,\lambda\geq0,\mu\geq0,\mathbf{\nu}\geq0,\mathbf{\alpha}\geq0,\boldsymbol{\beta}\geq0}~ ~ \mathcal{L}$

where $\mathcal{L}~$ is
$\mathcal{L}=\sum_{i=1}^{N}x_i+\sum_{i=1}^{N}y_i+\lambda(A-\sum_{i=1}^{N}\log_2(1+a_{i}x_{i}))+\mu(B-\sum_{i=1}^{N} a_{i}y_{i})+\nu(x_i+y_i-c_i)-\sum_{i}^{N}\alpha_{i}x_i-\sum_{i}^{N}\beta_{i}y_i$.
What should I do next? do I need to find $\frac{d(\mathcal{L})}{d(x_i)}=0~$ and $\frac{d(\mathcal{L})}{d(y_i)}=0$, If this is the answer, how can I calculate each of $x_i$ and $y_i$?

Any help is highly appreciated.

Thanks

$\endgroup$
1
$\begingroup$

Since it is probable you won't be able to find a closed form solution for the KKT you will have to employ a numerical method.

Those which seems to fit this problem are:

$\endgroup$
  • $\begingroup$ Agreed, this is going to require a numerical solution. $\endgroup$ – Michael Grant Mar 26 '18 at 15:36
  • $\begingroup$ Thank you both for your comments. This means the problem has no analytical solution, right? $\endgroup$ – user841315 Mar 26 '18 at 16:10
  • $\begingroup$ Only by this comment I can see you're optimistic guy :-). $\endgroup$ – Royi Mar 26 '18 at 16:30
  • $\begingroup$ @user841315 yes, that's what we are saying. $\endgroup$ – Michael Grant Mar 26 '18 at 20:38

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.