Conditioning theory of the equality constrained quadratic programming and its applications

ABSTRACT

Perturbation analysis of the equality constrained quadratic programming is considered. We present two different perturbation bounds to explore underlying factors for affecting the conditioning of equality constrained quadratic programming, and propose the condition numbers to give sharp forward error bounds. To improve the computational efficiency of condition numbers, some new compact forms and tight upper bounds of the condition numbers are introduced. Numerical examples are given to illustrate our theoretical results. As a special case of equality constrained quadratic programming, the rigorous perturbation analysis of Markowitz mean–variance model is also studied, which can be used to give a formal characterization of the roles of condition number and the smallest eigenvalue of the covariance matrix in bounding the forward errors. With respect to condition number and the smallest eigenvalue of the covariance matrix, numerical performances of two different covariance matrix estimators on optimal portfolio selection are also presented through simulations.

Keywords:

• Equality constrained quadratic programming
• first-order perturbation bound
• condition number
• covariance matrix estimator
• portfolio selection

MSC2010:

• 65F35
• 15A12
• 15A60

Acknowledgments

The authors would like to thank the handling editor and the anonymous referee for their invaluable suggestions and detailed comments that substantially improved the presentation of their paper.

Disclosure statement

No potential conflict of interest was reported by the authors.

ORCID

Shaoxin Wang  http://orcid.org/0000-0001-8885-8957

Notes

1 While this paper was under review, private communication with Professor Zhongxiao Jia points out that in finite precision arithmetic, when using a backward stable algorithm, e.g. the QR algorithm, to compute the largest eigenvalue of a cross-product matrix, its square root is unconditionally as accurate as the one computed by the QR algorithm applied to the matrix directly.

Additional information

Funding

The work was supported by a project of Shandong Province Higher Educational Science and Technology Program (Grant No. J17KA160) and the National Natural Science Foundation of China (Grant No. 11671059).