Lower bounds on the global minimum of a polynomial

M. Ghasemi (), J. Lasserre and M. Marshall

Computational Optimization and Applications, 2014, vol. 57, issue 2, 387-402

Abstract: We extend the method of Ghasemi and Marshall (SIAM J. Optim. 22(2):460–473, 2012 ), to obtain a lower bound f gp,M for a multivariate polynomial $f(\mathbf{x}) \in\mathbb{R}[\mathbf {x}]$ of degree ≤2d in n variables x=(x 1 ,…,x n ) on the closed ball $\{ \mathbf{x} \in\mathbb{R}^{n} : \sum x_{i}^{2d} \le M\}$ , computable by geometric programming, for any real M. We compare this bound with the (global) lower bound f gp obtained by Ghasemi and Marshall, and also with the hierarchy of lower bounds, computable by semidefinite programming, obtained by Lasserre (SIAM J. Optim. 11(3):796–816, 2001 ). Our computations show that the bound f gp,M improves on the bound f gp and that the computation of f gp,M , like that of f gp , can be carried out quickly and easily for polynomials having of large number of variables and/or large degree, assuming a reasonable sparsity of coefficients, cases where the corresponding computation using semidefinite programming breaks down. Copyright Springer Science+Business Media New York 2014

Keywords: Positive polynomials; Sums of squares; Optimization; Geometric programming (search for similar items in EconPapers)
Date: 2014
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1007/s10589-013-9596-x (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:coopap:v:57:y:2014:i:2:p:387-402

Ordering information: This journal article can be ordered from
http://www.springer.com/math/journal/10589

DOI: 10.1007/s10589-013-9596-x

Access Statistics for this article

Computational Optimization and Applications is currently edited by William W. Hager

More articles in Computational Optimization and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().