Worst-Case Iteration Bounds for Log Barrier Methods on Problems with Nonconvex Constraints

Oliver Hinder () and Yinyu Ye ()
Additional contact information
Oliver Hinder: Industrial Engineering, University of Pittsburgh, Pittsburgh, Pennsylvania 15260
Yinyu Ye: Department of Management Science and Engineering, Stanford University, Stanford, California 94305

Mathematics of Operations Research, 2024, vol. 49, issue 4, 2402-2424

Abstract: Interior point methods (IPMs) that handle nonconvex constraints such as IPOPT, KNITRO and LOQO have had enormous practical success. We consider IPMs in the setting where the objective and constraints are thrice differentiable, and have Lipschitz first and second derivatives on the feasible region. We provide an IPM that, starting from a strictly feasible point, finds a μ -approximate Fritz John point by solving O ( μ − 7 / 4 ) trust-region subproblems. For IPMs that handle nonlinear constraints, this result represents the first iteration bound with a polynomial dependence on 1 / μ . We also show how to use our method to find scaled-KKT points starting from an infeasible solution and improve on existing complexity bounds.

Keywords: 90C30; 90C60; nonlinear optimization; nonconvex optimization; interior point methods; Fritz John conditions (search for similar items in EconPapers)
Date: 2024
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2020.0274 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:49:y:2024:i:4:p:2402-2424

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().