Interior-point methods for nonconvex nonlinear programming: cubic regularization

Hande Benson () and David Shanno

Computational Optimization and Applications, 2014, vol. 58, issue 2, 323-346

Abstract: In this paper, we present a primal-dual interior-point method for solving nonlinear programming problems. It employs a Levenberg-Marquardt (LM) perturbation to the Karush-Kuhn-Tucker (KKT) matrix to handle indefinite Hessians and a line search to obtain sufficient descent at each iteration. We show that the LM perturbation is equivalent to replacing the Newton step by a cubic regularization step with an appropriately chosen regularization parameter. This equivalence allows us to use the favorable theoretical results of Griewank (The modification of Newton’s method for unconstrained optimization by bounding cubic terms, 1981 ), Nesterov and Polyak (Math. Program., Ser. A 108:177–205, 2006 ), Cartis et al. (Math. Program., Ser. A 127:245–295, 2011 ; Math. Program., Ser. A 130:295–319, 2011 ), but its application at every iteration of the algorithm, as proposed by these papers, is computationally expensive. We propose a hybrid method: use a Newton direction with a line search on iterations with positive definite Hessians and a cubic step, found using a sufficiently large LM perturbation to guarantee a steplength of 1, otherwise. Numerical results are provided on a large library of problems to illustrate the robustness and efficiency of the proposed approach on both unconstrained and constrained problems. Copyright Springer Science+Business Media New York 2014

Keywords: Interior-point methods; Nonlinear programming; Cubic regularization; Newton’s method (search for similar items in EconPapers)
Date: 2014
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://hdl.handle.net/10.1007/s10589-013-9626-8 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:coopap:v:58:y:2014:i:2:p:323-346

Ordering information: This journal article can be ordered from
http://www.springer.com/math/journal/10589

DOI: 10.1007/s10589-013-9626-8

Access Statistics for this article

Computational Optimization and Applications is currently edited by William W. Hager

More articles in Computational Optimization and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().