Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society, the Mathematics of Computation (MCOM) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

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

The 2020 MCQ for Mathematics of Computation is 1.98.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

Inhomogeneous polynomial optimization over a convex set: An approximation approach
HTML articles powered by AMS MathViewer

by Simai He, Zhening Li and Shuzhong Zhang PDF
Math. Comp. 84 (2015), 715-741 Request permission

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
Similar Articles
Additional Information
  • Simai He
  • Affiliation: Department of Management Sciences, City University of Hong Kong, Hong Kong
  • Email: simaihe@cityu.edu.hk
  • Zhening Li
  • Affiliation: (corresponding author) Department of Mathematics, University of Portsmouth, Portsmouth PO1 3HF, United Kingdom
  • Email: zheningli@gmail.com
  • Shuzhong Zhang
  • Affiliation: Department of Industrial and Systems Engineering, University of Minnesota, Minneapolis, Minnesota 55455
  • Email: zhangs@umn.edu
  • 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
  • © Copyright 2014 American Mathematical Society
  • Journal: Math. Comp. 84 (2015), 715-741
  • MSC (2010): Primary 90C26, 90C59, 65Y20, 68W25, 15A69
  • DOI: https://doi.org/10.1090/S0025-5718-2014-02875-5
  • MathSciNet review: 3290961