Abstract
In this paper we propose a smoothing Newton-type algorithm for the problem of minimizing a convex quadratic function subject to finitely many convex quadratic inequality constraints. The algorithm is shown to converge globally and possess stronger local superlinear convergence. Preliminary numerical results are also reported.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
A. Bakushinsky and A. Goncharsky, Ill-Posed Problems: Theory and Applications, Kluwer Academic Publishers, Boston, 1989.
F.H. Clarke, Optimization and Nonsmooth Analysis, Wiley, New York, 1983.
F. Cole, J.G. Ecker, and W. Gochet, “A reduced gradient method for quadratic programs with quadratic constraints and l p -constrained l p -approximation problems,” European J. Oper. Res., vol. 9, pp. 194–203, 1982.
S. Engelke and C. Kanzow, “Predictor-corrector smoothing methods for the solution of linear programming,” Preprint, Department of Mathematics, University of Hamburg, Germany, 2000.
S. Engelke and C. Kanzow, “Improved smoothing-type methods for the solution of linear programming,” Numer. Math., vol. 90, pp. 487–507, 2002.
F. Facchnei, A. Fischer, and C. Kanzow, “On the accurate identification of active constrains,” SIAM J. Optim., vol. 9, pp. 14–32, 1998.
F. Facchnei and C. Kanzow, “Beyond monotonicity in regularization methods for nonlinear complementarity problems,” SIAM J. Control Optim., vol. 37, pp. 1150–1161, 1999.
F. Facchinei and J.-S. Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems, Volume II. Springer-Verlag, New York, 2003.
A. Fischer, “Solution of monotone complementarity problems with Lipschitzian functions,” Math. Program., vol. 76, pp. 513–532, 1997.
A. Fischer, “Local beharior of an iterative framework for generalized equations with nonisolated solutions,” Math. Program., vol. 94, pp. 91–124, 2002.
M.S. Gowda and J.J. Sznajder, “Weak univalence and connectedness of inverse images of continuous functions,” Math. Oper. Res., vol. 24, pp. 255–261, 1999.
Z.H. Huang, “Sufficient conditions on nonemptiness and boundedness of the solution set of the P 0 function nonlinear complementarity problem,” Oper. Res. Letters, vol. 30, pp. 202–210, 2002.
Z.H. Huang, J. Han, and Z. Chen, “A predictor-corrector smoothing Newton algorithm, based on a new smoothing function, for solving the nonlinear complementarity problem with a P 0 function,” J. Optim. Theory Appl., vol. 117, pp. 39–68, 2003.
Z.H. Huang, L. Qi, and D. Sun, “Sub-quadratic convergence of a smoothing Newton algorithm for the P 0- and monotone LCP,” Math. Program., vol. 99, pp. 423–441, 2004.
S. Karamardian, “Complementarity problems over cones with monotone and pseudomonotone maps,” J. Optim. Theory Appl., vol. 18, pp. 445–454, 1976.
M. Kojima, “Strongly stable stationary solutions in nonlinear programs,” in S.M. Robinson (ed.), Analysis and Computation of Fixed Points, Academic Press, New York, pp. 93–138, 1980.
M.S. Lobo, L. Vandenberghe, S. Boyd, and H. Lebert, “Applications of second-order cone programming,” Linear Algebra Appl., vol. 284, pp. 193–228, 1998.
L. Mclinden, “Stable monotone variational inequalities,” Math. Program., vol. 48, pp. 303–338, 1990.
R. Mifflin, “ Semismooth and semiconvex functions in constrained optimization,” SIAM J. Control Optim., vol. 15, pp. 957–972, 1977.
S. Mizuno, “A superlinearly convergent infeasible-interior-point algorithm for geometrical LCPs without strictly complementary condition,” Math. Oper. Res., vol. 21, pp. 382–400, 1996.
Y.E. Nesterov and A.S. Nemirovskii, Interior Point Polynomial Methods in Convex Programming: Theory and Applications, SIAM, Philadelphia, PA, 1994.
E. Polak, Optimization: Algorithms and Consistent Approximations, New York, Springer-Verlag, 1997.
E. Polak, L. Qi, and D. Sun, “Second-order algorithm for generalized finite and semi-infinite min-max problems,” SIAM J. Optim., vol. 11, pp. 937–961, 2001.
H.D. Qi, “A regularized smoothing Newton method for box constrained variational inequality problems with P 0-functions,” SIAM J. Optim., vol. 10, pp. 315–330, 2000.
L. Qi and J. Sun, “A nonsmooth version of Newton’s method,” Math. Program., vol. 58, pp. 353–367, 1993.
L. Qi, D. Sun, and G. Zhou, “A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequality problems,” Math. Program., vol. 87, pp. 1–35, 2000.
D. Ralph and S.J. Wright, “Superlinear convergence of an interior point method for monotone variational inequalities,” Complementarity and Variational Problems: State of the Art, SIAM, pp. 345–385, 1997.
D. Ralph and S.J. Wright, “Superlinear convergence of an interior point method despite dependent constraints,” Math. Oper. Res., vol. 25, pp. 179–194, 2000.
G. Ravindran and M.S. Gowda, “Regularization of P 0−functions in box variational inequality problems,” SIAM J. Optim., vol. 11, pp. 748–760, 2001.
S.M. Robinson, “Normal maps induced by linear transformation,” Math. Oper. Res., vol. 17, pp. 691–714, 1992.
J. Stoer, M. Weches, and S. Mizuno, “Hight order infeasible-interior-point methods for solving sufficient linear complementarity problems,” Math. Oper. Res., vol. 23, pp. 832–862, 1998.
J.F. Sturm, “Superlinear convergence of an algorithm for monotone linear complementarity problems, when no strictly complementary solution exists,” Math. Oper. Res., vol. 24, pp. 72–94, 1999.
D. Sun, “A regularization Newton method for solving nonlinear complementarity problems,” Appl. Math. Optim., vol. 36, pp. 315–339, 1999.
J. Sun and G. Zhao, “Quadratic convergence of a long-step interior point method for nonlinear monotone variational inequality problems,” J. Optim. Theory Appl., vol. 97, pp. 471–491, 1998.
P. Tseng, “Error bounds and superlinear convergence analysis of some Newton-type methods in optimization,” in Nonlinear Optimization and Related Topics, Di G. Pillo and F. Giannessi (eds.), Kluwer Academic Publishers, Boston, pp. 445–462, 2000.
S.J. Wright, Primal-Dual Interior Methods. SIAM, Philadelphia, 1997.
N. Yamashita and M. Fukushima, “On the rate of convergence of the Levenberg-Marquardt method,” Computing[Suppl], vol. 15, pp. 239–249, 2001.
Y. Ye and K. Anstreicher, “On quadratic and O(\(n\) L) convergence of a predictor-corrector algorithm for LCP,” Math. Program., vol. 62, pp. 537–552, 1993.
Y. Ye, O. Güler, R.A. Tapia, and Y. Zhang, “A quadratically convergent O(\(n\) L)-iteration algorithm for linear programming,” Math. Program., vol. 59, pp. 151–162, 1993.
Y. Zhang, R.A. Tapia, and J.E. Dennis, “On superlinear and quadratic convergence of primal-dual interior point linear programming algorithms.” SIAM J. Optim., vol. 2, pp. 304–324, 1992.
G. Zhao and J. Sun, “On the rate of local convergence of high-order infeasible-path-following algorithms for P_*-LCP with or without strictly complementary solutions,” Comput. Optim. Appl., vol. 14, pp. 293–307, 1999.
Author information
Authors and Affiliations
Corresponding author
Additional information
Mathematics Subject Classification (1991): 90C33, 65K10
This author’s work was also partially supported by the Scientific Research Foundation of Tianjin University for the Returned Overseas Chinese Scholars and the Scientific Research Foundation of Liu Hui Center for Applied Mathematics, Nankai University-Tianjin University.
Rights and permissions
About this article
Cite this article
Huang, ZH., Sun, D. & Zhao, G. A Smoothing Newton-Type Algorithm of Stronger Convergence for the Quadratically Constrained Convex Quadratic Programming. Comput Optim Applic 35, 199–237 (2006). https://doi.org/10.1007/s10589-006-6512-7
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10589-006-6512-7