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

• 成果类型: Article
• 署名作者: Hinder, Oliver; Ye, Yinyu
• 署名单位: Pennsylvania Commonwealth System of Higher Education (PCSHE); University of Pittsburgh; Stanford University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2020.0274
• 发表日期: 2024
• 页码: 2402-2424
• 关键词: polynomial-time algorithm; interior-point methods; trust-region; Newton method; evaluation complexity; local convergence; implementation; optimization; optimality

摘要

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 mu-approximate Fritz John point by solving O(mu-7=4) trustregion subproblems. For IPMs that handle nonlinear constraints, this result represents the first iteration bound with a polynomial dependence on 1=mu. We also show how to use our method to find scaled-KKT points starting from an infeasible solution and improve on existing complexity bounds.