(280h) Constraint-Based Regularization for Nonlinear Interior Point Solvers

Ill-conditioned nonlinear problems arise in many applications. A well-known example is parameter estimation problems in which highly complex models combined with insufficient measurements usually result in identifiability issues. Solving these types of problems can be a challenging task [1,2].

Line search Newton-based algorithms for constrained nonlinear programs (NLP), such as interior point algorithms, are effective at solving large-scale problems [2-4]. An important characteristic of these solvers is that the step computation relies on the positive definiteness of the reduced Hessian matrix (which is the projection of the Hessian of the Lagrangian onto the null space of the constraint Jacobian) to guarantee that the Newton step provides a descent direction [5,6]. When working with highly nonlinear or intrinsically ill-conditioned problems, regularization strategies can be used to deal with indefinite or semidefinite matrices that are inherent to these problems. Ipopt, for example, uses a simple approach that consists of adding a multiple of the identity matrix to the Hessian of the Lagrangian [7]. Although it ensures the desired descent direction, determining a value for this multiple uses a heuristic that is not guaranteed to work well in practice, and the quality of the step may be poor resulting in an increased number of iterations [6,7].

In this work we propose a constraint regularization approach based on the eigenvalue decomposition of the reduced Hessian. The idea is to remove the ill-conditioning and negative curvature directions from the reduced Hessian by adding new linear constraints to the Karush-Kuhn-Tucker (KKT) system that fix the directions determined by eigenvectors associated with negative and (near) zero eigenvalues. We implemented this strategy in the regularization step of an interior point solver written in Pynumero [8], which is a package designed for developing customized solvers. We followed the methodology presented in [9] to calculate the reduced Hessian by performing a series of backsolves of the KKT system. We show that this approach can improve the quality of the step and decrease the number of iterations. Since the size of the reduced Hessian is equivalent to the degrees of freedom, large-scale NLP problems with relatively small number of degrees of freedom, such as parameter estimation, can benefit from this strategy.

References:

[1] Graciano, J. E., D. F. Mendoza, and Galo AC Le Roux. "Performance comparison of parameter estimation techniques for unidentifiable models." Computers & Chemical Engineering 64 (2014): 24-40.

[2] Zavala, Victor M., and Lorenz T. Biegler. "Large-scale parameter estimation in low-density polyethylene tubular reactors." Industrial & engineering chemistry research 45.23 (2006): 7867-7881.

[3] Biegler, Lorenz T., and Victor M. Zavala. "Large-scale nonlinear programming using IPOPT: An integrating framework for enterprise-wide dynamic optimization." Computers & Chemical Engineering 33.3 (2009): 575-582.

[4] Abdollahi, Javad, and Stevan Dubljevic. "Lipid production optimization and optimal control of heterotrophic microalgae fed-batch bioreactor." Chemical engineering science 84 (2012): 619-627.

[5] Nocedal, Jorge, and Stephen Wright. Numerical optimization. Springer Science & Business Media, 2006.

[6] Chiang, Nai-Yuan, and Victor M. Zavala. "An inertia-free filter line-search algorithm for large-scale nonlinear programming." Computational Optimization and Applications 64.2 (2016): 327-354.

[7] Wächter, Andreas, and Lorenz T. Biegler. "On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming." Mathematical programming 106.1 (2006): 25-57.

[8] Rodriguez, Josde Santiago, et al. PyNumero: Python Numerical Optimization. No. SAND2018-12430C. Sandia National Lab.(SNL-NM), Albuquerque, NM (United States), 2018.

[9] Zavala, Victor M. "Computational strategies for the optimal operation of large-scale chemical processes." Dissertation Abstracts International 69.08 (2008).