<p>Given a univariate polynomial of the form <span class="math-container">$p(x) = \prod_{i}{(x*a_i + b_i)}$</span> when all of the <span class="math-container">$a_i$</span> and <span class="math-container">$b_i$</span> are numbers in the range [-1,1] and <span class="math-container">$i$</span> goes from <span class="math-container">$0$</span> to <span class="math-container">$N$</span>.</p>
<p>What is the complexity of optimizing the polynomial (finding the maximum) with the constraint that <span class="math-container">$x$</span> is in the range of [0,1] (optimizing - getting some input that is <span class="math-container">$\epsilon$</span> close to the global maximum)?
Is there a solution that guarantees convergence to a global maximum?
Is it NP-hard?</p>
<p>Generally I could not find discussions about the complexity and hardness of optimizing a polynomial as a function of the degree of the polynomial (in my case <span class="math-container">$N$</span>), only as a function of the number of variables (e.g - <a href="https://link.springer.com/article/10.1007/BF01585569" rel="nofollow noreferrer">https://link.springer.com/article/10.1007/BF01585569</a>).</p>
<p>Thanks!</p>

CC BY-SA 4.0
2023-08-27T20:12:51.757Z
Under the stated conditions, $f$ is increasing on $[0,1]$, hence it attains maximum at $x=1$. So the computational complexity is trivial.
Emil Jeřábek
CC BY-SA 4.0
2023-08-28T15:38:16.813Z
Oh oops, thanks! will fix the error (a and b are not necessarily positive)
Amit Bergman
CC BY-SA 4.0
2023-08-28T16:27:34.147Z
The only potential issue here will be one of the numerical accuracy needed, as there is no exponential search space as for multivariate polys. Compute the derivatives of $p$, find its roots, and for any that are in the range [0,1], compute the value of p at those roots and take the max. Computing roots (to within a given range) can be done efficiently, e.g.: https://doi.org/10.1006/jsco.2002.0531
Joshua Grochow
CC BY-SA 4.0
2023-08-28T16:29:21.437Z
Which raises the question of what problem exactly you want to solve. Do you want max{p(x) : x in [0,1]} or the argmax? And also what kind of complexity bounds you are hoping for.
Joshua Grochow
CC BY-SA 4.0
2023-08-28T20:51:15.110Z
To find argmax (for arbitrary univariate polynomial $p$): observe that the elements of $S=\{p(x):p'(x)=0\}$ are roots of the resultant $q(x)=\mathrm{res}_y(p'(y),p(y)-x)$. Applying to $p'$ and $q$ some sort of a root separation bound, you can compute in polynomial time an $\epsilon>0$ such that distinct elements of $S$ and distinct roots of $p'$ are at least distance $\epsilon$ apart. Compute approximations to the roots $x$ of $p'$ accurate enough so that $x$ and $p(x)$ are determined within $\epsilon/3$. Fix the approximate root $x_0$ that gives the maximal $p(x)$. ...
Emil Jeřábek
CC BY-SA 4.0
2023-08-28T20:53:30.790Z
... Then the unique root of $p'$ within distance $\epsilon/3$ from $x_0$ is a true argmax, and you can approximate it to any given precision in polynomial time. (I’m kind of ignoring the endpoints of the interval; you have to check them as well.)
Emil Jeřábek
CC BY-SA 4.0
2023-08-28T21:21:01.943Z
Got it, thanks! I think my issue was that I was not aware that you can efficiently find all roots of polynomial. Is there a guarantee on convergence of the root finding algorithms?
Amit Bergman
CC BY-SA 4.0
2023-08-29T07:48:55.457Z
What exactly do you mean by “guarantee on convergence”? Given a rational polynomial $p$ and a parameter $n$ in unary, you can compute in polynomial time a list of rational approximations of all real roots of $p$ within additive error $2^{-n}$. Using a root separation bound, you can make sure the $i$th element of the list approximates the $i$th root of $p$ in the usual order.
Emil Jeřábek
CC BY-SA 4.0
2023-08-29T09:58:39.490Z
Let me add that while there are various more sophisticated and more efficient methods, here is a very simple polynomial-time root finding  algorithm that obviously works: (1) Compute the Sturm sequence for $p$ so that you can subsequently determine the number of roots in any given interval. (2) Using Cauchy's bound or the like, fix an interval that contains all roots. (3) Keep splitting the interval in halves until you identify isolating intervals for each root. (4) Continue halving the intervals until you get within the target precision.
Emil Jeřábek
CC BY-SA 4.0
2023-08-29T12:29:57.857Z
(It’s not clear that a naïvely defined Sturm sequence is computable in polynomial time, as one needs polynomial bounds on the height of the coefficients. See e.g. Yap’s *Fundamental problems in algorithmic algebra* for how this can be done properly.)
Emil Jeřábek
<np-hardness><polynomials>
Hardness of maximization of a univariate polynomial (as a function of its degree)
Amit Bergman
# Hardness of maximization of a univariate polynomial (as a function of its degree)

(Asked by: username_0 on 2023-08-27)

Given a univariate polynomial of the form $p(x) = \prod\_{i}{(x\*a\_i + b\_i)}$ when all of the $a\_i$ and $b\_i$ are numbers in the range [-1,1] and $i$ goes from $0$ to $N$.

What is the complexity of optimizing the polynomial (finding the maximum) with the constraint that $x$ is in the range of [0,1] (optimizing - getting some input that is $\epsilon$ close to the global maximum)?
Is there a solution that guarantees convergence to a global maximum?
Is it NP-hard?

Generally I could not find discussions about the complexity and hardness of optimizing a polynomial as a function of the degree of the polynomial (in my case $N$), only as a function of the number of variables (e.g - <https://link.springer.com/article/10.1007/BF01585569>).

Thanks!

**Tags:** np-hardness, polynomials

> **Comments:**
> **username_1**: Under the stated conditions, $f$ is increasing on $[0,1]$, hence it attains maximum at $x=1$. So the computational complexity is trivial.  
> **username_0**: Oh oops, thanks! will fix the error (a and b are not necessarily positive)  
> **username_2**: The only potential issue here will be one of the numerical accuracy needed, as there is no exponential search space as for multivariate polys. Compute the derivatives of $p$, find its roots, and for any that are in the range [0,1], compute the value of p at those roots and take the max. Computing roots (to within a given range) can be done efficiently, e.g.: https://doi.org/10.1006/jsco.2002.0531  
> **username_2**: Which raises the question of what problem exactly you want to solve. Do you want max{p(x) : x in [0,1]} or the argmax? And also what kind of complexity bounds you are hoping for.  
> **username_1**: To find argmax (for arbitrary univariate polynomial $p$): observe that the elements of $S=\{p(x):p'(x)=0\}$ are roots of the resultant $q(x)=\mathrm{res}_y(p'(y),p(y)-x)$. Applying to $p'$ and $q$ some sort of a root separation bound, you can compute in polynomial time an $\epsilon>0$ such that distinct elements of $S$ and distinct roots of $p'$ are at least distance $\epsilon$ apart. Compute approximations to the roots $x$ of $p'$ accurate enough so that $x$ and $p(x)$ are determined within $\epsilon/3$. Fix the approximate root $x_0$ that gives the maximal $p(x)$. ...  
> **username_1**: ... Then the unique root of $p'$ within distance $\epsilon/3$ from $x_0$ is a true argmax, and you can approximate it to any given precision in polynomial time. (I’m kind of ignoring the endpoints of the interval; you have to check them as well.)  
> **username_0**: Got it, thanks! I think my issue was that I was not aware that you can efficiently find all roots of polynomial. Is there a guarantee on convergence of the root finding algorithms?  
> **username_1**: What exactly do you mean by “guarantee on convergence”? Given a rational polynomial $p$ and a parameter $n$ in unary, you can compute in polynomial time a list of rational approximations of all real roots of $p$ within additive error $2^{-n}$. Using a root separation bound, you can make sure the $i$th element of the list approximates the $i$th root of $p$ in the usual order.  
> **username_1**: Let me add that while there are various more sophisticated and more efficient methods, here is a very simple polynomial-time root finding  algorithm that obviously works: (1) Compute the Sturm sequence for $p$ so that you can subsequently determine the number of roots in any given interval. (2) Using Cauchy's bound or the like, fix an interval that contains all roots. (3) Keep splitting the interval in halves until you identify isolating intervals for each root. (4) Continue halving the intervals until you get within the target precision.  
> **username_1**: (It’s not clear that a naïvely defined Sturm sequence is computable in polynomial time, as one needs polynomial bounds on the height of the coefficients. See e.g. Yap’s *Fundamental problems in algorithmic algebra* for how this can be done properly.)  

---

## 0 answers

