3. Trust Region SQP method

Along this week I intend to implement the Byrd-Omojokun Trust-Region SQP method (Algorithm 18.4 from [1]).

This SQP method (which is another substep of the more general interior point method) solve the equality-constrained nonlinear programming problem:

min f(x)

subject to: c(x) = 0

for which f(x) and c(x) are nonlinear functions.

In order to do so, at each substep it solve the trust-region equality-constrained QP problem:

min 1/2 x.T H x + g.T x
subject to:   A x - b = 0
               ||x|| <= delta
                lb <= x <= ub

for which:

• H is the Hessian of the Lagrangian;
• g is the objective function gradient;
• A is the Jacobian matrix of the constraints;
• b is the constraint, all evaluated at the given point.

The implementation will be based in [1], pp.547-549, and in [2]:

• Theoretical revision
• Read sections 18.1-18.5 from Nocedal and Wrigth book [1].
• Read paper [2];
• Write blog post about the method.
• Implementation
• Implement variation of Byrd-Omojokun Trust-Region SQP (description in [1] p.549).
  • Implement function for computing least-squares Lagrange multipliers (description in [2] p. 883);
  • Solve QP subproblem using previously implemented functions;
  • Implement scheme for choosing penalty parameter of merit function (description in [2] p. 891);
  • Compute reduction ratio (description in [2] p. 892);
  • Implement trust-region logic (description in [2] p. 892);
  • Second order corrections schemes (description in [2] p. 892);
• Debug
• Find why optimality is not so low as the reported result from KNITRO;
• Testing
• Unittest;
  • ELEC;
  • Example 15.4 from Nocedal/Wright book.
• Test on problems from CUTEst.
  • ELEC.
  • CHANNEL.
  • ORTHREGA.
  • ORTHREGC.
  • ORTHREGD.
  • HAGER2.
  • HAGER3.
  • DTOC1ND.
  • DTOC2.
  • DTOC3.
  • DTOC4.
  • DTOC5.
  • DTOC6.
  • EIGENA2.
  • EIGENC2.
  • ARTIF.
  • BRATU3D.

References

[1]   Nocedal, Jorge, and Stephen J. Wright. "Numerical optimization" Second Edition (2006).

[2]    Byrd, Richard H., Mary E. Hribar, and Jorge Nocedal. "An interior point algorithm for large-scale nonlinear programming." SIAM Journal on Optimization 9.4 (1999): 877-900.