2
$\begingroup$

So I have a collection of systems of equations, basically $n$ systems of equations, each composed of $k$ equations:

$$\frac{a_1x_{1j}}{a_1x_{1j} + \cdots + a_kx_{kj}} + \log x_{1j} + 1 - B_{1j} = 0$$ $$\frac{a_2x_{2j}}{a_1x_{1j} + \cdots + a_kx_{kj}} + \log x_{2j} + 1 - B_{2j} = 0$$ $$\vdots$$ $$\frac{a_kx_{kj}}{a_1x_{1j} + \cdots + a_kx_{kj}} + \log x_{kj} + 1 - B_{kj} = 0$$

for $j = 1,...,n$, with the restriction that each $(x_{1j},...,x_{kj})$ lies on the simplex.

As you can see the systems are all very similar to each other, the only difference being the $B_{ij}$ constant at the end. Also if it helps all the $a_i$ and $B_{ij}$ are positive.

I'm wondering first if these systems are actually simple enough that they have analytic solutions, and if not, then upon finding the solution to one of them (probably by using some sort of constraint-modified Newton's method), whether I can basically use this solution to immediately find the solution to the others.

$\endgroup$
1
$\begingroup$

Notice that, in your problem, these systems are decoupled with each other. To be more precise, the $j$-th system only contains variables $x_{1j},\dots,x_{kj}$. Therefore, you only need to solve each system separately using Newton's method (or using some build-in functions in MATLAB or python).

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Yes I know they're decoupled, but they're so closely related, differing only by the value of the constant $B_{ij}$, that I was hoping that I could solve one and then analytically derive the solution to the others from that first solution, without having to run Newton's method on all $n$ of them. $\endgroup$ – Thoth Jun 22 '16 at 1:38
0
$\begingroup$

Not sure if this would totally solve your problem, but it might be a step.

So lets take your $j^{th}$ system and just frame it as the following:

$$ \textbf{F}(\textbf{x}_j^{*}) - \textbf{B}_j = \textbf{0} $$

Given you find the solution to that, let's look at the $i^{th}$ system:

$$ \textbf{F}(\textbf{x}_i^{*}) - \textbf{B}_i = \textbf{0} $$

Now let's try to relate the $i^{th}$ system to the $j^{th}$ system like so:

$$ \textbf{F}(\textbf{x}_i^{*}) - \textbf{B}_i = \textbf{0} $$ $$ \textbf{F}(\textbf{x}_j^{*} + \Delta \textbf{x}) - (\textbf{B}_j + \Delta_{ij})= \textbf{0} $$

$$ \left(\textbf{F}(\textbf{x}_j^{*}) - \textbf{B}_j\right) + \left( \left.\frac{\partial \textbf{F}}{\partial\textbf{x}}\right|_{\textbf{x}_{j}^{*}}\Delta \textbf{x} - \Delta_{ij} \right)= \textbf{0} $$

The left term goes to zero based on the solution to the $j^{th}$ system. You end up with the equation: $$ \Delta \textbf{x} = \left[\left.\frac{\partial \textbf{F}}{\partial\textbf{x}}\right|_{\textbf{x}_{j}^{*}}\right]^{-1} \Delta_{ij}$$

By solving this equation above, you might be able to quickly get to the solution for the $i^{th}$ equation using knowledge of the $j^{th}$. What's cool about this is you only need to potentially solve the $j^{th}$ equation the hard way and then you could create a factored version of $\left[\left.\frac{\partial \textbf{F}}{\partial\textbf{x}}\right|_{\textbf{x}_{j}^{*}}\right]$ to make the solution of the above equation as efficient as possible for the remaining systems.

One thing to note, however, is you will need to experiment with this since I am unsure how sensitive the solution will be to small changes in the $\textbf{B}$ vector. The above solution should primarily work if the sensitivity to differences in $\textbf{B}$ are small.

| cite | improve this answer | |
$\endgroup$

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.