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
    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$ 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
    Jan 20, 2017 at 5:44
  • 1
    $\begingroup$ @AbhishekHalder Since the rational equation has poles, it is easier to bracket the roots. $\endgroup$ 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
    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
    Mar 23, 2018 at 1:58
  • 1
    $\begingroup$ FPI stands for fixed-point iteration? $\endgroup$ Mar 23, 2018 at 6:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.