Approximation algorithms for optimization of real-valued general conjugate complex forms

DOI10.1007/S10898-017-0561-6zbMATH Open1411.90273arXiv1612.02133OpenAlexW2560362633MaRDI QIDQ683722FDOQ683722

Authors: Taoran Fu, Bo Jiang, Zhening Li 

Publication date: 9 February 2018

Published in: Journal of Global Optimization (Search for Journal in Brave)

Abstract: Complex polynomial optimization has recently gained more and more attention in both theory and practice. In this paper, we study the optimization of a real-valued general conjugate complex form over various popular constraint sets including the m-th roots of complex unity, the complex unit circle, and the complex unit sphere. A real-valued general conjugate complex form is a homogenous polynomial function of complex variables as well as their conjugates, and always takes real values. General conjugate form optimization is a wide class of complex polynomial optimization models, which include many homogenous polynomial optimization in the real domain with either discrete or continuous variables, and Hermitian quadratic form optimization as well as its higher degree extensions. All the problems under consideration are NP-hard in general and we focus on polynomial-time approximation algorithms with worst-case performance ratios. These approximation ratios improve previous results when restricting our problems to some special classes of complex polynomial optimization, and improve or equate previous results when restricting our problems to some special classes of polynomial optimization in the real domain. These algorithms are based on tensor relaxation and random sampling. Our novel technical contributions are to establish the first set of probability lower bounds for random sampling over the m-th root of unity, the complex unit circle, and the complex unit sphere, and propose the first polarization formula linking general conjugate forms and complex multilinear forms.

Full work available at URL: https://arxiv.org/abs/1612.02133

Recommendations

• Approximation methods for complex polynomial optimization
• Approximation algorithms for indefinite complex quadratic maximization problems
• An algorithm for real and complex rational minimax approximation
• Approximation Classes for Real Number Optimization Problems
• Publication:4721499
• scientific article; zbMATH DE number 3988596
• On the Computational Complexity of Approximating Solutions for Real Algebraic Formulae
• An algorithm for complex linear approximation based on semi-infinite programming
• Efficiency for a generalized form of vector optimization problems in complex space
• Unconstrained Optimization of Real Functions in Complex Variables

zbMATH Keywords

approximation algorithmrandom samplingcomplex polynomial optimizationcomplex tensorgeneral conjugate formprobability boundtensor relaxation

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Multilinear algebra, tensor calculus (15A69) Inequalities; stochastic orderings (60E15) Nonconvex programming, global optimization (90C26)

Cites Work

• Title not available (Why is that?)
• Approximation algorithms for homogeneous polynomial optimization with quadratic constraints
• Tensor principal component analysis via convex optimization
• Global optimization with polynomials and the problem of moments
• The cubic spherical optimization problems
• Deterministic approximation algorithms for sphere constrained homogeneous polynomial optimization problems
• Nonnegative Polynomial Optimization over Unit Spheres and Convex Programming Relaxations
• Handbook on semidefinite, conic and polynomial optimization
• Probability bounds for polynomial functions in random variables
• The geometric measure of multipartite entanglement and the singular values of a hypermatrix
• On approximating complex quadratic optimization problems via semidefinite programming relaxations
• Complex Quadratic Optimization and Semidefinite Programming
• Approximation algorithms for discrete polynomial optimization
• Approximation algorithms for indefinite complex quadratic maximization problems
• Convexity in SemiAlgebraic Geometry and Polynomial Optimization
• Approximation Methods for Polynomial Optimization
• An improvement of convergence rate estimates in the Lyapunov theorem
• Ambiguity Function Shaping for Cognitive Radar Via Complex Quartic Optimization
• Strong duality in lasserre's hierarchy for polynomial optimization
• MIMO Radar Waveform Optimization With Prior Information of the Extended Target and Clutter
• Linear Equations Modulo 2 and the $L_1$ Diameter of Convex Bodies
• Characterizing real-valued multivariate complex polynomials and their symmetric tensor representations
• Lasserre hierarchy for large scale polynomial optimization in real and complex variables
• Convexification of Power Flow Equations in the Presence of Noisy Measurements
• Hardness and Approximation Results for L_p-Ball Constrained Homogeneous Polynomial Optimization Problems
• Approximation methods for complex polynomial optimization

Cited In (5)

• Approximation methods for complex polynomial optimization
• On decompositions and approximations of conjugate partial-symmetric tensors
• On approximation algorithm for orthogonal low-rank tensor approximation
• Complex and quaternionic optimization
• Unconstrained Optimization of Real Functions in Complex Variables

This page was built for publication: Approximation algorithms for optimization of real-valued general conjugate complex forms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q683722)