A globally convergent primal-dual interior-point relaxation method for nonlinear programs

Liu, Xin-Wei; Dai, Yu-Hong

doi:10.1090/mcom/3487

A globally convergent primal-dual interior-point relaxation method for nonlinear programs
HTML articles powered by AMS MathViewer

by Xin-Wei Liu and Yu-Hong Dai HTML | PDF

Math. Comp. 89 (2020), 1301-1329 Request permission

Abstract:

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.

References

Hande Y. Benson and David F. Shanno, An exact primal-dual penalty method approach to warmstarting interior-point methods for linear programming, Comput. Optim. Appl. 38 (2007), no. 3, 371–399. MR 2354201, DOI 10.1007/s10589-007-9048-6
Hande Y. Benson and David F. Shanno, Interior-point methods for nonconvex nonlinear programming: regularization and warmstarts, Comput. Optim. Appl. 40 (2008), no. 2, 143–189. MR 2390823, DOI 10.1007/s10589-007-9089-x
I. Bongartz, A. R. Conn, N. I. M. Gould, and P. L. Toint, CUTE: Constrained and Unconstrained Testing Environment, ACM Tran. Math. Software 21 (1995), 123–160.
James V. Burke, Frank E. Curtis, and Hao Wang, A sequential quadratic optimization algorithm with rapid infeasibility detection, SIAM J. Optim. 24 (2014), no. 2, 839–872. MR 3215068, DOI 10.1137/120880045
R. H. Byrd, Robust trust-region method for constrained optimization, Paper presented at the SIAM Conference on Optimization, Houston, TX, 1987.
Richard H. Byrd, Frank E. Curtis, and Jorge Nocedal, Infeasibility detection and SQP methods for nonlinear optimization, SIAM J. Optim. 20 (2010), no. 5, 2281–2299. MR 2650848, DOI 10.1137/080738222
Richard H. Byrd, Jean Charles Gilbert, and Jorge Nocedal, A trust region method based on interior point techniques for nonlinear programming, Math. Program. 89 (2000), no. 1, Ser. A, 149–185. MR 1795061, DOI 10.1007/PL00011391
Richard H. Byrd, Mary E. Hribar, and Jorge Nocedal, An interior point algorithm for large-scale nonlinear programming, SIAM J. Optim. 9 (1999), no. 4, 877–900. Dedicated to John E. Dennis, Jr., on his 60th birthday. MR 1724768, DOI 10.1137/S1052623497325107
Richard H. Byrd, Marcelo Marazzi, and Jorge Nocedal, On the convergence of Newton iterations to non-stationary points, Math. Program. 99 (2004), no. 1, Ser. A, 127–148. MR 2031780, DOI 10.1007/s10107-003-0376-8
L. Chen and D. Goldfarb, Interior-point $l_2$-penalty methods for nonlinear programming with strong global convergence properties, Math. Program. 108 (2006), no. 1, Ser. A, 1–36. MR 2229450, DOI 10.1007/s10107-005-0701-5
Frank E. Curtis, A penalty-interior-point algorithm for nonlinear constrained optimization, Math. Program. Comput. 4 (2012), no. 2, 181–209. MR 2934972, DOI 10.1007/s12532-012-0041-4
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.
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.
Anders Forsgren and Philip E. Gill, Primal-dual interior methods for nonconvex nonlinear programming, SIAM J. Optim. 8 (1998), no. 4, 1132–1152. MR 1646122, DOI 10.1137/S1052623496305560
Philip E. Gill and Daniel P. Robinson, A primal-dual augmented Lagrangian, Comput. Optim. Appl. 51 (2012), no. 1, 1–25. MR 2872489, DOI 10.1007/s10589-010-9339-1
Nick I. M. Gould, Dominique Orban, and Philippe L. Toint, An interior-point $\ell _1$-penalty method for nonlinear optimization, Numerical analysis and optimization, Springer Proc. Math. Stat., vol. 134, Springer, Cham, 2015, pp. 117–150. MR 3446845, DOI 10.1007/978-3-319-17689-5_{6}
Willi Hock and Klaus Schittkowski, Test examples for nonlinear programming codes, Lecture Notes in Economics and Mathematical Systems, vol. 187, Springer-Verlag, Berlin-New York, 1981. MR 611512, DOI 10.1007/BF00934594
Xinwei Liu and Jie Sun, A robust primal-dual interior-point algorithm for nonlinear programs, SIAM J. Optim. 14 (2004), no. 4, 1163–1186. MR 2112969, DOI 10.1137/S1052623402400641
Xin-Wei Liu and Ya-Xiang Yuan, A robust algorithm for optimization with general equality and inequality constraints, SIAM J. Sci. Comput. 22 (2000), no. 2, 517–534. MR 1780612, DOI 10.1137/S1064827598334861
Xinwei Liu and Yaxiang Yuan, A null-space primal-dual interior-point algorithm for nonlinear optimization with nice convergence properties, Math. Program. 125 (2010), no. 1, Ser. A, 163–193. MR 2718699, DOI 10.1007/s10107-009-0272-y
Jorge Nocedal, Figen Öztoprak, and Richard A. Waltz, An interior point method for nonlinear programming with infeasibility detection capabilities, Optim. Methods Softw. 29 (2014), no. 4, 837–854. MR 3175518, DOI 10.1080/10556788.2013.858156
Jorge Nocedal and Stephen J. Wright, Numerical optimization, Springer Series in Operations Research, Springer-Verlag, New York, 1999. MR 1713114, DOI 10.1007/b98874
David F. Shanno and Robert J. Vanderbei, Interior-point methods for nonconvex nonlinear programming: orderings and higher-order methods, Math. Program. 87 (2000), no. 2, Ser. B, 303–316. Studies in algorithmic optimization. MR 1763854, DOI 10.1007/s101070050116
Paul Tseng, Convergent infeasible interior-point trust-region methods for constrained minimization, SIAM J. Optim. 13 (2002), no. 2, 432–469. MR 1951029, DOI 10.1137/S1052623499357945
Michael Ulbrich, Stefan Ulbrich, and Luís N. Vicente, A globally convergent primal-dual interior-point filter method for nonlinear programming, Math. Program. 100 (2004), no. 2, Ser. A, 379–410. MR 2062934, DOI 10.1007/s10107-003-0477-4
Robert J. Vanderbei and David F. Shanno, An interior-point algorithm for nonconvex nonlinear programming, Comput. Optim. Appl. 13 (1999), no. 1-3, 231–252. Computational optimization—a tribute to Olvi Mangasarian, Part II. MR 1704122, DOI 10.1023/A:1008677427361
Andreas Wächter and Lorenz T. Biegler, Failure of global convergence for a class of interior point methods for nonlinear programming, Math. Program. 88 (2000), no. 3, Ser. A, 565–574. MR 1782156, DOI 10.1007/PL00011386
Andreas Wächter and Lorenz T. Biegler, On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming, Math. Program. 106 (2006), no. 1, Ser. A, 25–57. MR 2195616, DOI 10.1007/s10107-004-0559-y
Margaret H. Wright, Why a pure primal Newton barrier step may be infeasible?, SIAM J. Optim. 5 (1995), no. 1, 1–12. MR 1315702, DOI 10.1137/0805001
Hiroshi Yamashita, A globally convergent primal-dual interior point method for constrained optimization, Optim. Methods Softw. 10 (1998), no. 2, 443–469. Dedicated to Professor Masao Iri on the occasion of his 65th birthday. MR 1754750, DOI 10.1080/10556789808805723
Ya Xiang Yuan, On the convergence of a new trust region algorithm, Numer. Math. 70 (1995), no. 4, 515–539. MR 1337231, DOI 10.1007/s002110050133