0
$\begingroup$

I have a nearly linear system which I believe should have a solution (from model intuition and from numerical experimentation using a non-linear solver), but which I am having trouble studying analytically. The system has a form similar to

$$ x_j = min \left \{0; a_j + \sum_{i=1}^N b_i x_i \right \} $$ for all $j$ in $\{1,\dots, N \}$. My first attempt was to try to study the equation ignoring the minimum operator, find a solution, then enforce the minimum after the fact. However, this looks like

$$ \vec{x} = \vec{a} + \vec{1} \otimes \vec{b}^T\vec{x} \hspace{10pt} \Leftrightarrow \hspace{10pt} \left(\mathbb{I} - \vec{1}\otimes \vec{b}^T \right)\vec{x} = \vec{a} $$ where $\vec{1}$ is a column vector of length $N$. However, if $\sum_i b_i=1$ (which is my particular case) this matrix is exactly singular. That being said, even in this case several non-linear solvers seem to converge to the same solution.

Is this logic correct? Do I need to worry about any other cases? Am I missing something about the minimum operator that makes these equations independent? Or is there a more appropriate way to solve this problem?

$\endgroup$
1
  • $\begingroup$ What are the assumptions on the $a_i$ and $b_i$? Are the $b_i$ positive as weights? Are the $a_i$ non-negative? $\endgroup$ May 19, 2017 at 13:03

1 Answer 1

0
$\begingroup$

You can reformulate the problem as $$c = \sum_{i=1}^N b_i\min(0,a_i+c).$$

Now for $c\ge -\min_{i=1,..,N} a_i$ all terms on the right are zero, while for $c\le -\max_{i=1,..,N} a_i$ the right side has the value $$ c+\sum_{i=1}^N b_i a_i $$

Assuming the $b_i$ are non-negative weights, you get that for $c>\max(0, -\min a_i)$ the left side of the equation is larger than the right, while for $c< -\max_{i=1,..,N} a_i$ the opposite is the case, so that in-between both curves intersect exactly once. This can be solved with the bisection or a variant of the regula-falsi method.

If $\min a_i>0$, the intercept is at $c=0$ so that the only solution has all $x_i=0$.

If the $a_i$ are sorted in increasing order, one can also use the partial sums $p_n=\sum_{i=1}^nb_i$, $q_n=\sum_{i=1}^nb_ia_i$ and compute $c_n=\frac{q_n}{1-p_n}$ and test if $-a_{n+1}\le c_n\le -a_n$. Whenever that is true, then one has found the solution $c=c_n$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .