An Implicit Evaluation Method of Vector 2-Norms Arising from Sphere Constrained Quadratic Optimizations

Abstract

An implicit evaluation method of vector 2-norms is presented for function evaluations arising from sphere constrained quadratic optimizations. The efficiency of the method in terms of computational costs mainly comes from the well-known shifted conjugate gradient method, and the robustness of the method comes from the fact that it never suffers from cancellations when the coefficient matrix is symmetric positive definite. Numerical experiments indicates that the method is promising for reducing computational costs of Ye’s hybrid method for solving sphere constrained quadratic optimizations.

Keywords

Shifted linear systems / symmetric positive definite / the shifted conjugate gradient method / sphere constrained quadratic optimizations / Ye’s hybrid method

References

[1] CONN A. R., GOULD N. & TOINT PH. L. (2000) Trust-Region Methods. Philadelphia: SIAM.

[2] DARNELL D., MORGAN R. B., & WILCOX W. (2008) Deflated GMRES for systems with multiple shifts and multiple right-hand sides Lin. Alg. Appl. 429, 2415-2434.

[3] DAVIS T. A. (2006) Direct Methods for Sparse Linear System. Philadelphia: SIAM.

[4] ESHOF J. & SLEIJPEN G. L. G. (2004) Accurate conjugate gradient methods for families of shifted linear systems. Appl. Numer. Math., 49, 17-37.

[5] FROMMER A. (2003) BiCGStab(ℓ) for families of shifted linear systems. Computing, 70, 87-109.

[6] HAGER W. W. & KRYLYUK Y. (1999) Graph partitioning and continuous quadratic pro-gramming. SIAM J. Discrete. Math., 12, 500-523.

[7] JEGERLEHNER B. (1996) Krylov space solvers for shifted linear systems. Hep-lat/9612014.

[8] MENKE W. (1989) Geophysical Data Analysis: Discrete Inverse Theory. San Diego: Academic Press.

[9] SIMONCINI V. & SZYLD D. B. (2007) Recent computational developments in Krylov Sub-space Methods for linear systems. Numer. Lin. Alg. Appl., 14, 1-59.

[10] YE Y. (1992) A new complexity result on minimization of a quadratic function with a sphere constraint. in C. Floudas and P. Pardalos eds., Recent Advances in Global Optimization. New Jersey: Princeton University Press.

[11] YUAN Y. (2000) On the truncated conjugate gradient method. Math. Program., Ser. A 87, 561-573.