Semidefinite Relaxations, Multivariate Normal Distributions, and Order Statistics

Dimitris Bertsimas () and Yinyu Ye ()
Additional contact information
Dimitris Bertsimas: Massachusetts Institute of Technology, Sloan School of Management
Yinyu Ye: The University of Iowa, Department of Management Science

A chapter in Handbook of Combinatorial Optimization, 1998, pp 1473-1491 from Springer

Abstract: Abstract Given the symmetric matrix $$Q = \left\{ {qij} \right\} \in {R^{n \times n}}$$ and the constraint matrix $$A = \left\{ {{a_{ij}}} \right\} \in {R^{m \times n}}$$ , we consider the quadratic programming (QP) problem with linear and boolean constraints QP $$\begin{array}{l} Maximize q\left( x \right): = x'Qx\\ subject to \left| {\sum\limits_{j = 1}^n {{a_{ij}}{x_j}} } \right| = {b_i} = 1,...,m,\\ x_j^2 = 1,j = 1,...,n. \end{array}$$ Note that the constraint x j 2 =1 will force x j = 1 or x j = −1, making it a boolean variable.

Keywords: Approximation Algorithm; Quadratic Programming; Positive Semidefinite; Multivariate Normal Distribution; Semidefinite Programming (search for similar items in EconPapers)
Date: 1998
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-1-4613-0303-9_24

Ordering information: This item can be ordered from
http://www.springer.com/9781461303039

DOI: 10.1007/978-1-4613-0303-9_24

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().