Approximation bounds for trilinear and biquadratic optimization problems over nonconvex constraints (Q481050)

This paper deals with approximation bounds for trilinear and biquadratic optimization problems over nonconvex constraints. This problem is also related to other polynomial-optimization problems. To obtain the approximation bounds, the authors first consider the partial semidefinite relaxation of the original problem and show that there is a bounded approximation solution to it. This will be achieved by determining the diameters of certain convex bodies. It is shown that there is also a bounded approximation solution to the original problem via extracting the approximation solution of its semidefinite relaxation. The bounds obtained here are all new. Furthermore, approximation bounds for biquadratic optimization problems are also derived. It will be also interesting to further extend this approach to other polynomial-optimization problems.