×

zbMATH — the first resource for mathematics

A globally convergent primal-dual interior-point relaxation method for nonlinear programs. (English) Zbl 1440.90074
Summary: We prove that the classic logarithmic barrier problem is equivalent to a particular logarithmic barrier positive relaxation problem with barrier and scaling parameters. Based on the equivalence, a line-search primal-dual interior-point relaxation method for nonlinear programs is presented. Our method does not require any primal or dual iterates to be interior-points, which has similarity to some warmstarting interior-point methods and is different from most of the globally convergent interior-point methods in the literature. A new logarithmic barrier penalty function dependent on both primal and dual variables is used to prompt the global convergence of the method, where the penalty parameter is adaptively updated. Without assuming any regularity condition, it is proved that our method will either terminate at an approximate KKT point of the original problem, an approximate infeasible stationary point, or an approximate singular stationary point of the original problem. Some preliminary numerical results are reported, including the results for a well-posed problem for which many line-search interior-point methods were demonstrated not to be globally convergent, a feasible problem for which the LICQ and the MFCQ fail to hold at the solution and an infeasible problem, and for some standard test problems of the CUTE collection. Correspondingly, for comparison we also report the numerical results obtained by the interior-point solver IPOPT. These results show that our algorithm is not only efficient for well-posed feasible problems, but is also applicable for some feasible problems without LICQ or MFCQ and some infeasible problems.
MSC:
90C30 Nonlinear programming
90C51 Interior-point methods
90C26 Nonconvex programming, global optimization
Software:
CUTE; CUTEr; ipfilter; Ipopt
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Benson, Hande Y.; Shanno, David F., An exact primal-dual penalty method approach to warmstarting interior-point methods for linear programming, Comput. Optim. Appl., 38, 3, 371-399 (2007) · Zbl 1171.90546
[2] Benson, Hande Y.; Shanno, David F., Interior-point methods for nonconvex nonlinear programming: regularization and warmstarts, Comput. Optim. Appl., 40, 2, 143-189 (2008) · Zbl 1181.90243
[3] BonCGT95 I. Bongartz, A. R. Conn, N. I. M. Gould, and P. L. Toint, CUTE: Constrained and Unconstrained Testing Environment, ACM Tran. Math. Software <span class=”textbf”>2</span>1 (1995), 123-160. · Zbl 0886.65058
[4] Burke, James V.; Curtis, Frank E.; Wang, Hao, A sequential quadratic optimization algorithm with rapid infeasibility detection, SIAM J. Optim., 24, 2, 839-872 (2014) · Zbl 1301.49069
[5] byrd R. H. Byrd, Robust trust-region method for constrained optimization, Paper presented at the SIAM Conference on Optimization, Houston, TX, 1987. · Zbl 0631.65068
[6] Byrd, Richard H.; Curtis, Frank E.; Nocedal, Jorge, Infeasibility detection and SQP methods for nonlinear optimization, SIAM J. Optim., 20, 5, 2281-2299 (2010) · Zbl 1211.90179
[7] Byrd, Richard H.; Gilbert, Jean Charles; Nocedal, Jorge, A trust region method based on interior point techniques for nonlinear programming, Math. Program., 89, 1, Ser. A, 149-185 (2000) · Zbl 1033.90152
[8] Byrd, Richard H.; Hribar, Mary E.; Nocedal, Jorge, An interior point algorithm for large-scale nonlinear programming, SIAM J. Optim., 9, 4, 877-900 (1999) · Zbl 0957.65057
[9] Byrd, Richard H.; Marazzi, Marcelo; Nocedal, Jorge, On the convergence of Newton iterations to non-stationary points, Math. Program., 99, 1, Ser. A, 127-148 (2004) · Zbl 1072.90038
[10] Chen, L.; Goldfarb, D., Interior-point \(l_2\)-penalty methods for nonlinear programming with strong global convergence properties, Math. Program., 108, 1, Ser. A, 1-36 (2006) · Zbl 1142.90498
[11] Curtis, Frank E., A penalty-interior-point algorithm for nonlinear constrained optimization, Math. Program. Comput., 4, 2, 181-209 (2012) · Zbl 1269.49045
[12] DLS17 Y.-H. Dai, X.-W. Liu, and J. Sun, A primal-dual interior-point method capable of rapidly detecting infeasibility for nonlinear programs, J. Ind. Manag. Optim., 2018. DOI 10.3934/jimo.2018190.
[13] EngAnV09 A. Engau, M. F. Anjos and A. Vannelli, A primal-dual slack approach to warmstarting interior-point methods for linear programming, In: Operations Research and Cyber-Infrastructure, J.W. Chinneck, B. Kristjansson, M.J. Saltzman, eds., Springer US, 2009, 195-217.
[14] Forsgren, Anders; Gill, Philip E., Primal-dual interior methods for nonconvex nonlinear programming, SIAM J. Optim., 8, 4, 1132-1152 (1998) · Zbl 0915.90236
[15] Gill, Philip E.; Robinson, Daniel P., A primal-dual augmented Lagrangian, Comput. Optim. Appl., 51, 1, 1-25 (2012) · Zbl 1244.90219
[16] Gould, Nick I. M.; Orban, Dominique; Toint, Philippe L., An Interior-point \(\ell_1\)-penalty Method for Nonlinear Optimization. Numerical analysis and optimization, Springer Proc. Math. Stat. 134, 117-150 (2015), Springer, Cham · Zbl 1330.65085
[17] Hock, Willi; Schittkowski, Klaus, Test Examples for Nonlinear Programming Codes, Lecture Notes in Economics and Mathematical Systems 187, v+177 pp. (1981), Springer-Verlag, Berlin-New York · Zbl 0393.90072
[18] Liu, Xinwei; Sun, Jie, A robust primal-dual interior-point algorithm for nonlinear programs, SIAM J. Optim., 14, 4, 1163-1186 (2004) · Zbl 1079.90160
[19] Liu, Xin-Wei; Yuan, Ya-Xiang, A robust algorithm for optimization with general equality and inequality constraints, SIAM J. Sci. Comput., 22, 2, 517-534 (2000) · Zbl 0972.65038
[20] Liu, Xinwei; Yuan, Yaxiang, A null-space primal-dual interior-point algorithm for nonlinear optimization with nice convergence properties, Math. Program., 125, 1, Ser. A, 163-193 (2010) · Zbl 1205.90272
[21] Nocedal, Jorge; \"Oztoprak, Figen; Waltz, Richard A., An interior point method for nonlinear programming with infeasibility detection capabilities, Optim. Methods Softw., 29, 4, 837-854 (2014) · Zbl 1306.90152
[22] Nocedal, Jorge; Wright, Stephen J., Numerical Optimization, Springer Series in Operations Research, xxii+636 pp. (1999), Springer-Verlag, New York · Zbl 0930.65067
[23] Shanno, David F.; Vanderbei, Robert J., Interior-point methods for nonconvex nonlinear programming: orderings and higher-order methods, Math. Program., 87, 2, Ser. B, 303-316 (2000) · Zbl 1054.90091
[24] Tseng, Paul, Convergent infeasible interior-point trust-region methods for constrained minimization, SIAM J. Optim., 13, 2, 432-469 (2002) · Zbl 1049.90128
[25] Ulbrich, Michael; Ulbrich, Stefan; Vicente, Lu\'\is N., A globally convergent primal-dual interior-point filter method for nonlinear programming, Math. Program., 100, 2, Ser. A, 379-410 (2004) · Zbl 1070.90110
[26] Vanderbei, Robert J.; Shanno, David F., An interior-point algorithm for nonconvex nonlinear programming, Comput. Optim. Appl., 13, 1-3, 231-252 (1999) · Zbl 1040.90564
[27] W\"achter, Andreas; Biegler, Lorenz T., Failure of global convergence for a class of interior point methods for nonlinear programming, Math. Program., 88, 3, Ser. A, 565-574 (2000) · Zbl 0963.65063
[28] W\"achter, Andreas; Biegler, Lorenz T., On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming, Math. Program., 106, 1, Ser. A, 25-57 (2006) · Zbl 1134.90542
[29] Wright, Margaret H., Why a pure primal Newton barrier step may be infeasible?, SIAM J. Optim., 5, 1, 1-12 (1995) · Zbl 0821.65039
[30] Yamashita, Hiroshi, A globally convergent primal-dual interior point method for constrained optimization, Optim. Methods Softw., 10, 2, 443-469 (1998) · Zbl 0946.90110
[31] Yuan, Ya Xiang, On the convergence of a new trust region algorithm, Numer. Math., 70, 4, 515-539 (1995) · Zbl 0828.65062
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.