×

zbMATH — the first resource for mathematics

Dynamic updates of the barrier parameter in primal-dual methods for nonlinear programming. (English) Zbl 1180.90305
Summary: We introduce a framework in which updating rules for the barrier parameter in primal-dual interior-point methods become dynamic. The original primal-dual system is augmented to incorporate explicitly an updating function. A Newton step for the augmented system gives a primal-dual Newton step and also a step in the barrier parameter. Based on local information and a line search, the decrease of the barrier parameter is automatically adjusted. We analyze local convergence properties, report numerical experiments on a standard collection of nonlinear problems and compare our results to a state-of-the-art interior-point implementation. In many instances, the adaptive algorithm reduces the number of iterations and of function evaluations. Its design guarantees a better fit between the magnitudes of the primal-dual residual and of the barrier parameter along the iterations.

MSC:
90C30 Nonlinear programming
90C51 Interior-point methods
Software:
CUTEr; Ipopt; COPS; SifDec; KELLEY
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bertsekas, D.P.: Constrained Optimization and Lagrange Multiplier Methods. Academic, London (1982) · Zbl 0572.90067
[2] Byrd, R.H., Liu, G., Nocedal, J.: On the local behavior of an interior point method for nonlinear programming. In: Griffiths, D.F., Higham, D.J. (eds.) Numerical Analysis 1997, pp. 37–56. Addison Wesley Longman (1997). Proceedings of the Dundee 1997 Conference on Numerical Analysis · Zbl 0902.65021
[3] Dolan, E., Moré, J.J.: Benchmarking optimization software with performance profiles. Math. Program. Ser. B 91, 201–213 (2002) · Zbl 1049.90004
[4] Dolan, E.D., Moré, J.J., Munson, T.S.: Benchmarking optimization software with COPS 3.0. Technical Report ANL/MCS-273, Argonne National Laboratory (2004)
[5] Dussault, J.-P.: Numerical stability and efficiency of penalty algorithms. SIAM J. Numer. Anal. 32(1), 296–317 (1995) · Zbl 0816.65039
[6] El-Bakry, A.S., Tapia, R.A., Tsuchiya, T., Zhang, Y.: On the formulation and theory of newton interior point methods for nonlinear programming. J. Optim. Theory Appl. 89(3), 507–541 (1996) · Zbl 0851.90115
[7] Fiacco, A.V., McCormick, G.P.: Nonlinear Programming: Sequential Unconstrained Minimization Techniques. Wiley, Chichester (1968). Reprinted as Classics in Applied Mathematics. SIAM, Philadelphia (1990) · Zbl 0193.18805
[8] Gay, D.M., Overton, M.L., Wright, M.H.: A primal-dual interior method for nonconvex nonlinear programming. In: Yuan, Y. (ed.) Advances in Nonlinear Programming, pp. 31–56. Kluwer Academic, Dordrecht (1998) · Zbl 0908.90236
[9] Gould, N.I.M., Orban, D., Sartenaer, A., Toint, P.L.: Superlinear convergence of primal-dual interior point algorithms for nonlinear programming. SIAM J. Optim. 11(4), 974–1002 (2001) · Zbl 1003.65066
[10] Gould, N.I.M., Orban, D., Sartenaer, A., Toint, P.L.: Componentwise fast convergence in the solution of full-rank systems of nonlinear equation. Math. Program. Ser. B 92(3), 481–508 (2002) · Zbl 1012.65046
[11] Gould, N.I.M., Orban, D., Toint, P.L.: \(\mathsf{CUTEr}\) and \(\mathsf{SifDec}\) , a constrained and unconstrained testing environment, revisited. Trans. ACM Math. Softw. 29(4), 373–394 (2003) · Zbl 1068.90526
[12] Kelley, C.T.: Iterative Methods for Linear and Nonlinear Equations. Frontiers in Applied Mathematics, vol. 16. SIAM, Belmont (1995) · Zbl 0832.65046
[13] Mehrotra, S.: On the implementation of a primal-dual interior point method. SIAM J. Optim. 2(4), 575–601 (1992) · Zbl 0773.90047
[14] Nocedal, J., Wächter, A., Waltz, R.A.: Adaptive barrier strategies for nonlinear interior methods. Technical Report, Northwestern University, IL, USA (2005) · Zbl 1176.49036
[15] Vanderbei, R.J., Shanno, D.F.: An interior point algorithm for nonconvex nonlinear programming. Comput. Optim. Appl. 13(2), 231–252 (1999) · Zbl 1040.90564
[16] Vicente, L.N., Wright, S.J.: Local convergence of a primal-dual method for degenerate nonlinear programming. Comput. Optim. Appl. 22(3), 311–328 (2002) · Zbl 1039.90093
[17] Wächter, A., Biegler, L.T.: Failure of global convergence for a class of interior point methods for nonlinear programming. Math. Program. Ser. B 88(3), 565–574 (2000) · Zbl 0963.65063
[18] Wächter, A., Biegler, L.T.: On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Math. Program. Ser. A 106(1), 25–57 (2006) · Zbl 1134.90542
[19] Yabe, H., Yamashita, H.: Q-superlinear convergence of primal-dual interior point quasi-Newton methods for constrained optimization. J. Oper. Res. Soc. Jpn. 40(3), 415–436 (1997) · Zbl 0914.90246
[20] Yamashita, H., Yabe, H.: Superlinear and quadratic convergence of some primal-dual interior point methods for constrained optimization. Math. Program. Ser. A 75(3), 377–397 (1996) · Zbl 0874.90175
[21] Yamashita, H., Yabe, H., Tanabe, T.: A globally and superlinearly convergent primal-dual interior point trust region method for large scale constrained optimization. Math. Program. Ser. A 102(1), 111–151 (2005) · Zbl 1062.90036
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.