A polynomial time log barrier method for problems with nonconvex constraints
share
Interior point methods (IPMs) that handle nonconvex constraints such as IPOPT, KNITRO and LOQO have had enormous practical success. Unfortunately, all known analyses of log barrier methods with general constraints (implicitly) prove guarantees with exponential dependencies on 1/μ where μ is the barrier penalty parameter. This paper provides an IPM that finds a μ-approximate Fritz John point in O( μ^-7/4) iterations when the objective and constraints have Lipschitz first and second derivatives. For this setup, the results represent both the first polynomial time dependence on 1/μ for a log barrier method and the best-known guarantee for finding Fritz John points. We also show that, given convexity and regularity conditions, our algorithm finds an ϵ-optimal point in at most O(ϵ^-2/3) iterations. The algorithm that we study in this paper, although naive, provides inspiration for our practical one-phase IPM.
READ FULL TEXT