The cubic spherical optimization problems

Xinzhen Zhang; Liqun Qi; Yinyu Ye

doi:10.1090/S0025-5718-2012-02577-4

The cubic spherical optimization problems

Xinzhen Zhang, Liqun Qi, Yinyu Ye

Research output: Journal article publication › Journal article › Academic research › peer-review

28 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 language	English
Pages (from-to)	1513-1525
Number of pages	13
Journal	Mathematics of Computation
Volume	81
Issue number	279
DOIs	https://doi.org/10.1090/S0025-5718-2012-02577-4
Publication status	Published - 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

More information

10.1090/S0025-5718-2012-02577-4

Cite this

@article{c74716153fe545f0bb4a55d0024f1215,

title = "The cubic spherical optimization problems",

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.",

keywords = "Approximation solution, Cubic spherical optimization, Polynomial time approximation scheme (PTAS)",

author = "Xinzhen Zhang and Liqun Qi and Yinyu Ye",

year = "2012",

month = dec,

day = "14",

doi = "10.1090/S0025-5718-2012-02577-4",

language = "English",

volume = "81",

pages = "1513--1525",

journal = "Mathematics of Computation",

issn = "0025-5718",

publisher = "American Mathematical Society",

number = "279",

}

TY - JOUR

T1 - The cubic spherical optimization problems

AU - Zhang, Xinzhen

AU - Qi, Liqun

AU - Ye, Yinyu

PY - 2012/12/14

Y1 - 2012/12/14

N2 - 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.

AB - 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.

KW - Approximation solution

KW - Cubic spherical optimization

KW - Polynomial time approximation scheme (PTAS)

UR - http://www.scopus.com/inward/record.url?scp=84867295918&partnerID=8YFLogxK

U2 - 10.1090/S0025-5718-2012-02577-4

DO - 10.1090/S0025-5718-2012-02577-4

M3 - Journal article

SN - 0025-5718

VL - 81

SP - 1513

EP - 1525

JO - Mathematics of Computation

JF - Mathematics of Computation

IS - 279

ER -

The cubic spherical optimization problems

Abstract

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this