2014/03/17 by Zi Xu, Mingyi Hong, Xu, Zi +1
Computer Science · Engineering · Mathematics · #Advanced Control Systems Optimization #Advanced Optimization Algorithms Research #FOS: Mathematics #Optimization and Control (math.OC) #Optimization and Variational Analysis
paper · pdf · doi:10.48550/arxiv.1403.3998
openalex publication_date 2014/03/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This paper develops new semidefinite programming (SDP) relaxation techniques for two classes of mixed binary quadratically constrained quadratic programs (MBQCQP) and analyzes their approximation performance. The first class of problem finds two minimum norm vectors in N-dimensional real or complex Euclidean space, such that M out of 2M concave quadratic functions are satisfied. By employing a special randomized rounding procedure, we show that the ratio between the norm of the optimal solution of this model and its SDP relaxation is upper bounded by \frac54M2π in the real case and by (24M)/(√π) in the complex case. The second class of problem finds a series of minimum norm vectors subject to a set of quadratic constraints and a cardinality constraint 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.