# Optimization of N variables with K linear equality constraints

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.

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 }.$$

• 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 – Aleksandar Bojchevski Jul 29 '16 at 19:16
• 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. – smcc Jul 29 '16 at 19:24
• 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? – Aleksandar Bojchevski Jul 29 '16 at 20:39
• $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}}$ – smcc Jul 29 '16 at 20:59
• 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. – Aleksandar Bojchevski Jul 29 '16 at 21:07