TY - JOUR

T1 - Inhomogeneous polynomial optimization over a convex set

T2 - An approximation approach

AU - He, Simai

AU - Li, Zhening

AU - Zhang, Shuzhong

N1 - Publisher Copyright:
© 2014 American Mathematical Society.

PY - 2014

Y1 - 2014

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

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

KW - Approximation algorithm

KW - Inhomogeneous polynomial

KW - Polynomial optimization

KW - Tensor optimization

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

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

U2 - 10.1090/S0025-5718-2014-02875-5

DO - 10.1090/S0025-5718-2014-02875-5

M3 - Article

AN - SCOPUS:84919343127

SN - 0025-5718

VL - 84

SP - 715

EP - 741

JO - Mathematics of Computation

JF - Mathematics of Computation

IS - 292

ER -