Abstract
We propose and analyze a perturbed version of the classical Josephy–Newton method for solving generalized equations. This perturbed framework is convenient to treat in a unified way standard sequential quadratic programming, its stabilized version, sequential quadratically constrained quadratic programming, and linearly constrained Lagrangian methods. For the linearly constrained Lagrangian methods, in particular, we obtain superlinear convergence under the second-order sufficient optimality condition and the strict Mangasarian–Fromovitz constraint qualification, while previous results in the literature assume (in addition to second-order sufficiency) the stronger linear independence constraint qualification as well as the strict complementarity condition. For the sequential quadratically constrained quadratic programming methods, we prove primal-dual superlinear/quadratic convergence under the same assumptions as above, which also gives a new result.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
An, L.T.H.: An efficient algorithm for globally minimizing a quadratic function under convex quadratic constraints. Math. Program. 87, 401–426 (2000)
Anitescu, M.: A superlinearly convergent sequential quadratically constrained quadratic programming algorithm for degenerate nonlinear programming. SIAM J. Optim. 12, 949–978 (2002)
Arutyunov, A.V., Izmailov, A.F.: Sensitivity analysis for cone-constrained optimization problems under the relaxed constraint qualifications. Math. Oper. Res. 30, 333–353 (2005)
Audet, C., Hansen, P., Jaumard, B., Savard, G.: A branch and cut algorithm for nonconvex quadratically constrained quadratic programming. Math. Program. 87, 131–152 (2000)
Bertsekas, D.P.: Constrained Optimization and Lagrange Multiplier Methods. Academic Press, New York (1982)
Boggs, B.T., Tolle, J.W.: Sequential quadratic programming. Acta Numer. 4, 1–51 (1996)
Bonnans, J.F.: Local analysis of Newton-type methods for variational inequalities and nonlinear programming. Appl. Math. Optim. 29, 161–186 (1994)
Bonnans, J.F., Shapiro, A.: Perturbation Analysis of Optimization Problems. Springer, New York (2000)
Bonnans, J.F., Gilbert, J.Ch., Lemaréchal, C., Sagastizábal, C.: Numerical Optimization: Theoretical and Practical Aspects, 2nd edn. Springer, Berlin (2006)
Dennis, J.E., Moré, J.J.: A characterization of superlinear convergence and its application to quasi-Newton methods. Math. Comput. 28, 549–560 (1974)
Fernández, D., Solodov, M.: On local convergence of sequential quadratically-constrained quadratic-programming type methods, with an extension to variational problems. Comput. Optim. Appl. 39, 143–160 (2008)
Fernández, D., Solodov, M.: Stabilized sequential quadratic programming for optimization and a stabilized Newton-type method for variational problems. Math. Program. (2009). DOI 10.1007/s10107-008-0255-4
Fischer, A.: Local behavior of an iterative framework for generalized equations with nonisolated solutions. Math. Program. 94, 91–124 (2002)
Friedlander, M.P., Saunders, M.A.: A globally convergent linearly constrained Lagrangian method for nonlinear optimization. SIAM J. Optim. 15, 863–897 (2005)
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)
Hager, W.W.: Stabilized sequential quadratic programming. Comput. Optim. Appl. 12, 253–273 (1999)
Huang, Z.-H., Sun, D., Zhao, G.: A smoothing Newton-type algorithm of stronger convergence for the quadratically constrained convex quadratic programming. Comput. Optim. Appl. 35, 199–237 (2006)
Josephy, N.H.: Newton’s method for generalized equations. Technical Summary Report no. 1965, Mathematics Research Center, University of Wisconsin, Madison (1979)
Josephy, N.H.: Quasi-Newton methods for generalized equations. Technical Summary Report no. 1966, Mathematics Research Center, University of Wisconsin, Madison (1979)
Kantorovich, L.V., Akilov, G.P.: Functional Analysis, 2nd edn. Pergamon, Oxford (1982)
Kruk, S., Wolkowicz, H.: Sequential, quadratically constrained, quadratic programming for general nonlinear programming. In: Wolkowicz, H., Saigal, R., Vandenberghe, L. (eds.) Handbook of Semidefinite Programming, pp. 563–575. Kluwer Academic, Dordrecht (2000)
Li, D.-H., Qi, L.: Stabilized SQP method via linear equations. Appl. Math. Techn. Rept. AMR00/5, Univ. New South Wales, Sydney (2000)
Lobo, M.S., Vandenberghe, L., Boyd, S., Lebret, H.: Applications of second-order cone programming. Linear Algebra Appl. 284, 193–228 (1998)
Murtagh, B.A., Saunders, M.A.: A projected Lagrangian algorithm and its implementation for sparse nonlinear constraints. Math. Program. Study 16, 84–117 (1982)
Nesterov, Y.E., Nemirovskii, A.S.: Interior Point Polynomial Methods in Convex Programming: Theory and Applications. SIAM, Philadelphia (1993)
Panin, V.M.: A second-order method for discrete min-max problem. USSR Comput. Math. Math. Phys. 19, 90–100 (1979)
Robinson, S.M.: A quadratically convergent algorithm for general nonlinear programming problems. Math. Program. 3, 145–156 (1972)
Robinson, S.M.: Perturbed Kuhn–Tucker points and rates of convergence for a class of nonlinear-programming algorithms. Math. Program. 7, 1–16 (1974)
Robinson, S.M.: Stability theorems for systems of inequalities, Part II: Differentiable nonlinear systems. SIAM J. Numer. Anal. 13, 497–513 (1976)
Robinson, S.M.: Strongly regular generalized equations. Math. Oper. Res. 5, 43–62 (1980)
Solodov, M.V.: On the sequential quadratically constrained quadratic programming methods. Math. Oper. Res. 29, 64–79 (2004)
Wiest, E.J., Polak, E.: A generalized quadratic programming-based phase-I–phase-II method for inequality-constrained optimization. Appl. Math. Optim. 26, 223–252 (1992)
Wright, S.J.: Superlinear convergence of a stabilized SQP method to a degenerate solution. Comput. Optim. Appl. 11, 253–275 (1998)
Wright, S.J.: Modifying SQP for degenerate problems. SIAM J. Optim. 13, 470–497 (2002)
Wright, S.J.: Constraint identification and algorithm stabilization for degenerate nonlinear programs. Math. Program. 95, 137–160 (2003)
Author information
Authors and Affiliations
Corresponding author
Additional information
Research of the first author is supported by the Russian Foundation for Basic Research Grants 07-01-00270, 07-01-00416 and 08-01-90001-Bel, and by RF President’s Grant NS-693.2008.1 for the support of leading scientific schools. The second author is supported in part by CNPq Grants 300513/2008-9 and 471267/2007-4, by PRONEX–Optimization, and by FAPERJ.
Rights and permissions
About this article
Cite this article
Izmailov, A.F., Solodov, M.V. 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). https://doi.org/10.1007/s10589-009-9265-2
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10589-009-9265-2