Worst-Case Iteration Bounds for Log Barrier Methods on Problems with Nonconvex Constraints
针对目标函数和约束三阶可导且Lipschitz连续的非凸问题，提出一种内点法，从严格可行点出发，通过求解多项式个信赖域子问题找到近似Fritz John点，首次给出多项式迭代界。
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 [Formula: see text] trust-region subproblems. For IPMs that handle nonlinear constraints, this result represents the first iteration bound with a polynomial dependence on [Formula: see text]. We also show how to use our method to find scaled-KKT points starting from an infeasible solution and improve on existing complexity bounds. Funding: This work was supported by Air Force Office of Scientific Research [9550-23-1-0242]. A significant portion of this work was done at Stanford where O. Hinder was supported by the PACCAR, Inc., Stanford Graduate Fellowship and the Dantzig-Lieberman fellowship.