3
$\begingroup$

Is anything in general known about the positive root $x_{+}$ of the following polynomial of degree $(n+1)$, as a function of the coefficients $\alpha_{1}, \alpha_{2}, ..., \alpha_{n} > 0$:

$$\displaystyle\sum_{i=1}^{n}\left(1 - x^{2}\alpha_{i}\right)\prod_{j=1\\j\neq i}^{n}\left(1 + x\alpha_{j}\right) = 0.$$

Is this polynomial well-known? At this point, I know that $x_{+}$ is unique, but would like to know its dependence on $\alpha_{i}>0, i=1,...,n$.

Of course, I can employ root-finding algorithms, but currently my focus is understanding the qualitative nature of $x_{+}$. I could not even tackle $n=2$ case.

Please tag as appropriate.

$\endgroup$
2
  • 1
    $\begingroup$ How do you know it is unique? $\endgroup$
    – Igor Rivin
    Commented Jan 20, 2017 at 3:00
  • 5
    $\begingroup$ I know it two ways. First: the above polynomial is the first order optimality condition for a convex optimization problem over $x>0$. Second: if you break down the products in the above polynomial and use the fact that $\alpha_{i}>0$, then you will see that the only change in sign occurs from the $x^n$ term to the $x^{n-1}$th term. Then by Descartes' rule of sign, the number of positive roots is exactly one. $\endgroup$ Commented Jan 20, 2017 at 3:24

1 Answer 1

4
$\begingroup$

Not a full answer, but some comments and an algorithm that the OP may find relevant.

Assuming $x \not= -1/\alpha_1,\ldots,-1/\alpha_n$, we can rewrite the equation as \begin{equation*} \prod_j (1+x\alpha_j)\sum_i \frac{(1-x^2\alpha_i)}{1+x\alpha_i} = 0. \end{equation*} Under our assumption, this further simplifies to the OP's older equation: \begin{equation*} f(x) := \sum_i \frac{1-x^2\alpha_i}{1+x\alpha_i}=0. \end{equation*} Perhaps at this point, you could try to: (i) bracket the root, obtaining points $a<x^*<b$ such that $f(a)<0$, $f(x^*)=0$ and $f(b)>0$, where the bounds are reasonable functions of the $\alpha_i$; (ii) run (by hand) an iteration or two of Newton's method to get an approximate $x^*$ (seems hard); (iii) try Lagrange inversion; or (iv) try a fixed-point iteration.


Example of (iv). Rewrite the equation as follows \begin{equation*} x^2\sum_i \frac{\alpha_i}{1+x \alpha_i} = \sum_i \frac{1}{1+x\alpha_i}. \end{equation*} Using the notation $a(x)=\sum_i \alpha_i/(1+x \alpha_i)$ and $b(x)=\sum_i 1/(1+x \alpha_i)$, we then solve for $x$ by running the iteration \begin{equation*} x_{k+1} = [b(x_k)/a(x_k)]^{1/2},\quad k=0,1,\ldots. \end{equation*} An experiment suggests that started from $x_0=0$, this iteration monotonically increases $x$ (some calculation required, but one can show this easily). Since $b(x)/a(x)$ is bounded above, the sequence $(x_k)$ must converge. Using a couple of steps of this iteration, one can get a "reasonable" approximation to the the desired solution $x^*$ (this seems to converge quite fast, so could be a reasonable method to solve for $x$ numerically too).


EDIT: It seems that this Fixed-Point Iteration (FPI) is used in the preprint authored by the OP (albeit, without attribution)!

EDIT 2: Meanwhile (as noted in the comments below) the OP has fixed the attribution; please check the link the his comment for the latest version.

$\endgroup$
14
  • 1
    $\begingroup$ Not really; I just wrote it back in this form as it seems more amenable to points (i) and (iii) above. $\endgroup$
    – Suvrit
    Commented Jan 20, 2017 at 5:44
  • 1
    $\begingroup$ @AbhishekHalder Since the rational equation has poles, it is easier to bracket the roots. $\endgroup$ Commented Jan 20, 2017 at 7:38
  • 1
    $\begingroup$ If I recall correctly, you can directly show it by choosing $x < y$ and computing $b(x)/a(x)- b(y)/a(y)$, which is rather close of course to computing derivatives. $\endgroup$
    – Suvrit
    Commented Aug 30, 2017 at 1:04
  • 2
    $\begingroup$ @AbhishekHalder I saw that you wrote a preprint arxiv.org/pdf/1803.08157.pdf which seems to use the above FPI, but your preprint contains no link to MO nor any acknowledgment? am I missing something? $\endgroup$
    – Suvrit
    Commented Mar 23, 2018 at 1:58
  • 1
    $\begingroup$ FPI stands for fixed-point iteration? $\endgroup$ Commented Mar 23, 2018 at 6:20

You must log in to answer this question.

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