On the stability of solutions to quadratic programming problems

Abstract.

We consider the parametric programming problem (Q _p ) of minimizing the quadratic function f(x,p):=x ^T Ax+b ^T x subject to the constraint Cx≤d, where x∈ℝⁿ, A∈ℝ^n×n, b∈ℝⁿ, C∈ℝ^m×n, d∈ℝ^m, and p:=(A,b,C,d) is the parameter. Here, the matrix A is not assumed to be positive semidefinite. The set of the global minimizers and the set of the local minimizers to (Q _p ) are denoted by M(p) and M ^loc(p), respectively. It is proved that if the point-to-set mapping M ^loc(·) is lower semicontinuous at p then M ^loc(p) is a nonempty set which consists of at most ? _m,n points, where ? _m,n =$\binom{m}{{\text{min}}\{[m/2],n\}}$ is the maximal cardinality of the antichains of distinct subsets of {1,2,...,m} which have at most n elements. It is proved also that the lower semicontinuity of M(·) at p implies that M(p) is a singleton. Under some regularity assumption, these necessary conditions become the sufficient ones.