Interior Point Methods with a Gradient Oracle

DOI10.1145/3564246.3585142MaRDI QIDQ6432632zbMATH OpenOpenAlexFDO

Authors Adrian Vladu

Publication date 10 April 2023

Full work available at URL https://doi.org/10.1145/3564246.3585142

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: We provide an interior point method based on quasi-Newton iterations, which only requires first-order access to a strongly self-concordant barrier function. To achieve this, we extend the techniques of Dunagan-Harvey [STOC '07] to maintain a preconditioner, while using only first-order information. We measure the quality of this preconditioner in terms of its relative excentricity to the unknown Hessian matrix, and we generalize these techniques to convex functions with a slowly-changing Hessian. We combine this with an interior point method to show that, given first-order access to an appropriate barrier function for a convex set $K$, we can solve well-conditioned linear optimization problems over $K$ to $varepsilon$ precision in time $widetildeOleft(left(mathcalT+n^{2}ight)sqrtnulogleft(1/varepsilonight)ight)$, where $u$ is the self-concordance parameter of the barrier function, and $mathcalT$ is the time required to make a gradient query. As a consequence we show that: $$ Linear optimization over $n$-dimensional convex sets can be solved in time $widetildeOleft(left(mathcalTn+n^{3}ight)logleft(1/varepsilonight)ight)$. This parallels the running time achieved by state of the art algorithms for cutting plane methods, when replacing separation oracles with first-order oracles for an appropriate barrier function. $$ We can solve semidefinite programs involving $mgeqn$ matrices in $mathbb{R}^{nimesn}$ in time $widetildeOleft(m{n}^4+m^{1.25}{n}^{3.5}logleft(1/varepsilonight)ight)$, improving over the state of the art algorithms, in the case where $m=Omegaleft(n^{frac3.5omega-1.25}ight)$. Along the way we develop a host of tools allowing us to control the evolution of our potential functions, using techniques from matrix analysis and Schur convexity.

This page was built for publication: Interior Point Methods with a Gradient Oracle

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6432632)