Moment Approximations for Set-Semidefinite Polynomials
- PDF / 588,506 Bytes
- 12 Pages / 439.37 x 666.142 pts Page_size
- 31 Downloads / 219 Views
Moment Approximations for Set-Semidefinite Polynomials Peter J.C. Dickinson · Janez Povh
Received: 24 April 2012 / Accepted: 7 February 2013 © Springer Science+Business Media New York 2013
Abstract The set of polynomials that are nonnegative over a subset of the nonnegative orthant (we call them set-semidefinite) have many uses in optimization. A common example of this type set is the set of copositive matrices, where we are effectively considering nonnegativity over the entire nonnegative orthant and are restricted to homogeneous polynomials of degree two. Lasserre (SIAM J. Optim., 21(3):864–885, 2011) has previously considered a method using moments in order to provide an outer approximation to this set, for nonnegativity over a general subset of the real space. In this paper, we shall show that, in the special case of considering nonnegativity over a subset of the nonnegative orthant, we can provide a new outer approximation hierarchy. This is based on restricting moment matrices to be completely positive, and it is at least as good as Lasserre’s method. This can then be relaxed to give tractable approximations that are still at least as good as Lasserre’s method. In doing this, we also provide interesting new insights into the use of moments in constructing these approximations. Keywords Nonnegative polynomials · Set-semidefinite polynomials · Copositive programming · Doubly nonnegative matrices · Moments · Completely positive matrices
Communicated by Johannes Jahn. P.J.C. Dickinson Johann Bernoulli Institute, University of Groningen, 9700 AK Groningen, The Netherlands e-mail: [email protected] J. Povh () Faculty of information studies in Novo mesto, Ulica talcev 3, 8000 Novo mesto, Slovenia e-mail: [email protected]
J Optim Theory Appl
1 Introduction In this paper, we provide outer approximations to the set of polynomials that are nonnegative over a closed subset of the nonnegative orthant, where we may also add restrictions to the polynomials. We call such polynomials “set-semidefinite polynomials.” For example, if we restricted ourselves to homogeneous polynomials of degree 2 and consider nonnegativity over the entire nonnegative orthant, then we would, in effect, be considering the copositive cone [1–5]. Checking membership of the copositive cone is a co-N P-complete problem [6], and thus checking membership of the set that we are interested in is, in general, an N P-hard problem. This set is of especial interest in optimization due to its numerous applications [7–10], which includes reformulations of some N P-hard problems. We thus see that outer approximations to this cone are of interest for providing bounds to these problems. This set was extended in [11, 12] for nonnegativity over a general subset of the space of real vectors, whilst still being restricted to homogeneous polynomials of degree 2. This then allows for yet more applications [13, 14]. For another application of this set, we consider K being a closed subset of the nonnegative orthant, and let f be a polynomial of which we wi
Data Loading...
