Rechercher

[LEL19a] Semidefinite programming relaxations through quadratic reformulation for box-constrained polynomial optimization problems

Conférence Internationale avec comité de lecture : CODIT, April 2019, pp.1-6, Paris, France,
motcle:
Résumé: In this paper we introduce new semidefinite pro- gramming relaxations to box-constrained polynomial optimization programs (P). For this, we first reformu- late (P) into a quadratic program. More precisely, we recursively reduce the degree of (P) to two by substitut- ing the product of two variables by a new one. We ob- tain a quadratically constrained quadratic program. We build a first immediate SDP relaxation in the dimension of the total number of variables. We then strengthen the SDP relaxation by use of valid constraints that follow from the quadratization. We finally show the tightness of our relaxations through several experiments on box polynomial instances.

BibTeX

@inproceedings {
LEL19a,
title="{Semidefinite programming relaxations through quadratic reformulation for box-constrained polynomial optimization problems}",
author=" A. Lazare and S. Elloumi and A. Lambert ",
booktitle="{CODIT}",
year=2019,
month="April",
issue=2019,
pages="1-6",
address="Paris, France",
}