Hi Michael,
Thanks for your interest. In short, Optizelle may work, but there’s a flaw in the algorithm that may cause slow or lack of convergence for that kind of problem.
Specifically, for general nonlinear optimization, there’s a variety of algorithms, but second-order Newton type algorithms tend to be a powerful, general tool. In these algorithms, Newton’s method is applied to the nonlinear equations that require the gradient of the Lagrangian to be zero (optimality) and the residual of the constraints to be zero (feasibility). Now, the problem with this approach is that Newton’s method may not converge if far from the solution, so we need to globalize. In a line-search method, this can be a bit tricky because solving the full Newton system does not guarantee a descent direction without modifying the system. In a trust-region method, solving the full system doesn’t guarantee a solution within the trust-region. In response to this, there are two approaches. Either we modify the full Newton system or we divide the solve into one step toward feasibility and another step toward optimality, which is called a composite step method. Optizelle uses a composite step method. An algorithm like IPOPT works with the overall system directly.
Which method is better is a matter of debate. Personally, I strongly prefer composite step methods because it separates the linear systems for feasibility and optimality, which often have different physics, structure, and scale. It therefore allows some very specialized solution methods and preconditioners for the constraints, which is important for very large mechanics and physics based problems.
This brings us to the interior point method. There are two general approaches to integrating this algorithm with a Newton method. In the first method, the modified complementary slackness condition is solved out of the Newton system. This creates a modification of the gradient and Hessian of the optimality system. This is what both Optizelle and IPOPT do. In the second method, the complementary slackness condition is left in the Newton system, but a slack variable is introduced to the Newton system and the step in the slack variable is scaled by the slack itself. This is what the NITRO algorithm does.
As it turns out, the NITRO approach is really what you want to use with a composite step method, not what Optizelle does. It works well for IPOPT because it is not a composite step method and solves the overall system, so step is handled differently. The reason that Optizelle struggles with this approach is that the step toward feasibility (the quasi-normal step) does not have any information as to where the bound is. This means that it can repeatedly run into the boundary during the feasibility step as well as the during the null-space projection during the optimality step. This is bad and slows down convergence. This does not happen with the NITRO algorithm because the scaling by the slack variable is very clever. Essentially, when the slack variable gets small, it slows down modifications to the step and it makes it less likely that the inequality becomes violated.
When I wrote Optizelle, I didn’t know this and implemented the first approach, which is what the linear SDP solvers did.
Now, algorithmically, this is fixable, but it actually changes how you abstract the algorithm. At the moment, Optizelle combines the algorithms for unconstrained and inequality constrained problems. It also combines the algorithms for equality constrained and fully constrained problems. If one wants to implement the NITRO algorithm, basically, the unconstrained code sits separately from the inequality, equality, and constrained codes. Also, since there’s now always a linear system, especially one that the user did not construct, it makes sense to handle solving the linear system in the default case, which Optizelle doesn’t do.
We have a code that does all of this and more, but it’s not been released. I’d love to and I’ve promised one for years. I’d still like to, but practically it’s been difficult. Essentially, there’s two issues. One, there’s a bunch of algorithmic improvements that should be published ahead of time. Two, our clients don’t exactly pay for us to publish general papers, so I need to expense that cost in overhead. I’m fine with that, but it’s hard to really balance all of this with ongoing work. Honestly, if you know of a friendly editor that wants to publish a sequence of papers that detail this algorithm, please let me know.
Alright, so where this leaves you is: Optizelle is mostly fine for unconstrained, pure equality constrained, and pure inequality constrained problems. It may or may not work for problems with a combination of equality and inequality constraints. If you try the problem and it keeps hitting the boundary during the feasibility step or the nullspace projection, it’s probably going to struggle.
Anyway, hopefully this helps. Let me know if that helps to clarify things and sorry there isn’t an easier answer.
Joe