On approximating complex quadratic optimization problems via semidefinite programming relaxations
The paper is concerned with both a NP-hard discrete and a continuous quadratic optimization problem in the complex Hermitian form, and it provides a generic algorithm as well as a unified approach for the approximation of these problems by semidefinite programming (SDP) relaxations. An example of the studied type of discrete problem is the MAX-3-CUT problem with a positive semidefinite Laplacian matrix, and examples of the continuous problem occur in connection with robust optimization and in control theory. For the discrete problem a \((k\sin (\pi /k))^{2}/(4\pi )\)-algorithm is given under the assumptions that the decision variables are \(k\)-ary and the objective matrix is positive semidefinite. For the continuous problem with positive semidefinite objective matrix the well-known \(\pi /4\)-approximation result is obtained, however, in comparison to earlier proofs of this result, by a simpler analysis and within a more general framework for such problems. Moreover it is shown that, in the latter case, the gap between the optimal values of the given problem and its SDP relaxation can be arbitrarily close to \(\pi /4\). At last, the new approach is used to demonstrate that an \(\Omega (1/\log (n))\)-approximation algorithm can be derived when the matrix in the quadratic objective of the continuous problem is not positive semidefinite.
- On Approximating Complex Quadratic Optimization Problems via Semidefinite Programming Relaxations
- Complex Quadratic Optimization and Semidefinite Programming
- Quadratic maximization and semidefinite relaxation
- Approximation Bounds for Quadratic Optimization with Homogeneous Quadratic Constraints
- Approximation bounds for quadratic maximization and max-cut problems with semidefinite programming relaxation
- A proof of the Grothendieck inequality
- Approximating quadratic programming with bound and quadratic constraints
- Approximating the cut-norm via Grothendieck's inequality
- Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming
- Approximation algorithms for NP-hard problems.
- Complex Quadratic Optimization and Semidefinite Programming
- Extended Matrix Cube Theorems with Applications to μ-Theory in Control
- scientific article; zbMATH DE number 1534298 (Why is no real title available?)
- Improved approximation algorithms for MAX k-cut and MAX BISECTION
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- On maximization of quadratic form over intersection of ellipsoids with common center
- On the complexity of purely complex μ computation and related problems in multidimensional systems
- Quadratic forms on graphs (extended abstract)
- Semidefinite Programming
- Quadratic maximization and semidefinite relaxation
- Approximation algorithms from inexact solutions to semidefinite programming relaxations of combinatorial optimization problems
- Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming
- On decompositions and approximations of conjugate partial-symmetric tensors
- Frequency-hopping code design for Target detection via optimization theory
- Set-completely-positive representations and cuts for the max-cut polytope and the unit modulus lifting
- On the gap between the quadratic integer programming problem and its semidefinite relaxation
- Phase recovery, MaxCut and complex semidefinite programming
- On recovery guarantees for angular synchronization
- Computation of the phase and gain margins of MIMO control systems
- Characterizing real-valued multivariate complex polynomials and their symmetric tensor representations
- On quadratic programming with a ratio objective
- The Grothendieck inequality revisited
- Approximating the little Grothendieck problem over the orthogonal and unitary groups
- Biquadratic Optimization Over Unit Spheres and Semidefinite Programming Relaxations
- On Approximating Complex Quadratic Optimization Problems via Semidefinite Programming Relaxations
- scientific article; zbMATH DE number 1751736 (Why is no real title available?)
- On the estimation performance and convergence rate of the generalized power method for phase synchronization
- Tightness of a New and Enhanced Semidefinite Relaxation for MIMO Detection
- scientific article; zbMATH DE number 1833395 (Why is no real title available?)
- Hardness and Approximation Results for Lp-Ball Constrained Homogeneous Polynomial Optimization Problems
- Disentangling orthogonal matrices
- Tightness of the maximum likelihood semidefinite relaxation for angular synchronization
- Complex Quadratic Optimization and Semidefinite Programming
- A unified approach to synchronization problems over subgroups of the orthogonal group
- New semidefinite relaxations for a class of complex quadratic programming problems
- Approximation algorithms for indefinite complex quadratic maximization problems
- Moment inequalities for sums of random matrices and their applications in optimization
- Approximation algorithms for optimization of real-valued general conjugate complex forms
- Argument division based branch-and-bound algorithm for unit-modulus constrained complex quadratic programming
- Quadratic convex reformulations for a class of complex quadratic programming problems
- On approximation algorithms for commutative quaternion polynomial optimization
- Cuts and semidefinite liftings for the complex cut polytope
- Convergence of the sum-of-squares hierarchy for quadratic optimization over roots-of-unity
- Approximation methods for complex polynomial optimization
This page was built for publication: On approximating complex quadratic optimization problems via semidefinite programming relaxations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q877200)
