- D.C. Versus Copositive Bounds for Standard QP Kurt Anstreicher (kurt-anstreicheruiowa.edu) Samuel Burer (samuel-bureruiowa.edu) Abstract: The standard quadratic program (QPS) is $\min_{x\in\Delta} x'Qx$, where $\Delta\subset\Re^n$ is the simplex $\Delta=\{ x\ge 0 : \sum_{i=1}^n x_i=1 \}$. QPS can be used to formulate combinatorial problems such as the maximum stable set problem, and also arises in global optimization algorithms for general quadratic programming when the search space is partitioned using simplices. One class of d.c." (for difference between convex") bounds for QPS is based on writing $Q=S-T$, where $S$ and $T$ are both positive semidefinite, and bounding $x\tran Sx$ (convex on $\Delta$) and $-x\tran Tx$ (concave on $\Delta$) separately. We show that the maximum possible such bound can be obtained by solving a semidefinite programming (SDP) problem. The dual of this SDP problem corresponds to adding a simple constraint to the well-known Shor relaxation of QPS. We show that the max d.c.bound is dominated by another known bound based on a copositive relaxation of QPS, also obtainable via SDP at comparable computational expense. For the application of QPS to bounding the stability number of a graph, we use a novel formulation of the Lovasz $\vartheta$ number to compare $\vartheta$, Schrijver's $\varthetaprime$, and the max d.c. bound. Keywords: standard quadratic programming, semidefinite programming, copositive programming, d.c. optimization Category 1: Global Optimization (Theory ) Category 2: Linear, Cone and Semidefinite Programming (Semi-definite Programming ) Citation: Dept. of Management Sciences, University of Iowa, May 2003. Download: [Postscript]Entry Submitted: 05/29/2003Entry Accepted: 05/30/2003Entry Last Modified: 05/30/2003Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Programming Society and by the Optimization Technology Center.