Approximation methods for polynomial optimization: models, algorithms, and applications

Zhening Li, Simai He, Shuzhong Zhang

Research output: Book/ReportBook

Abstract

Polynomial optimization, as its name suggests, is used to optimize a generic multivariate polynomial function, subject to some suitable polynomial equality and/or inequality constraints. Such problem formulation dates back to the nineteenth century when the relationship between nonnegative polynomials and sum of squares (SOS) was discussed by Hilbert. Polynomial optimization is one of the fundamental problems in Operations Research and has applications in a wide range of areas, including biomedical engineering, control theory, graph theory, investment science, material science, numerical linear algebra, quantum mechanics, signal processing, speech recognition, among many others. This brief discusses some important subclasses of polynomial optimization models arising from various applications. The focus is on optimizing a high degree polynomial function over some frequently encountered constraint sets, such as the Euclidean ball, the Euclidean sphere, intersection of co-centered ellipsoids, binary hypercube, general convex compact set, and possibly a combination of the above constraints. All the models under consideration are NP-hard in general. In particular, this brief presents a study on the design and analysis of polynomial-time approximation algorithms, with guaranteed worst-case performance ratios. We aim at deriving the worst-case performance/approximation ratios that are solely dependent on the problem dimensions, meaning that they are independent of any other types of the problem parameters or input data. The new techniques can be applied to solve even broader classes of polynomial/tensor optimization models. Given the wide applicability of the polynomial optimization models, the ability to solve such models—albeit approximately—is clearly beneficial. To illustrate how such benefits might be, we present a variety of examples in this brief so as to showcase the potential applications of polynomial optimization.
Original languageEnglish
Place of PublicationNew York
PublisherSpringer
Number of pages124
ISBN (Electronic)9781461439844
ISBN (Print)9781461439837
DOIs
Publication statusPublished - 2012

Publication series

NameSpringer briefs in optimization
PublisherSpringer
ISSN (Print)2190-8354

Fingerprint

Dive into the research topics of 'Approximation methods for polynomial optimization: models, algorithms, and applications'. Together they form a unique fingerprint.

Cite this