×

zbMATH — the first resource for mathematics

A primal-dual interior-point method capable of rapidly detecting infeasibility for nonlinear programs. (English) Zbl 1449.90325
Summary: With the help of a logarithmic barrier augmented Lagrangian function, we can obtain closed-form solutions of slack variables of logarithmic-barrier problems of nonlinear programs. As a result, a two-parameter primal-dual nonlinear system is proposed, which corresponds to the Karush-Kuhn-Tucker point and the infeasible stationary point of nonlinear programs, respectively, as one of two parameters vanishes. Based on this distinctive system, we present a primal-dual interior-point method capable of rapidly detecting infeasibility of nonlinear programs. The method generates interior-point iterates without truncation of the step. It is proved that our method converges to a Karush-Kuhn-Tucker point of the original problem as the barrier parameter tends to zero. Otherwise, the scaling parameter tends to zero, and the method converges to either an infeasible stationary point or a singular stationary point of the original problem. Moreover, our method has the capability to rapidly detect the infeasibility of the problem. Under suitable conditions, the method can be superlinearly or quadratically convergent to the Karush-Kuhn-Tucker point if the original problem is feasible, and it can be superlinearly or quadratically convergent to the infeasible stationary point when the problem is infeasible. Preliminary numerical results show that the method is efficient in solving some simple but hard problems, where the superlinear convergence to an infeasible stationary point is demonstrated when we solve two infeasible problems in the literature.
MSC:
90C30 Nonlinear programming
90C51 Interior-point methods
90C26 Nonconvex programming, global optimization
90C46 Optimality conditions and duality in mathematical programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] R. Andreani; E. G. Birgin; J. M. Martinez; M. L. Schuverdt, Augmented Lagrangian methods under the constant positive linear dependence constraint qualification, Math. Program., 111, 5-32 (2008) · Zbl 1163.90041
[2] P. Armand; J. Benoist, A local convergence property of primal-dual methods for nonlinear programming, Math. Program., 115, 199-222 (2008) · Zbl 1167.65031
[3] P. Armand; J. C. Gilbert; S. Jan-Jégou, A feasible BFGS interior point algorithm for solving convex minimization problems, SIAM J. Optim., 11, 199-222 (2000) · Zbl 0990.90092
[4] I. Bongartz; A. R. Conn; N. I. M. Gould; P. L. Toint, CUTE: Constrained and Unconstrained Testing Environment, ACM Tran. Math. Software, 21, 123-160 (1995) · Zbl 0886.65058
[5] J. V. Burke; F. E. Curtis; H. Wang, A sequential quadratic optimization algorithm with rapid infeasibility detection, SIAM J. Optim., 24, 839-872 (2014) · Zbl 1301.49069
[6] J. V. Burke; S. P. Han, A robust sequential quadratic programming method, Math. Program., 43, 277-303 (1989) · Zbl 0683.90070
[7] R. H. Byrd, Robust Trust-Region Method for Constrained Optimization, Paper presented at the SIAM Conference on Optimization, Houston, TX, 1987.
[8] R. H. Byrd; F. E. Curtis; J. Nocedal, Infeasibility detection and SQP methods for nonlinear optimization, SIAM J. Optim., 20, 2281-2299 (2010) · Zbl 1211.90179
[9] R. H. Byrd; J. C. Gilbert; J. Nocedal, A trust region method based on interior point techniques for nonlinear programming, Math. Program., 89, 149-185 (2000) · Zbl 1033.90152
[10] R. H. Byrd; M. E. Hribar; J. Nocedal, An interior point algorithm for large-scale nonlinear programming, SIAM J. Optim., 9, 877-900 (1999) · Zbl 0957.65057
[11] R. H. Byrd, G. Liu and J. Nocedal, On the local behaviour of an interior point method for nonlinear programming, In, Numerical Analysis 1997 (eds. D. F. Griffiths and D. J. Higham), Addison-Wesley Longman, Reading, MA, 380 (1998), 37-56. · Zbl 0902.65021
[12] R. H. Byrd; M. Marazzi; J. Nocedal, On the convergence of Newton iterations to non-stationary points, Math. Program., 99, 127-148 (2004) · Zbl 1072.90038
[13] L. F. Chen; D. Goldfarb, Interior-point \(\begin{document} \ell_2\end{document} \)-penalty methods for nonlinear programming with strong global convergence properties, Math. Program., 108, 1-36 (2006) · Zbl 1142.90498
[14] F. E. Curtis, A penalty-interior-point algorithm for nonlinear constrained optimization, Math. Program. Comput., 4, 181-209 (2012) · Zbl 1269.49045
[15] A. S. El-Bakry; R. A. Tapia; T. Tsuchiya; Y. Zhang, On the formulation and theory of the Newton interior-point method for nonlinear programming, J. Optim. Theory Appl., 89, 507-541 (1996) · Zbl 0851.90115
[16] A. V. Fiacco and G. P. McCormick, Nonlinear Programming: Sequential Unconstrained Minimization Techniques, John Wiley and Sons, New York, 1968; republished as Classics in Appl. Math. 4, SIAM, Philadelphia, 1990. · Zbl 0193.18805
[17] R. Fletcher, Practical Methods for Optimization. Vol. 2: Constrained Optimization, John Wiley and Sons, Chichester, 1980. · Zbl 0439.93001
[18] A. Forsgren; P. E. Gill, Primal-dual interior methods for nonconvex nonlinear programming, SIAM J. Optim., 8, 1132-1152 (1998) · Zbl 0915.90236
[19] A. Forsgren; Ph. E. Gill; M. H. Wright, Interior methods for nonlinear optimization, SIAM Review, 44, 525-597 (2002) · Zbl 1028.90060
[20] D. M. Gay, M. L. Overton and M. H. Wright, A primal-dual interior method for nonconvex nonlinear programming, in Advances in Nonlinear Programming, (ed. Y.-X. Yuan), Kluwer Academic Publishers, Dordrecht, 14 (1998), 31-56. · Zbl 0908.90236
[21] E. M. Gertz; Ph. E. Gill, A primal-dual trust region algorithm for nonlinear optimization, Math. Program., 100, 49-94 (2004) · Zbl 1146.90514
[22] N. I. M. Gould, D. Orban and Ph. L. Toint, An interior-point \(\begin{document} \ell_1\end{document} \)-penalty method for nonlinear optimization, in Recent Developments in Numerical Analysis and Optimization, Proceedings of NAOIII 2014, Springer, Verlag, 134 (2015), 117-150.
[23] W. Hock and K. Schittkowski, Test Examples for Nonlinear Programming Codes, Lecture Notes in Eco. and Math. Systems 187, Springer-Verlag, Berlin, New York, 1981. · Zbl 0452.90038
[24] X.-W. Liu; G. Perakis; J. Sun, A robust SQP method for mathematical programs with linear complementarity constraints, Comput. Optim. Appl., 34, 5-33 (2006) · Zbl 1111.90110
[25] X.-W. Liu; J. Sun, A robust primal-dual interior point algorithm for nonlinear programs, SIAM J. Optim., 14, 1163-1186 (2004) · Zbl 1079.90160
[26] X.-W. Liu; Y.-X. Yuan, A robust algorithm for optimization with general equality and inequality constraints, SIAM J. Sci. Comput., 22, 517-534 (2000) · Zbl 0972.65038
[27] X.-W. Liu; Y.-X. Yuan, A null-space primal-dual interior-point algorithm for nonlinear optimization with nice convergence properties, Math. Program., 125, 163-193 (2010) · Zbl 1205.90272
[28] J. Nocedal; F. Öztoprak; R. A. Waltz, An interior point method for nonlinear programming with infeasibility detection capabilities, Optim. Methods Softw., 29, 837-854 (2014) · Zbl 1306.90152
[29] J. Nocedal and S. Wright, Numerical Optimization, Springer-Verlag New York, Inc., 1999. · Zbl 0930.65067
[30] D. F. Shanno; R. J. Vanderbei, Interior-point methods for nonconvex nonlinear programming: Orderings and higher-order methods, Math. Program., 87, 303-316 (2000) · Zbl 1054.90091
[31] P. Tseng, Convergent infeasible interior-point trust-region methods for constrained minimization, SIAM J. Optim., 13, 432-469 (2002) · Zbl 1049.90128
[32] M. Ulbrich; S. Ulbrich; L. N. Vicente, A globally convergent primal-dual interior-point filter method for nonlinear programming, Math. Program., 100, 379-410 (2004) · Zbl 1070.90110
[33] A. Wächter; L. T. Biegler, Failure of global convergence for a class of interior point methods for nonlinear programming, Math. Program., 88, 565-574 (2000) · Zbl 0963.65063
[34] A. Wächter; L. T. Biegler, Line search filter methods for nonlinear programming: Motivation and global convergence, SIAM J. Optim., 16, 1-31 (2005) · Zbl 1114.90128
[35] A. Wächter; L. T. Biegler, On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming, Math. Program., 106, 25-57 (2006) · Zbl 1134.90542
[36] M. H. Wright, Why a pure primal Newton barrier step may be infeasible?, SIAM J. Optim., 5, 1-12 (1995) · Zbl 0821.65039
[37] S. J. Wright, On the convergence of the Newton/Log-barrier method, Math. Program., 90, 71-100 (2001) · Zbl 0986.90061
[38] Y.-X. Yuan, On the convergence of a new trust region algorithm, Numer. Math., 70, 515-539 (1995) · Zbl 0828.65062
[39] Y. Zhang, Solving large-scale linear programs by interior-point methods under the MATLAB environment, Optim. Methods Softw.,10 (1998), 1-31. · Zbl 0916.90208
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.