Our current line search approach has several issues:
- Regularization failures due to numerical conditioning
- Symmetric indefinite matrix factorization failures (solvable by implementing LDLT with 2x2 pivoting aka Bunch-Kaufman)
- Poor step directions inherent to line search
- Really small max step lengths caused by the fraction-to-the-boundary rule. This occurs even for simple problems like example 19.2 of "Numerical Optimization":
problem = Problem()
x = problem.decision_variable()
s1 = problem.decision_variable()
s2 = problem.decision_variable()
x.set_value(-2)
s1.set_value(3)
s2.set_value(1)
problem.minimize(x)
problem.subject_to(x**2 - s1 - 1 == 0)
problem.subject_to(x - s2 - 0.5 == 0)
problem.subject_to(s1 >= 0)
problem.subject_to(s2 >= 0)
We can avoid all these issues by using a trust-region approach instead. Section 19.5 of "Numerical Optimization" describes one. Trust-region methods don't need regularization, use projected conjugate gradient instead of LDLT, and don't have bad step directions since that's determined second.
This would replace the current line search IPM and SQP solvers. Once the new IPM solver is done, we could strip it down for problems without inequality constraints, like how the current SQP solver is a simpler version of the current IPM solver.
Our current line search approach has several issues:
We can avoid all these issues by using a trust-region approach instead. Section 19.5 of "Numerical Optimization" describes one. Trust-region methods don't need regularization, use projected conjugate gradient instead of LDLT, and don't have bad step directions since that's determined second.
This would replace the current line search IPM and SQP solvers. Once the new IPM solver is done, we could strip it down for problems without inequality constraints, like how the current SQP solver is a simpler version of the current IPM solver.