Inertia-Free Curvature Test

contributed by Nai-Yuan Chiang24 and Victor M. Zavala Tejeda25


In a filter line-search setting it is necessary to detect the presence of negative curvature and to regularize the Hessian of the Lagrangian when such is present. Regularization ensures that the computed step is a descent direction for the objective function when the constraint violation is sufficiently small, which in turn is necessary to guarantee global convergence.

To detect the presence of negative curvature, the default method implemented in IPOPT requires inertia information of the augmented system. The inertia of the augmented system is the number of positive, negative, and zero eigenvalues. Inertia is currently estimated using symmetric indefinite factorization routines implemented in powerful packages such as MA27, MA57, or Pardiso. When more general linear algebra strategies/packages are used (e.g., iterative, parallel decomposition), however, inertia information is difficult (if not impossible) to obtain.

In [14], we present acceptance tests for the search step that do not require inertia information of the linear system and prove that such tests are sufficient to ensure global convergence. Similar tests were proposed in the exact penalty framework reported in [2]. The inertia-free approach also enables the use of a wider range of linear algebra strategies and packages. We have performed significant benchmarks and found satisfactory performance compared to the inertia-based counterpart. Moreover, we have found that this test can yield significant improvements in computing time because it provides more flexibility to accept steps. This flexibility is particularly beneficial in problems that are inherently ill-conditioned and require significant amounts of regularization.

The inertia-free capability implemented in IPOPT is controlled by the options neg_curv_test_tol and neg_curv_test_reg.



Footnotes

... Chiang24
Argonne National Laboratory, http://www.mcs.anl.gov/~nychiang/
... Tejeda25
University of Wisconsin-Madison, http://zavalab.engr.wisc.edu/