Semidefinite approximation for mixed binary quadratically constrained quadratic programs

来源 :Shanghai Workshop on Numerical Algebra,Imaging and Optimizat | 被引量 : 0次 | 上传用户:gaolch014
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
Motivated by applications in wireless communications,this paper develops semidefinite programming(SDP)relaxation techniques for some mixed binary quadratically constrained quadratic programs(MBQCQP)and analyzes their approximation performance.We consider both a minimization and a maximization model of this problem.For the minimization model,the objective is to find a minimum norm vector in $N$-dimensional real or complex Euclidean space,such that $M$ concave quadratic constraints and a cardinality constraint are satisfied with both binary and continuous variables.By employing a special randomized rounding procedure,we show that the ratio between the norm of the optimal solution of the minimization model and its SDP relaxation is upper bounded by $O(Q^2(M-Q+1)+M^2)$ in the real case and by $O(M(M-Q+1))$ in the complex case.For the maximization model,the goal is to find a maximum norm vector 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 bounded from below by $O(\epsilon∧ln(M))$ for both the real and the complex cases.Moreover,this ratio is tight up to a constant factor.
其他文献
  The Projected Shell Model has been developed by including various intrinsic deformations in the configuration space.In this new method,the quadrupole deform
会议
质子发射核为研究质子滴线附近的核结构提供了重要信息[1].1981年,在德国GSI的SHIP的速度选择器上,发现了第一个基态质子发射核151Lu.近期又发现151Lu存在一个短寿命的低自旋
会议
I shall discuss issues related to the level surfaces and singular sets for solutions to semilinear problems of the type $Delta u = f(u)$,where $f$ admits disco
会议
In this talk,we study some mathematical aspects on supersonic flow past a delta wing.Here the wing is assumed to be infinite along its edges,so we need only to
会议
We survey some of our recent progress on the local well-posedness problem for compressible Navier-Stokes Equations with density dependent viscosity when initial
会议
  The Boltzmann equation can describe the gas transport phenomena for the full spectrum of flow regimes and act as the main foundation for the study of comple
会议
  In this talk,I will introduce the Wigner transport equation(WTE),which can be regarded as a quantum correction of the Boltzmann equation.The WTE has found m
会议
  We consider the Navier-Stokes Equations with Navier boundary condition.We get a strong convergence of Navier-Stokes Equations with Navier boundary condition
会议
  Time-dependent neutron transport equation is a kind of important hyperbolic partial differential equation in nuclear science and engineering applications.Hi
Kernel functions play an important role in the design and analysis of interior-point methods(IPMs).They are not only used for determining the search directions
会议