The spectral barrier method to solve analytic convex optimization problems in function spaces

Abstract Spectral methods approximate the solutions of variational problems, boundary value problems and partial differential equations with high degree polynomials. Such methods are especially well-suited to problems where the solution is holomorphic. We focus on convex optimization problems such as the p -Laplacian, which has long been considered hard to solve. We solve these problems by the barrier method. Theoretically, the barrier method requires the use of “short t -steps.” Our new spectral barrier (SPB) method uses “long t -steps.” By computing these long steps on progressively higher degree polynomial spaces, we ensure that the overall method converges to a tolerance $${\mathop {\textrm{tol}}\limits }&gt;0$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mtext>tol</mml:mtext> <mml:mo>&gt;</mml:mo> <mml:mn>0</mml:mn> </mml:mrow> </mml:math> in $$\hat{O}(\log {\mathop {\textrm{tol}}\limits }^{-1})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mover> <mml:mi>O</mml:mi> <mml:mo>^</mml:mo> </mml:mover> <mml:mrow> <mml:mo>(</mml:mo> <mml:mo>log</mml:mo> <mml:msup> <mml:mrow> <mml:mtext>tol</mml:mtext> </mml:mrow> <mml:mrow> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> Newton iterations, where the hat indicates that we neglect very slow growing functions like $$\log \log $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>log</mml:mo> <mml:mo>log</mml:mo> </mml:mrow> </mml:math> and $$\log ^*$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mo>log</mml:mo> <mml:mo>∗</mml:mo> </mml:msup> </mml:math> , and provided the problem is reverse Hölder regular. We confirm this theoretical performance estimate with numerical experiments.