Sensitivity Analysis for Degenerate Quadratic Programming

Arjan B. Berkelaar, Benjamin Jansen, Kees Roos and Tamas Terlaky

In this paper we deal with sensitivity analysis in convex quadratic programming, without making assumptions on nondegeneracy, strict convexity of the objective function, and the existence of a strictly complementary solution. We show that the optimal value as a function of a right--hand side element (or an element of the linear part of the objective) is piecewise quadratic, where the pieces can be characterized by maximal complementary solutions and tripartitions. Further, we investigate differentiability of this function. A new algorithm to compute the optimal value function is proposed. Finally, we discuss the advantages of this approach when applied to mean--variance portfolio models.

Technical Report, February, 1996.