Approximation algorithms for optimization of real-valued general conjugate complex forms
| Autor: | Zhening Li, Bo Jiang, Taoran Fu |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2018 |
| Předmět: |
Control and Optimization
tensor relaxation 0211 other engineering and technologies 010103 numerical & computational mathematics 02 engineering and technology Management Science and Operations Research 01 natural sciences complex tensor Reciprocal polynomial complex polynomial optimization Imaginary unit Hermitian function 90C59 90C26 90C10 15A69 60E15 FOS: Mathematics Applied mathematics Linear complex structure 0101 mathematics Mathematics - Optimization and Control approximation algorithm Mathematics Discrete mathematics 021103 operations research Complex conjugate Zero of a function Applied Mathematics probability bound random sampling Computing Hermitian matrix Computer Science Applications Optimization and Control (math.OC) general conjugate form Complex conjugate root theorem |
| Zdroj: | Fu, T, Jiang, B & Li, Z 2018, ' Approximation algorithms for optimization of real-valued general conjugate complex forms ', Journal of Global Optimization, vol. 70, no. 1, pp. 99-130 . https://doi.org/10.1007/s10898-017-0561-6 |
| DOI: | 10.1007/s10898-017-0561-6 |
| Popis: | Complex polynomial optimization has recently gained more attention in both theory and practice. In this paper, we study 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. The 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 to propose the first polarization formula linking general conjugate forms and complex multilinear forms. Some preliminary numerical experiments are conducted to show good performance of the proposed algorithms. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|