biquadratic optimization

On Solving Biquadratic Optimization via Semidefinite Relaxation

  • Yuning Yang
  • Qingzhi Yang
    • Categories Semi-definite Programming Tags , , ,

    In this paper, we study a class of biquadratic optimization problems. We first relax the original problem to its semidefinite programming (SDP) problem and discuss the approximation ratio between them. Under some conditions, we show that the relaxed problem is tight. Then we consider how to approximately solve the problems in polynomial time. Under several … Read more

    Approximation algorithms for trilinear optimization with nonconvex constraints and its extensions

  • Yuning Yang
  • Qingzhi Yang
    • Categories Semi-definite Programming Tags , , , ,

    In this paper, we study trilinear optimization problems with nonconvex constraints under some assumptions. We first consider the semidefinite relaxation (SDR) of the original problem. Then motivated by So \cite{So2010}, we reduce the problem to that of determining the $L_2$-diameters of certain convex bodies, which can be approximately solved in deterministic polynomial-time. After the relaxed … Read more