The cubic spherical optimization problems

Xinzhen Zhang, Liqun Qi, Yinyu Ye

Research output: Journal article publicationJournal articleAcademic researchpeer-review

21 Citations (Scopus)

Abstract

In this paper, the cubic spherical optimization problems, including the cubic one-spherical/two-spherical/three-spherical optimization problems, are discussed. We first show that the two-spherical optimization problem is a special case of the three-spherical optimization problem. Then we show that the one-spherical optimization problem and the two-spherical optimization problem have the same optimal value when the tensor is symmetric. In addition, NP-hardness of them are established. For the cubic three-spherical optimization problem, we discuss the conditions under which the problem is polynomial time solvable and if the polynomial time approximation scheme (PTAS) exists. Then we present a relative quality bound by finding the largest singular values of matrices. Finally, a practical method for solving the cubic three-spherical optimization problem is proposed and preliminary numerical results are reported.
Original languageEnglish
Pages (from-to)1513-1525
Number of pages13
JournalMathematics of Computation
Volume81
Issue number279
DOIs
Publication statusPublished - 14 Dec 2012

Keywords

  • Approximation solution
  • Cubic spherical optimization
  • Polynomial time approximation scheme (PTAS)

ASJC Scopus subject areas

  • Algebra and Number Theory
  • Applied Mathematics
  • Computational Mathematics

Cite this