Abstract
We consider the class of quadratically-constrained quadratic-programming methods in the framework extended from optimization to more general variational problems. Previously, in the optimization case, Anitescu (SIAM J. Optim. 12, 949–978, 2002) showed superlinear convergence of the primal sequence under the Mangasarian-Fromovitz constraint qualification and the quadratic growth condition. Quadratic convergence of the primal-dual sequence was established by Fukushima, Luo and Tseng (SIAM J. Optim. 13, 1098–1119, 2003) under the assumption of convexity, the Slater constraint qualification, and a strong second-order sufficient condition. We obtain a new local convergence result, which complements the above (it is neither stronger nor weaker): we prove primal-dual quadratic convergence under the linear independence constraint qualification, strict complementarity, and a second-order sufficiency condition. Additionally, our results apply to variational problems beyond the optimization case. Finally, we provide a necessary and sufficient condition for superlinear convergence of the primal sequence under a Dennis-Moré type condition.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Anitescu, M.: A superlinearly convergent sequential quadratically constrained quadratic programming algorithm for degenerate nonlinear programming. SIAM J. Optim. 12, 949–978 (2002)
Boggs, B.T., Tolle, J.W.: Sequential quadratic programming. Acta Numer. 4, 1–51 (1996)
Bonnans, J.F., Shapiro, A.: Perturbation Analysis of Optimization Problems. Springer, New York (2000)
Clarke, F.H.: Optimization and Nonsmooth Analysis. SIAM, Philadelphia (1990)
Daryina, A.N., Izmailov, A.F., Solodov, M.V.: A class of active-set Newton methods for mixed complementarity problems. SIAM J. Optim. 15, 409–429 (2004)
Dennis, J.E., Moré, J.J.: A characterization of superlinear convergence and its application to quasi-Newton methods. Math. Comput. 28, 549–560 (1974)
Facchinei, F., Pang, J.-S.: Finite-Dimensional Variational Inequalities and Complementarity Problems. Springer, New York (2003)
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)
Izmailov, A.F., Solodov, M.V.: Karush-Kuhn-Tucker systems: regularity conditions, error bounds and a class of Newton-type methods. Math. Program. 95, 631–650 (2003)
Josephy, N.H.: Newton’s method for generalized equations. Technical Summary Report 1965, Mathematics Research Center, University of Wisconsin, Madison, Wisconsin (1979)
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)
Lobo, M.S., Vandenberghe, L., Boyd, S., Lebret, H.: Applications of second-order cone programming. Linear Algebra Appl. 284, 193–228 (1998)
Maratos, N.: Exact penalty function algorithms for finite dimensional and control optimization problems. Ph.D. thesis, Imperial College, University of London (1978)
Monteiro, R.D.C., Tsuchiya, T.: Polynomial convergence of primal-dual algorithms for the second-order cone programs based on the MZ-family of directions. Math. Program. 88, 61–83 (2000)
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)
Panin, V.M.: Some methods of solving convex programming problems. USSR Comput. Math. Math. Phys. 21, 57–72 (1981)
Powell, M.J.D.: Variable metric methods for constrained optimization. In: Bachem, A., Grötschel, M., Korte, B. (eds.) Mathematical Programming: The State of Art, pp. 288–311. Springer, Berlin (1983)
Solodov, M.V.: On the sequential quadratically constrained quadratic programming methods. Math. Oper. Res. 29, 64–79 (2004)
Tsuchiya, T.: A convergence analysis of the scale-invariant primal-dual path-following algorithms for second-order cone programming. Optim. Methods Softw. 11, 141–182 (1999)
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)
Author information
Authors and Affiliations
Corresponding author
Additional information
Research of the second author is partially supported by CNPq Grants 300734/95-6 and 471780/2003-0, by PRONEX–Optimization, and by FAPERJ.
Rights and permissions
About this article
Cite this article
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). https://doi.org/10.1007/s10589-007-9064-6
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10589-007-9064-6