384004 Structured Regularization for Degenerate Models in Primal-Dual Interior Point Method

Wednesday, November 19, 2014: 8:51 AM
406 - 407 (Hilton Atlanta)
Wei Wan, Chemical Engineering, Carnegie Mellon Univeristy, Pittsburgh, PA and Lorenz T. Biegler, Chemical Engineering, Carnegie Mellon University, Pittsburgh, PA

Nonlinear programing (NLP) is an essential tool for formulating large-scale mathematical models of chemical engineering processes. Active set methods and interior point methods are both popular strategies for solving NLP problems. The active set method involves the combinatorial complexity of identifying the active constraints and therefore avoids the influence of inactive dependent constraints. However, identifying the active constraints slows down the algorithm for large-scale problems especially when there are many degrees of freedom. Alternatively, interior point methods introduce a barrier parameter  and add a penalty term to the objective function for the inequality constraints resulting in cheaper iterations with newton steps. The high performance of the interior point method makes it widely used for NLP problems. However, interior point methods require certain regularity conditions for the solution path to exist. Dependent constraints, both equalities and inequalities, are common in chemical processes and violate the regularity conditions which may cause the interior point method to fail.

Material flow equations for multicomponent streams exist widely in chemical process models. When composition is unknown, the mass balance equations involve bilinear terms. In addition, synthesis or design MINLP problems derive NLP subproblem relaxations with the input flow rate vanishing when the corresponding unit is unselected. In that case, bilinear terms lead to local dependence in the equations at optima, which violate Linear Independent Constraints Qualification (LICQ) and make Lagrange multipliers undefined in the Karush-Kuhn-Tucker (KKT) matrix. The interior point solver IPOPT introduces regularization terms to fix the KKT matrix, however in some cases the required regularization terms are too large and the solver will fail. Moreover, inequality constrained problems in process optimization frequently violate constraint qualifications (such as LICQ and the Mangasarian-Fromovitz Constraint Qualification  (MFCQ)), and therefore lead to unbounded multipliers. For instance, semi-definite programming problems that are reformulated as NLPs lead to inequalities that can violate the MFCQ. In the NLP solver, this leads to unbounded multipliers, which causes the Lagrange Hessian to blow up.

To deal with these challenges, we present a new regularization algorithm, which uses ideas from active set methods, and identify an independent subset of active constraints. For interior point methods, this is achieved by adding big-M terms in dependent rows that essentially eliminate dependent constraints. This results in more accurate Newton steps and faster convergence to a solution. Numerical experiments on hundreds of modified examples from comprehensive test sets are implemented in the C++ version of IPOPT with linear solver HSL_MA57, HSL_MA97 and MUMPS. The test results show the effectiveness of the new algorithm with average reduction of more than 50% of the iterations. Moreover, several large-scale nonlinear blending problems and semi-definite optimization problems are solved with the proposed algorithm and the improvements over existing regularization are demonstrated.

Extended Abstract: File Not Uploaded
See more of this Session: Advances in Optimization I
See more of this Group/Topical: Computing and Systems Technology Division