Interior Point Methods with a Gradient Oracle

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 ε precision in time O (( T + n 2 )√ n νlog(1/ε)), where ν is the self-concordance parameter of the barrier function, and T is the time required to make a gradient query.

Authors

• Adrian Vladu

Keywords

• interior point methods
• linear systems
• preconditioning