×

zbMATH — the first resource for mathematics

An interior-point affine-scaling trust-region method for semismooth equations with box constraints. (English) Zbl 1180.90219
Summary: An algorithm for the solution of a semismooth system of equations with box constraints is described. The method is an affine-scaling trust-region method. All iterates generated by this method are strictly feasible. In this way, possible domain violations outside or on the boundary of the box are avoided. The method is shown to have strong global and local convergence properties under suitable assumptions, in particular, when the method is used with a special scaling matrix. Numerical results are presented for a number of problems arising from different areas.

MSC:
90C20 Quadratic programming
90C51 Interior-point methods
PDF BibTeX Cite
Full Text: DOI
References:
[1] Allgower, E.L., Georg, K.: Introduction to Numerical Continuation Methods. Wiley, New York (1979) · Zbl 1036.65047
[2] Bellavia, S., Macconi, M., Morini, B.: An affine scaling trust-region approach to bound-constrained nonlinear systems. Appl. Numer. Math. 44, 257–280 (2003) · Zbl 1018.65067
[3] Bellavia, S., Macconi, M., Morini, B.: STRSCNE: a scaled trust-region solver for constrained nonlinear systems. Comput. Optim. Appl. 28, 31–50 (2004) · Zbl 1056.90128
[4] Bellavia, S., Macconi, M., Morini, B.: A two-dimensional trust-region method for large scale bound-constrained nonlinear systems. Technical report, submitted for publication · Zbl 1056.90128
[5] Bellavia, S., Morini, B.: An interior global method for nonlinear systems with simple bounds. Optim. Methods Softw. 20, 453–474 (2005) · Zbl 1134.90050
[6] Bertsekas, D.P.: Projected Newton methods for optimization problems with simple constraints. SIAM J. Control Optim. 20, 221–246 (1982) · Zbl 0507.49018
[7] Byrd, R.H., Lu, P., Nocedal, J.: A limited memory algorithm for bound constrained optimization. SIAM J. Sci. Stat. Comput. 16, 1190–1208 (1995) · Zbl 0836.65080
[8] Chen, B., Chen, X., Kanzow, C.: A penalized Fischer–Burmeister NCP-function. Math. Program. 88, 211–216 (2000) · Zbl 0968.90062
[9] Clarke, F.H.: Optimization and Nonsmooth Analysis. Wiley, New York (1983) · Zbl 0582.49001
[10] Coleman, T.F., Li, Y.: On the convergence of interior reflective Newton methods for nonlinear minimization subject to bounds. Math. Program. 67, 189–224 (1994) · Zbl 0842.90106
[11] Coleman, T.F., Li, Y.: An interior trust region approach for nonlinear minimization subject to bounds. SIAM J. Optim. 6, 418–445 (1996) · Zbl 0855.65063
[12] Conn, A.R., Gould, N.I.M., Toint, P.L.: Global convergence of a class of trust region algorithms for optimization with simple bounds. SIAM J. Numer. Anal. 25, 433–460 (1998) (Correction in SIAM J. Numer. Anal. 26, 764–767 (1989)) · Zbl 0643.65031
[13] Conn, A.R., Gould, N.I.M., Toint, Ph.L.: Testing a class of methods for solving minimization problems with simple bounds on the variables. Math. Comput. 50, 399–430 (1988) · Zbl 0645.65033
[14] Conn, A.R., Gould, N.I.M., Toint, P.L.: Trust-Region Methods. MPS/SIAM Series on Optimization. SIAM, Philadelphia (2000) · Zbl 0958.65071
[15] De Luca, T., Facchinei, F., Kanzow, C.: A semismooth equation approach to the solution of nonlinear complementarity problems. Math. Program. 75, 407–439 (1996) · Zbl 0874.90185
[16] Dembo, R.S., Eisenstat, S.C., Steihaug, T.: Inexact Newton methods. SIAM J. Numer. Anal. 19, 400–408 (1982) · Zbl 0478.65030
[17] Dennis, J.E., Schnabel, R.B.: Numerical Methods for Unconstrained Optimization and Nonlinear Equations. Prentice-Hall, Englewood Cliffs (1983) · Zbl 0579.65058
[18] Dennis, J.E., Vicente, L.N.: Trust-region interior-point algorithms for minimization problems with simple bounds. In: Fischer, H., Riedmüller, B., Schäffler, S. (eds.) Applied Mathematics and Parallel Computing. Festschrift for Klaus Ritter, pp. 97–107. Physica, Heidelberg (1996) · Zbl 0907.65056
[19] Deuflhard, P.: Newton Methods for Nonlinear Problems. Springer, Berlin/Heidelberg (2004) · Zbl 1056.65051
[20] Dirkse, S.P., Ferris, M.C.: MCPLIB: A collection of nonlinear mixed complementarity problems. Optim. Methods Softw. 5, 319–345 (1995)
[21] Facchinei, F., Fischer, A., Kanzow, C.: Inexact Newton methods for semismooth equations with applications to variational inequality problems. In: Di Pillo, G., Giannessi, F. (eds.) Nonlinear Optimization and Applications, pp. 125–139. Plenum, New York (1996) · Zbl 0980.90101
[22] Facchinei, F., Júdice, J., Soares, J.: An active set Newton algorithm for large-scale nonlinear programs with box constraints. SIAM J. Optim. 8, 158–186 (1998) · Zbl 0911.90301
[23] Facchinei, F., Lucidi, S., Palagi, L.: A truncated Newton algorithm for large scale box constrained optimization. SIAM J. Optim. 12, 1100–1125 (2002) · Zbl 1035.90103
[24] Facchinei, F., Pang, J.-S.: Finite-Dimensional Variational Inequalities and Complementarity Problems, vol. II. Springer, New York (2003) · Zbl 1062.90002
[25] Facchinei, F., Soares, J.: A new merit function for nonlinear complementarity problems and a related algorithm. SIAM J. Optim. 7, 225–247 (1997) · Zbl 0873.90096
[26] Ferris, M.C., Pang, J.-S.: Engineering and economic applications of complementarity problems. SIAM Rev. 39, 669–713 (1997) · Zbl 0891.90158
[27] Floudas, C.A., et al.: Handbook of Test Problems in Local and Global Optimization. Kluwer Academic, Dordrecht (1999) · Zbl 0943.90001
[28] Friedlander, A., Martínez, J.M., Santos, S.A.: A new trust region algorithm for bound constrained minimization. Appl. Math. Optim. 30, 235–266 (1994) · Zbl 0821.90101
[29] Heinkenschloss, M., Ulbrich, M., Ulbrich, S.: Superlinear and quadratic convergence of affine-scaling interior-point Newton methods for problems with simple bounds without strict complementarity assumption. Math. Program. 86, 615–635 (1999) · Zbl 0945.49023
[30] Kanzow, C.: Strictly feasible equation-based methods for mixed complementarity problems. Numer. Math. 89, 135–160 (2001) · Zbl 0992.65070
[31] Kanzow, C.: An active set-type Newton method for constrained nonlinear systems. In: Ferris, M.C., Mangasarian, O.L., Pang, J.-S. (eds.) Complementarity: Applications, Algorithms and Extensions, pp. 179–200. Kluwer Academic, Dordrecht (2001) · Zbl 0983.90060
[32] Kanzow, C., Klug, A.: On affine-scaling interior-point Newton methods for nonlinear minimization with bound constraints. Comput. Optim. Appl. 35, 177–197 (2006) · Zbl 1151.90552
[33] Kelley, C.T.: Iterative Methods for Linear and Nonlinear Equations. SIAM, Philadelphia (1995) · Zbl 0832.65046
[34] Kelley, C.T.: Solving Nonlinear Equations with Newton’s Method. SIAM, Philadelphia (2003) · Zbl 1031.65069
[35] Kozakevich, D.N., Martínez, J.M., Santos, S.A.: Solving nonlinear systems of equations with simple constraints. Comput. Appl. Math. 16, 215–235 (1997) · Zbl 0896.65041
[36] Lescrenier, M.: Convergence of trust region algorithms for optimization with bounds when strict complementarity does not hold. SIAM J. Numer. Anal. 28, 476–495 (1991) · Zbl 0726.65068
[37] Lewis, R.M., Torczon, V.: Pattern search algorithms for bound constrained minimization. SIAM J. Optim. 9, 1082–1099 (1999) · Zbl 1031.90047
[38] Lin, C.-J., Moré, J.J.: Newton’s method for large bound-constrained optimization problems. SIAM J. Optim. 9, 1100–1127 (1999) · Zbl 0957.65064
[39] Lukšan, L.: Inexact trust region method for large sparse systems of nonlinear equations. J. Optim. Theory Appl. 81, 569–590 (1994) · Zbl 0803.65071
[40] Martínez, J.M., Qi, L.: Inexact Newton methods for solving nonsmooth equations. J. Comput. Appl. Math. 60, 127–145 (1995) · Zbl 0833.65045
[41] Meintjes, K., Morgan, A.P.: Chemical equilibrium systems as numerical test problems. ACM Trans. Math. Softw. 16, 143–151 (1990) · Zbl 0900.65153
[42] Moré, J.J., Cosnard, M.Y.: Numerical solution of nonlinear equations. ACM Trans. Math. Softw. 5, 64–85 (1979) · Zbl 0393.65019
[43] Ortega, J.M., Rheinboldt, W.C.: Iterative Solution of Nonlinear Equations in Several Variables. Academic, New York/London (1970) · Zbl 0241.65046
[44] Pang, J.-S., Qi, L.: Nonsmooth equations: motivation and algorithms. SIAM J. Optim. 3, 443–465 (1993) · Zbl 0784.90082
[45] Qi, L.: Convergence analysis of some algorithms for solving nonsmooth equations. Math. Oper. Res. 18, 227–244 (1993) · Zbl 0776.65037
[46] Qi, L., Sun, J.: A nonsmooth version of Newton’s method. Math. Program. 58, 353–367 (1993) · Zbl 0780.90090
[47] Qi, L., Tong, X., Li, D.: Active-set projected trust region algorithm for box constrained nonsmooth equations. J. Optim. Theory Appl. 120, 601–625 (2004) · Zbl 1140.65331
[48] Saad, Y.: Iterative Methods for Sparse Linear Systems, 2nd edn. SIAM, Philadelphia (2003) · Zbl 1031.65046
[49] Schwartz, A., Polak, E.: Family of projected descent methods for optimization problems with simple bounds. J. Optim. Theory Appl. 92, 1–31 (1997) · Zbl 0886.90140
[50] Stoer, J., Bulirsch, R.: Introduction to Numerical Analysis, 2nd edn. Springer, New York (1993) · Zbl 0771.65002
[51] Tong, X.J., Qi, L.: On the convergence of a trust-region method for solving constrained nonlinear equations with degenerate solutions. J. Optim. Theory Appl. 123, 187–211 (2004) · Zbl 1069.65055
[52] Ulbrich, M.: Non-monotone trust-region methods for bound-constrained semismooth equations with applications to nonlinear mixed complementarity problems. SIAM J. Optim. 11, 889–917 (2001) · Zbl 1010.90085
[53] Ulbrich, M., Ulbrich, S.: Superlinear convergence of affine-scaling interior-point Newton methods for infinite-dimensional nonlinear problems with pointwise bounds. SIAM J. Control Optim. 38, 1938–1984 (2000) · Zbl 1010.90094
[54] Ulbrich, M., Ulbrich, S., Heinkenschloss, M.: Global convergence of trust-region interior-point algorithms for infinite-dimensional nonconvex minimization subject to pointwise bounds. SIAM J. Control Optim. 37, 731–764 (1999) · Zbl 1111.90368
[55] Zhu, C., Byrd, R.H., Nocedal, J.: Algorithm 778: L-BFGS-B, FORTRAN routines for large scale bound constrained optimization. ACM Trans. Math. Softw. 23, 550–560 (1997) · Zbl 0912.65057
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.