×

Newton-type methods: a broader view. (English) Zbl 1310.65063

Summary: We discuss the question of which features and/or properties make a method for solving a given problem belong to the “Newtonian class.” Is it the strategy of linearization (or perhaps, second-order approximation) of the problem data (maybe only part of the problem data)? Or is it fast local convergence of the method under natural assumptions and at a reasonable computational cost of its iteration? We consider both points of view, and also how they relate to each other. In particular, we discuss abstract Newtonian frameworks for generalized equations, and how a number of important algorithms for constrained optimization can be related to them by introducing structured perturbations to the basic Newton iteration. This gives useful tools for local convergence and rate-of-convergence analysis of various algorithms from unified perspectives, often yielding sharper results than provided by other approaches. Specific constrained optimization algorithms, which can be conveniently analyzed within perturbed Newtonian frameworks, include the sequential quadratic programming method and its various modifications (truncated, augmented Lagrangian, composite step, stabilized, and equipped with second-order corrections), the linearly constrained Lagrangian methods, inexact restoration, sequential quadratically constrained quadratic programming, and certain interior feasible directions methods. We recall most of those algorithms as examples to illustrate the underlying viewpoint. We also discuss how the main ideas of this approach go beyond clearly Newton-related methods and are applicable, for example, to the augmented Lagrangian algorithm (also known as the method of multipliers), which is in principle not of Newton type since its iterations do not approximate any part of the problem data.

MSC:

65K05 Numerical mathematical programming methods
90C20 Quadratic programming
90C30 Nonlinear programming
90C53 Methods of quasi-Newton type

Software:

