Solving Algorithm NCL’s Subproblems: The Need for Interior Methods

Algorithm NCL was devised to solve a class of large nonlinearly constrained optimization problems whose constraints do not satisfy LICQ at a solution. It is mathematically equivalent to the augmented Lagrangian algorithm LANCELOT, which solves a short sequence of bound-constrained subproblems BCₖ BC k and has no LICQ difficulties. NCL’s equivalent subproblems NCₖ NC k are much bigger and must be solved by a nonlinear interior method (needing first and second derivatives). We study the KKT-type systems arising within nonlinear interior methods when they are applied to the NCₖ NC k subproblems. We find that the KKT systems can sometimes be reduced to smaller SQD systems (symmetric quasi-definite) and sometimes to even smaller SPD systems (symmetric positive definite). The smaller systems have proved suitable for GPU implementation within the interior solver MadNLP when it is used by MadNCL to implement Algorithm NCL.