Semidefinite Relaxation for Two Mixed Binary Quadratically Constrained Quadratic Programs: Algorithms and Approximation
- PDF / 595,585 Bytes
- 17 Pages / 439.37 x 666.142 pts Page_size
- 16 Downloads / 231 Views
Semidefinite Relaxation for Two Mixed Binary Quadratically Constrained Quadratic Programs: Algorithms and Approximation Bounds Zi Xu1 · Ming-Yi Hong2
Received: 20 December 2014 / Revised: 7 February 2015 / Accepted: 19 May 2015 / Published online: 8 July 2015 © Operations Research Society of China, Periodicals Agency of Shanghai University, Science Press, and Springer-Verlag Berlin Heidelberg 2015
Abstract This paper develops new semidefinite programming (SDP) relaxation techniques for two classes of mixed binary quadratically constrained quadratic programs and analyzes their approximation performance. The first class of problems finds two minimum norm vectors in N -dimensional real or complex Euclidean space, such that M out of 2M concave quadratic constraints are satisfied. By employing a special randomized rounding procedure, we show that the ratio between the norm of the optimal 2 solution of this model and its SDP relaxation is upper bounded by 54M π in the real √ case and by 24M in the complex case. The second class of problems finds a series π of minimum norm vectors subject to a set of quadratic constraints and cardinality constraints with both binary and continuous variables. We show that in this case the approximation ratio is also bounded and independent of problem dimension for both the real and the complex cases. Keywords Nonconvex quadratically constrained quadratic programming · Semidefinite program relaxation · Approximation bound · NP-hard
The first author’s research was supported by the National Natural Science Foundation of China (No. 11101261).
B
Zi Xu [email protected] Ming-Yi Hong [email protected]
1
Department of Mathematics, College of Sciences, Shanghai University, Shanghai 200444, China
2
Department of Industrial and Manufacturing Engineering, Iowa State University, Ames, IA 50011, USA
123
206
Z. Xu, M.-Y. Hong
Mathematics Subject Classification
90C22 · 90C20 · 90C59
1 Introduction In this paper, we study two classes of nonconvex mixed binary quadratically constrained quadratic programming (MBQCQP) problems, where the objective functions are quadratic in the continuous variables and the constraints contain both continuous and binary variables. These two classes of optimization problems are difficult as they are nonconvex even with the binary variables being fixed. The focus of our study is to design efficient semidefinite programming-(SDP) based algorithms for both problems and to analyze their approximation bounds. The First Model. Consider the following MBQCQP problem: min
w1 ,w2
∈F N ,β
w1 2 + w2 2
(P1)
s.t. w1H Hi w1 βi , i = 1 · · · , M, w2H Hi w2 1 − βi , i = 1 · · · , M, βi ∈ {0, 1}, i = 1, · · · , M, where F is either the field of real numbers R or the field of complex numbers C; β := (β1 , · · · , β M )T ; Hi := h i h iH (i = 1, · · · , M) and h i are N -dimensional real or complex vectors; · denotes the Euclidean norm in F N ; and M > 0 is a given integer. Throughout, we use the superscript H to denote the complex Hermitian transpose when F = C, and
Data Loading...
