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

Abstract 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 $$\text {BC}_k$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mtext>BC</mml:mtext> <mml:mi>k</mml:mi> </mml:msub> </mml:math> and has no LICQ difficulties. NCL’s equivalent subproblems $$\text {NC}_k$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mtext>NC</mml:mtext> <mml:mi>k</mml:mi> </mml:msub> </mml:math> 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 $$\text {NC}_k$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mtext>NC</mml:mtext> <mml:mi>k</mml:mi> </mml:msub> </mml:math> 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.