Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



The cubic spherical optimization problems

Authors: Xinzhen Zhang, Liqun Qi and Yinyu Ye
Journal: Math. Comp. 81 (2012), 1513-1525
MSC (2010): Primary 15A18, 15A69, 90C60
Published electronically: February 3, 2012
MathSciNet review: 2904588
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 15A18, 15A69, 90C60

Retrieve articles in all journals with MSC (2010): 15A18, 15A69, 90C60

Additional Information

Xinzhen Zhang
Affiliation: Department of Mathematics, School of Science, Tianjin University, Tianjin, 300072, China.

Liqun Qi
Affiliation: Department of Applied Mathematics, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong.

Yinyu Ye
Affiliation: Department of Management Science and Engineering, Stanford University, Stanford, CA94305 and The Hong Kong Polytechnic University, Hong Kong.

Keywords: Cubic spherical optimization, approximation solution, polynomial time approximation scheme (PTAS)
Received by editor(s): June 4, 2009
Received by editor(s) in revised form: June 2, 2011
Published electronically: February 3, 2012
Additional Notes: The first author is supported by the National Natural Science Foundation of China (Grant Nos. 11101303 and 11171180), and Independent Innovation Fund of Tianjin University
The second author is supported by the Hong Kong Research Grant Council
Article copyright: © Copyright 2012 American Mathematical Society

American Mathematical Society