0
$\begingroup$

I am trying to solve the following problem:

Find the maximum with regards to each $x_i$ in the following objective function $$ 2\sum_i^N c_i d_i log(x_i) $$

subject to $k$ constraints: $$ \forall k: \sum_i^N c_i f_{ik} x_i = b_k $$

Of course we can write the constraints also as $Ax=b$ where $A$ is $k\times n$ matrix and $b$ is a vector of length $k$.

Here $c_i$ are just some constants that appear both in the objective function and in the constraints. And $d_i$ and $f_{ik}$ are some other constants.

I am not sure where to start at all. Lagrangian multipliers maybe?

What also holds in my case is that $\sum_k f_{ik}=1$ for any $i$. But I am guessing that fact is not necessary to solve the optimization. Also I can say that $b_k=1$ for example if it makes it easier, but again I was hoping for a general solution.

$\endgroup$
0
$\begingroup$

This is only a partial answer:

You can write down the Lagrangian. If $\lambda_j$ is the Lagrange multiplier associated with constraint $j\in\{1,\ldots,k\}$, then the first-order conditions are simply:

$$\frac{2c_id_i}{x_i}=\sum_{j=1}^k \lambda _jc_if_{ij}$$

for each $i\in\{1,\ldots,N\}$.

Thus

$$x_i=\frac{2d_i}{\sum_{j=1}^k \lambda_jf_{ij}}$$

If you substitute this into constraint $s$ you get

$$\sum_{i=1}^N c_if_{is}\frac{2d_i}{\sum_{j=1}^k \lambda_jf_{ij}}=b_s$$

If you had only one constraint, this would be

$$\sum_{i=1}^N c_i\frac{2d_i}{\lambda}=b$$

so that $$\lambda=\frac{2}{b}\sum_{i=1}^N c_id_i$$

and therefore $$x_i=\frac{bd_i}{f_{i}\sum_{m=1}^N c_md_m }.$$

$\endgroup$
10
  • $\begingroup$ I also got as far as $x_i=\frac{2d_i}{\sum_j \lambda_j f_{ij}}$, the problem is precisely finding the $\lambda_j$'s $\endgroup$ – Aleksandar Bojchevski Jul 29 '16 at 19:16
  • $\begingroup$ Have you looked up optimization with additively separable objective function subject to linear constraints? I am not sure you can get a nice explicit solution with more than one constraint, since you have nonlinear equations in $n+k$ variables to solve. $\endgroup$ – smcc Jul 29 '16 at 19:24
  • $\begingroup$ In my case I can pick $b_k$ to be anything I want. I need any constraints for identifiability. So in this case if I pick $b_k=2\sum_i f_{ik}c_id_i$, then when substituting $x_i$ into any of the constraints I get $\frac{2\sum_i f_{ik}c_id_i}{\sum_j\lambda_jf_{ij}}=\frac{2\sum_i f_{ik}c_id_i}{1}$ from where it follows $\sum_j\lambda_jf_{ij}=1$. Or am I missing something? $\endgroup$ – Aleksandar Bojchevski Jul 29 '16 at 20:39
  • $\begingroup$ $2\sum_{i=1}^N \frac{c_id_if_{is}}{\sum_{j=1}^k \lambda_jf_{ij}}\neq \frac{2\sum_{i=1}^N c_id_if_{is}}{\sum_{j=1}^k \lambda_jf_{ij}}$ $\endgroup$ – smcc Jul 29 '16 at 20:59
  • $\begingroup$ That is true. But that also doesn't make sense since the term on the right in the denominator now has $f_{ij}$ but there is no $i$ to be indexed upon. $\endgroup$ – Aleksandar Bojchevski Jul 29 '16 at 21:07

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.