0
$\begingroup$

To calculate the solution for the following equation set's unknown variables ${C,V}$

\begin{equation} \begin{aligned} \sum_{i=1}^m Abs[bt_{i} \cdot xt'_{i} - V \cdot bt'_{i}] \cdot c &== C \\ C + V &== \sum_{i=1}^m bt_{i} \cdot xt'_{i} \end{aligned} \end{equation}

For $m = 2$ it's easily solved by Mathematica's Solve function: $\left\{V\to \frac{bt_1 \cdot xt'_1 \left(S_1 \cdot c + 1 \right) + bt_2 \cdot xt'_2 \left(S_2 \cdot c + 1 \right)}{bt'_1 \cdot S_1 \cdot c + bt'_2 \cdot S_2 \cdot c + 1 }\right\}$ and $\left\{ C \to \sum_{i=1}^2 bt_{i} \cdot xt'_{i} - V \right\}$

where $ S_i = \left\{ \begin{array}{lr} 1 & \\ -1 & \end{array} \right. $

But for $m \ge 3$ it took forever for Solve function to give an analytical solution, I waited for 10 mins hoping Mathematica would crack out the solutions before I aborted the evaluation. Eventually I made a guess that the solution for any integer $m$ could be: $\left\{V\to \frac{\sum _{i=1}^m bt_i xt'_i \left(S_i \cdot c + 1 \right)}{\sum _{i=1}^m bt'_i \cdot S_i \cdot c + 1}\right\}$ where $ S_i = \left\{ \begin{array}{lr} 1 & \\ -1 & \end{array} \right. $

This unproved solution seems to make the original equations satisfied with any numeric $bt_i, bt'_i, xt'_i$ and $c$ I throw at it.

But I'm still not sure it is the actual solution, thus questions:

  1. Is there a way to get this equation's analytical solution when $m \ge 3$ ?
  2. If Mathematica can not provide the analytical solution, does it at least provide some function to verify the legitimacy of my guessed solution?
  3. If my guessed solution is indeed the legitimate one, how to determine the sign of $S_i$ ? I know it depends on the relative quantity of $bt_{i} \cdot xt'_{i} $ and $ bt'_{i}$ but still can not figure out a definitive rule about it.

I tried use $S_i = \text{If}\left[bt_i>bt'_i,-1,1\right]$, but it has been proved wrong by some numerical coefficients combinations.

When $m \lt 10$ I can try all $S_i \pm$ combinations to find the non trivial solution, but this approach quickly becomes non-feasible when $m$ is more than that, because of the exponential increase of possible combinations.

Any help on the Math or Mathematica would be appreciated.

I have put the actual Mathematica code in below (Note I don't know how to type prime sign so i used bt2 and xt2 instead):

NSolve[{\!\(
\*UnderoverscriptBox[\(\[Sum]\), \(i = 1\), \(m\)]\(Abs[
\*SubscriptBox[\(bt\), \(i\)]*
\*SubscriptBox[\(xt2\), \(i\)] - V*
\*SubscriptBox[\(bt2\), \(i\)]]*c\)\) == C && C + V == \!\(
\*UnderoverscriptBox[\(\[Sum]\), \(i = 1\), \(m\)]\(
\*SubscriptBox[\(bt\), \(i\)]*
\*SubscriptBox[\(xt2\), \(i\)]\)\)} /. {m -> 3}
$\endgroup$
  • 1
    $\begingroup$ Welcome to Mathematica.SE! I suggest that: 1) You take the introductory Tour now! 2) When you see good questions and answers, vote them up by clicking the gray triangles, because the credibility of the system is based on the reputation gained by users sharing their knowledge. Also, please remember to accept the answer, if any, that solves your problem, by clicking the checkmark sign! 3) As you receive help, try to give it too, by answering questions in your area of expertise. $\endgroup$ – bbgodfrey Apr 6 '15 at 19:43
  • 1
    $\begingroup$ Please, post actual code, not $\LaTeX$ formatted expressions $\endgroup$ – Sektor Apr 6 '15 at 19:47
  • $\begingroup$ Sorry this is my first time asking question on this Mathematica SE site, I have made modification as suggested $\endgroup$ – imadcat Apr 6 '15 at 19:59
  • $\begingroup$ Copy the code as input format please. $\endgroup$ – 2012rcampion Apr 6 '15 at 20:10
2
$\begingroup$

We can start by eliminating $C$ from your equations, as it's trivial to solve for once you have the value of $v$. I'm also going to simplify some of your variable names:

$$ \begin{align} bt_ixt'_i &= a_i \\ bt'_i &= b_i \end{align} $$

Now we simply have:

$$ c \sum_i \left|a_i - vb_i\right| + v = \sum_i a_i $$

Defining $s_i$ as:

$$ s_i = \left\{ \begin{array}{rl} 1 & : a_i - vb_i > 0 \\ -1 & : a_i - vb_i < 0 \end{array} \right. $$

we can rewrite the absolute value as:

$$ c \sum_i s_i\left(a_i - vb_i\right) + v = \sum_i a_i \\ f(v) = c \sum_i s_i a_i - \sum_i a_i - v \left(c \sum_i s_i b_i - 1\right) = 0 $$

Now if we know the $s_i$, we can solve for $v$ explicitly:

$$ v = \frac{c \sum_i s_i a_i - \sum_i a_i}{c \sum_i s_i b_i - 1} = \frac{\sum_i \left(c s_i - 1\right) a_i}{\sum_i cs_i b_i - 1} $$

This matches your solution, with the $s_i$ negated.

We can rewrite $s_i$ to make something a little more clear:

$$ \begin{align} s_i &= \left\{ \begin{array}{rl} 1 & : vb_i < a_i \\ -1 & : vb_i > a_i \end{array} \right. \\ &= \left\{ \begin{array}{rl} 1 & : v < a_i/b_i \oplus b_i < 0 \\ -1 & : v > a_i/b_i \oplus b_i < 0 \end{array} \right. \end{align} $$

We can now see that we don't have to try every combination of the $s_i$, since they will change one by one as $v$ increases. We can now write a simple $\text{O}(n)$ algorithm to find the solution.


The algorithm takes three inputs: two arrays a and b of equal length, and a real number c. Our first step is to sort a and b by a/b:

{a, b} = Transpose[SortBy[Transpose[{a,b}], Divide @@ # &]]

Next, we calculate the breakpoints for v (where the s[[i]] change sign):

vb = {-Infinity} ~Join~ (a/b) ~Join~ {+Infinity}

Now we loop over each interval in vb. For each one we will compute s and solve for v:

m = Length[a]

vi = Table[
  With[{s = Sign[b] Join @@ ConstantArray @@@ {{-1, i}, {1, m - i}} },
   (c s - 1).a/(c s.b - 1)
  ], {i, 0, m}]

Now we select only the vi that are in the proper range:

solns = Pick[vi, Thread[Most[vb] <= vi <= Rest[vb]]]

If you have very large a and b lists, there is a trick that you can use to speed up finding the solutions. Note that the equation $f(v)=0$ is piecewise linear and piecewise continuous. When $v=-\infty$, $s_i$ is just $\text{sign}(b_i)$. This means that all of the linear terms $-v s_i b_i)$ are negative.

As $v$ increases, the signs flip one by one until they are all positive. This means that the slope is always nondecreasing; therefore $f(v)$ is concave up (unless $c$ is negative, in which case it is concave down), and there can be only two solutions. (There is a special case where one segment of the function is colinear with the x-axis, but when a and b are real numbers the probability of this is zero, i.e. it is almost certain not to happen.) You can do a modified binary search to quickly find the two by looking at the sign of the residual to figure out where in the function you are.

$\endgroup$
  • $\begingroup$ Thank you for the elegant numerical solution and nice step by step explanation, couldn't wait to run it on my computer when I'm back! Any thought on the analytical solutions? $\endgroup$ – imadcat Apr 6 '15 at 23:01
  • $\begingroup$ @imadcat This is the analytic solution. Replace every comparison with a piecewise expression and you're good to go. (Ok, I'm only half-joking here. I'll write down the construction for an explicit formula after dinner.) $\endgroup$ – 2012rcampion Apr 6 '15 at 23:04
  • $\begingroup$ @imadcat So my research indicates that there's no closed-form solution for arbitrary $m$ with fewer than $\text{O}(e^n)$ terms. How big are you talking about here? And why do you need a closed-form solution? $\endgroup$ – 2012rcampion Apr 7 '15 at 0:28
  • $\begingroup$ Again thank you for the quick research, $m$ could range from 2 to a few thousands. Before your answer I feared that numerical approach may quickly grow out of computational power limit especially because I have to solve this equation iteratively for coefficients at each time point (can be hundreds to million points). Now I admit that my motivation to search for a closed-form solution might not be practically justified given that you have demonstrated that it's numeric solution is quit surprisingly fast O(n) operation. $\endgroup$ – imadcat Apr 7 '15 at 0:46
  • $\begingroup$ So my naive closed-form solution generated from guessing isn't right even without considering the $S_i$ issue? So far I have only tested $m=2, 3$. It seems to work. I will examine it for $m>3$ and let you know. $\endgroup$ – imadcat Apr 7 '15 at 0:53

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.