Some properties of solution sets to nonconvex quadratic programming problems

Abstract

This article deals with some properties of the global minimizer set G_Q , the local minimizer set L_Q , and the stationary point set S_Q to the quadratic programming problem (Q) of minimizing the function f(x)=(1/2)x^TAx+b^Tx on the polyhedron , where , i∈I={1,2,…, m}. In particular, we investigate the intersection of these solution sets with faces and pseudofaces , where J⊂I. Some selected results are the following. If G_Q∩D_J≠ =∅ then G_Q  ∩ D_J and are relatively affine in the following sense: G_Q∩D_J =aff(G_Q∩D_J)∩D_J and . If L_Q∩D_J≠ =∅ then L_Q  ∩ D_J is open relative to aff(L_Q∩D_J)∩D_J , is open relative to , and L_Q  ∩ D_J and are convex. If G_Q∩D_J≠ =∅ then each stationary point (in particular, each local minimizer) in is a global minimizer. If x⁰∈L_Q∩D_J , , and x₀≠ = x¹ , then [x⁰,x¹)⊂L_Q∩D_J⊂L_Q . Let and denote the maximal number of nonempty faces and the maximal cardinality of an antichain of nonempty faces of a polyhedron defined as intersection of m closed halfspaces in . Then G_Q (or L_Q , or S_Q , respectively) contains a segment connecting two distinct points if it possesses more than (or , or , respectively) different points.

Keywords:

• Quadratic programming problem
• Solution set
• Global minimizer set
• Local minimizer set
• Stationary point set
• Kuhn–Tucker point

Keywords:

• Mathematics Subject Classification 2000:
• Primary: 90C20

Acknowledgment

The author would like to thank the referee for the comments.