How to get an analytical solution for this equation set with Abs function in it?

Question

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}

Answer 1

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.