PLCP; MINOS; SQPlab
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Izmailov, AF; Kurennoy, AS, Abstract Newtonian frameworks and their applications, SIAM J. Optim., 23, 2369-2396, (2013) · Zbl 1298.49046
[2] Facchinei, F., Pang, J.-S.: Finite-Dimensional Variational Inequalities and Complementarity Problems. Springer-Verlag, New York (2003) · Zbl 1062.90002
[3] Bonnans, JF, Local analysis of Newton-type methods for variational inequalities and nonlinear programming, Appl. Math. Optim., 29, 161-186, (1994) · Zbl 0809.90115
[4] Fischer, A, Local behavior of an iterative framework for generalized equations with nonisolated solutions, Math. Program., 94, 91-124, (2002) · Zbl 1023.90067
[5] Klatte, D., Kummer, B.: Nonsmooth Equations in Optimization: Regularity, Calculus, Methods and Applications. Kluwer Academic Publishers, Dordrecht (2002) · Zbl 1173.49300
[6] Robinson, SM, Newton’s method for a class of nonsmooth functions, Set-Valued Anal., 2, 291-305, (1994) · Zbl 0804.65062
[7] Robinson, SM, A point-of-attraction result for newton’s method with point-based approximations, Optimization, 60, 89-99, (2011) · Zbl 1216.49026
[8] Dontchev, A.L., Rockafellar, R.T.: Implicit Functions and Solution Mappings. Springer, New York (2009) · Zbl 1178.26001
[9] Izmailov, AF; Solodov, MV, Inexact josephy-Newton framework for generalized equations and its applications to local analysis of Newtonian methods for constrained optimization, Comput. Optim. Appl., 46, 347-368, (2010) · Zbl 1220.90165
[10] Izmailov, AF; Solodov, MV, A truncated SQP method based on inexact interior-point solutions of subproblems, SIAM J. Optim., 20, 2584-2613, (2010) · Zbl 1211.90233
[11] Wright, SJ, Superlinear convergence of a stabilized SQP method to a degenerate solution, Comput. Optim. Appl., 11, 253-275, (1998) · Zbl 0917.90279
[12] Hager, WW, Stabilized sequential quadratic programming, Comput. Optimizat. Appl., 12, 253-273, (1999) · Zbl 1040.90566
[13] Fernández, D; Solodov, M, Stabilized sequential quadratic programming for optimization and a stabilized Newton-type method for variational problems, Math. Program., 125, 47-73, (2010) · Zbl 1203.90144
[14] Izmailov, AF; Solodov, MV, Stabilized SQP revisited, Math. Program., 133, 93-120, (2012) · Zbl 1245.90145
[15] Solodov, MV; Cochran, JJ (ed.), Constraint qualifications, (2010), New York · Zbl 1193.49042
[16] Robinson, SM, A quadratically convergent algorithm for general nonlinear programming problems, Math. Program., 3, 145-156, (1972) · Zbl 0264.90041
[17] Murtagh, BA; Saunders, MA, A projected Lagrangian algorithm and its implementation for sparse nonlinear constraints, Math. Program. Study, 16, 84-117, (1982) · Zbl 0477.90069
[18] Friedlander, MP; Saunders, MA, A globally convergent linearly constrained Lagrangian method for nonlinear optimization, SIAM J. Optim., 15, 863-897, (2005) · Zbl 1077.90065
[19] Martínez, JM, Inexact restoration method with Lagrangian tangent decrease and new merit function for nonlinear programming, J. Optim. Theory Appl., 111, 39-58, (2001) · Zbl 1052.90089
[20] Birgin, EG; Martínez, JM, Local convergence of an inexact-restoration method and numerical experiments, J. Optim. Theory Appl., 127, 229-247, (2005) · Zbl 1116.90094
[21] Fischer, A; Friedlander, A, A new line search inexact restoration approach for nonlinear programming, Comput. Optim. Appl., 46, 333-346, (2010) · Zbl 1220.90122
[22] Fernández, D; Pilotta, EA; Torres, GA, An inexact restoration strategy for the globalization of the ssqp method, Comput. Optim. Appl., 54, 595-617, (2013) · Zbl 1295.90077
[23] Wiest, EJ; Polak, E, A generalized quadratic programming-based phase-I-II method for inequality-constrained optimization, Appl. Math. Optim., 26, 223-252, (1992) · Zbl 0770.90049
[24] Kruk, S; Wolkowicz, H; Wolkowicz, H (ed.); Saigal, R (ed.); Vandenberghe, L (ed.), Sequential, quadratically constrained, quadratic programming for general nonlinear programming, 563-575, (2000), Dordrecht · Zbl 0957.90532
[25] Anitescu, M, A superlinearly convergent sequential quadratically constrained quadratic programming algorithm for degenerate nonlinear programming, SIAM J. Optim., 12, 949-978, (2002) · Zbl 1035.90081
[26] Fukushima, M; Luo, Z-Q; Tseng, P, A sequential quadratically constrained quadratic programming method for differentiable convex minimization, SIAM J. Optim., 13, 1098-1119, (2003) · Zbl 1060.90077
[27] Solodov, MV, On the sequential quadratically constrained quadratic programming methods, Math. Oper. Res., 29, 64-79, (2004) · Zbl 1082.90140
[28] Fernández, D; Solodov, MV, On local convergence of sequential quadratically-constrained quadratic-programming type methods, with an extension to variational problems, Comput. Optim. Appl., 39, 143-160, (2008) · Zbl 1144.90457
[29] Vardi, A, A trust region algorithm for equality constrained minimization: convergence properties and implementation, SIAM J. Numer. Anal., 22, 575-591, (1985) · Zbl 0581.65045
[30] Omojokun, E.O.: Trust region algorithms for optimization with nonlinear equality and inequality constraints. Ph.D. thesis. Department of Computer Science, University of Colorado at Boulder, (1989) · Zbl 1144.90457
[31] Fletcher, R; Griffiths, D (ed.), Second order corrections for non-differentiable optimization, 85-114, (1982), Berlin
[32] Herskovits, J.: A two-stage feasible direction algorithm including variable metric techniques for nonlinear optimization problems. Rapport de Recherche 118. INRIA, Rocqencourt, (1982) · Zbl 1060.90077
[33] Herskovits, J, A two-stage feasible directions algorithm for nonlinear constrained optimization, Math. Program., 36, 19-38, (1986) · Zbl 0623.90070
[34] Herskovits, J, Feasible direction interior-point technique for nonlinear optimization, J. Optim. Theory Appl., 99, 121-146, (1998) · Zbl 0911.90303
[35] Panier, ER; Tits, AL; Herskovits, J, A QP-free, globally convergent, locally superlinearly convergent algorithm for inequality constrained optimization, SIAM J. Control Optim., 26, 788-811, (1988) · Zbl 0651.90072
[36] Tits, AL; Wächter, A; Bakhtiari, S; Urban, TJ; Lawrence, CT, A primal-dual interior-point method for nonlinear programming with strong global and local convergence properties, SIAM J. Optim., 14, 173-199, (2003) · Zbl 1075.90078
[37] Izmailov, A.F., Kurennoy, A.S., Solodov, M.V.: Some composite-step constrained optimization methods interpreted via the perturbed sequential quadratic programming framework. Optim. Method. Softw. (to appear) · Zbl 1327.90313
[38] Izmailov, A.F., Solodov, M.V.: Newton-Type Methods for Optimization and Variational Problems. Springer Series in Operations Research and Financial Engineering. Springer International Publishing, Switzerland (2014) · Zbl 1304.49001
[39] Hestenes, MR, Multiplier and gradient methods, J. Optim. Theory Appl., 4, 303-320, (1969) · Zbl 0174.20705
[40] Powell, MJD; Fletcher, R (ed.), A method for nonlinear constraints in minimization problems, 283-298, (1969), New York
[41] Conn, AR; Gould, N; Sartenaer, A; Toint, PL, Convergence properties of an augmented Lagrangian algorithm for optimization with a combination of general equality and linear constraints, SIAM J. Optim., 6, 674-703, (1996) · Zbl 0856.90098
[42] Andreani, R; Birgin, EG; Martínez, JM; Schuverdt, ML, On augmented Lagrangian methods with general lower-level constraints, SIAM J. Optim., 18, 1286-1309, (2007) · Zbl 1151.49027
[43] Fernández, D; Solodov, MV, Local convergence of exact and inexact augmented Lagrangian methods under the second-order sufficient optimality condition, SIAM J. Optim., 22, 384-407, (2012) · Zbl 1259.90132
[44] Josephy, N.H.: Newton’s method for generalized equations. Technical Summary Report 1965. Mathematics Research Center, University of Wisconsin, Madison, WI (1979)
[45] Rockafellar, R.T., Wets, J.B.: Variational Analysis. Springer-Verlag, Berlin (1998) · Zbl 0888.49001
[46] Kinderlehrer, D., Stampacchia, G.: An Introduction to Variational Inequalities and Their Applications. Academic Press, New York (1980) · Zbl 0457.35001
[47] Bonnans, J.F., Shapiro, A.: Perturbation Analysis of Optimization Problems. Springer-Verlag, New York (2000) · Zbl 0966.49001
[48] Giannessi, F.: Constrained Optimization and Image Space Analysis. Springer-Verlag, New York (2005) · Zbl 1082.49001
[49] Boggs, P; Tolle, J, Sequential quadratic programming, Acta Numer., 4, 1-51, (1995) · Zbl 0828.65060
[50] Gill, PE; Wong, E; Lee, J (ed.); Leyffer, S (ed.), Sequential quadratic programming methods, No. 154, 147-224, (2012), Berlin · Zbl 1242.90297
[51] Rademacher, H, Über partielle und totale differenzierbarkeit I, Math. Ann., 89, 340-359, (1919) · JFM 47.0243.01
[52] Dontchev, AL; Rockafellar, RT, Newton’s method for generalized equations: a sequential implicit function theorem, Math. Program., 123, 139-159, (2010) · Zbl 1190.49024
[53] Robinson, SM, Strongly regular generalized equations, Math. Oper. Res., 5, 43-62, (1980) · Zbl 0437.90094
[54] Izmailov, AF, Strongly regular nonsmooth generalized equations, Math. Program., (2013) · Zbl 1301.49043
[55] Kojima, M; Robinson, SM (ed.), Strongly stable stationary solutions in nonlinear programs, 93-138, (1980), New York
[56] Bonnans, JF; Sulem, A, Pseudopower expansion of solutions of generalized equations and constrained optimization, Math. Program., 70, 123-148, (1995) · Zbl 0842.65044
[57] Dontchev, AL; Rockafellar, RT, Characterizations of strong regularity for variational inequalities over polyhedral convex sets, SIAM J. Optim., 6, 1087-1105, (1996) · Zbl 0899.49004
[58] Izmailov, AF; Kurennoy, AS; Solodov, MV, A note on upper Lipschitz stability, error bounds, and critical multipliers for Lipschitz-continuous KKT systems, Math. Program., 142, 591-604, (2013) · Zbl 1282.90177
[59] Izmailov, AF; Kurennoy, AS; Solodov, MV, The josephy-Newton method for semismooth generalized equations and semismooth SQP for optimization, Set-Valued Var. Anal., 21, 17-45, (2013) · Zbl 1285.90065
[60] Josephy, N.H.: Quasi-Newton methods for generalized equations. Technical Summary Report 1966. Mathematics Research Center, University of Wisconsin, Madison, WI (1979)
[61] Mifflin, R, Semismooth and semiconvex functions in constrained optimization, SIAM J. Control Optim., 15, 959-972, (1977) · Zbl 0376.90081
[62] Conn, A.R., Gould, N.I.M., Toint, PhL: Trust-Region Methods. SIAM, Philadelphia (2000) · Zbl 0958.65071
[63] Bonnans, J.F., Gilbert, JCh., Lemaréchal, C., Sagastizábal, C.: Numerical Optimization: Theoretical and Practical Aspects, 2nd edn. Springer-Verlag, Berlin (2006)
[64] Nocedal, J., Wright, S.J.: Numerical Optimization, 2nd edn. Springer, New York (2006) · Zbl 1104.65059
[65] Wilson, R.B.: A simplicial algorithm for concave programming. Ph.D. thesis. Graduate School of Business Administration, Harvard University (1963) · Zbl 0946.65047
[66] Robinson, SM, Perturbed Kuhn-Tucker points and rates of convergence for a class of nonlinear-programming algorithms, Math. Program., 7, 1-16, (1974) · Zbl 0294.90078
[67] Bertsekas, D.P.: Constrained Optimization and Lagrange Multiplier Methods. Academic Press, New York (1982) · Zbl 0572.90067
[68] Fernández, D; Izmailov, AF; Solodov, MV, Sharp primal superlinear convergence results for some Newtonian methods for constrained optimization, SIAM J. Optim., 20, 3312-3334, (2010) · Zbl 1235.90147
[69] Dembo, RS; Eisenstat, SC; Steihaug, T, Inexact Newton methods, SIAM J. Numer. Anal., 19, 400-408, (1982) · Zbl 0478.65030
[70] Gould, N.I.M.: Some reflections on the current state of active-set and interior-point methods for constrained optimization. Numerical Analysis Group Internal Report 2003-1. Computational Science and Engineering Department, Rutherford Appleton Laboratory, Oxfordshire (2003)
[71] Gould, NIM; Orban, D; Toint, PhL, Numerical methods for large-scale nonlinear optimization, Acta Numer., 14, 299-361, (2005) · Zbl 1119.65337
[72] Leibfritz, F; Sachs, EW, Inexact SQP interior point methods and large scale optimal control problems, SIAM J. Control Optim., 38, 272-293, (1999) · Zbl 0946.65047
[73] Murtagh, B.A., Saunders, M.A.: MINOS 5.0 user’s guide. Technical Report SOL 83.20. Stanford University (1983) · Zbl 0804.65062
[74] Martínez, JM; Pilotta, EA, Inexact restoration algorithms for constrained optimization, J. Optim. Theory Appl., 104, 135-163, (2000) · Zbl 0969.90094
[75] Martínez, JM; Pilotta, EA; Qi, LQ (ed.); Teo, KL (ed.); Yang, XQ (ed.), Inexact restoration methods for nonlinear programming: advances and perspectives, 271-292, (2005), Berlin · Zbl 1118.90319
[76] Maratos, N.: Exact penalty function algorithms for finite dimensional and control optimization problems. Ph.D. thesis. University of London (1978)
[77] Li, D.-H., Qi, L.: Stabilized SQP method via linear equations. Applied Mathematics Technical Reptort AMR00/5. University of New South Wales, Sydney (2000) · Zbl 1295.90077
[78] Wright, SJ, Modifying SQP for degenerate problems SIAM, J. Optim., 13, 470-497, (2002) · Zbl 1026.90097
[79] Wright, SJ, Constraint identification and algorithm stabilization for degenerate nonlinear programs, Math. Program., 95, 137-160, (2003) · Zbl 1030.90126
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.