← All problems

Polynomial spectral-radius lower-bound conjecture for p-CLI methods

12 years old · traced to

Let 0<μ<L0<\mu<L, and let a(z)a(z) and b(z)b(z) be polynomials of degree at most p−1p-1 satisfying b(1)=1b(1)=1. For a polynomial, let ρ\rho denote the maximum modulus of its roots. Write

Q=Lμ.Q=\frac{L}{\mu}.

Polynomial lower-bound conjecture. There exists η∈[μ,L]\eta\in[\mu,L] such that

ρ(zp−(ηa(z)+b(z)))≥L/μ−1L/μ+1.\rho\bigl(z^p-(\eta a(z)+b(z))\bigr)\geq\frac{\sqrt{L/\mu}-1}{\sqrt{L/\mu}+1}.

This is presented as a reduction of the algorithmic conjecture to a question about polynomials, so it expresses the same proposed obstruction in purely analytic terms. The source gives no evidence that it has been resolved.

References
  1. Yossi Arjevani, “On Lower and Upper Bounds in Smooth Strongly Convex Optimization - A Unified Approach via Linear Iterative Methods”, arXiv:1410.6387 (2014).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.