Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



Inhomogeneous polynomial optimization over a convex set: An approximation approach

Authors: Simai He, Zhening Li and Shuzhong Zhang
Journal: Math. Comp. 84 (2015), 715-741
MSC (2010): Primary 90C26, 90C59, 65Y20, 68W25, 15A69
Published electronically: July 24, 2014
MathSciNet review: 3290961
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: In this paper, we consider computational methods for optimizing a multivariate inhomogeneous polynomial function over a general convex set. The focus is on the design and analysis of polynomial-time approximation algorithms. The methods are able to deal with optimization models with polynomial objective functions in any fixed degrees. In particular, we first study the problem of maximizing an inhomogeneous polynomial over the Euclidean ball. A polynomial-time approximation algorithm is proposed for this problem with an assured (relative) worst-case performance ratio, which is dependent only on the dimensions of the model. The method and approximation ratio are then generalized to optimize an inhomogeneous polynomial over the intersection of a finite number of co-centered ellipsoids. Furthermore, the constraint set is extended to a general convex compact set. Specifically, we propose a polynomial-time approximation algorithm with a (relative) worst-case performance ratio for polynomial optimization over some convex compact sets, e.g., a polytope. Finally, numerical results are reported, revealing good practical performance of the proposed algorithms for solving some randomly generated instances.

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


Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 90C26, 90C59, 65Y20, 68W25, 15A69

Retrieve articles in all journals with MSC (2010): 90C26, 90C59, 65Y20, 68W25, 15A69

Additional Information

Simai He
Affiliation: Department of Management Sciences, City University of Hong Kong, Hong Kong

Zhening Li
Affiliation: (corresponding author) Department of Mathematics, University of Portsmouth, Portsmouth PO1 3HF, United Kingdom

Shuzhong Zhang
Affiliation: Department of Industrial and Systems Engineering, University of Minnesota, Minneapolis, Minnesota 55455

Keywords: Polynomial optimization, approximation algorithm, inhomogeneous polynomial, tensor optimization
Received by editor(s): June 29, 2011
Received by editor(s) in revised form: September 11, 2012, and June 13, 2013
Published electronically: July 24, 2014
Additional Notes: The research of the first author was supported in part by Hong Kong GRF #CityU143711
The research of the second author was supported in part by Natural Science Foundation of China #11371242, Natural Science Foundation of Shanghai #12ZR1410100, and Ph.D. Programs Foundation of Chinese Ministry of Education #20123108120002.
The research of the third author was supported in part by National Science Foundation of USA #CMMI1161242
Article copyright: © Copyright 2014 American Mathematical Society