A dynamic inequality generation scheme for polynomial programming

B. Ghaddar, J.C. Vera Lizcano, M.F. Anjos

Research output: Contribution to journalArticleScientificpeer-review

Abstract

Hierarchies of semidefinite programs have been used to approximate or even solve polynomial programs. This approach rapidly becomes computationally expensive and is often tractable only for problems of small size. In this paper, we propose a dynamic inequality generation scheme to generate valid polynomial inequalities for general polynomial programs. When used iteratively, this scheme improves the bounds without incurring an exponential growth in the size of the relaxation. As a result, the proposed scheme is in principle scalable to large general polynomial programming problems. When all the variables of the problem are non-negative or when all the variables are binary, the general algorithm is specialized to a more efficient algorithm. In the case of binary polynomial programs, we show special cases for which the proposed scheme converges to the global optimal solution. We also present several examples illustrating the computational behavior of the scheme and provide comparisons with Lasserre’s approach and, for the binary linear case, with the lift-and-project method of Balas, Ceria, and Cornuejols.
Original languageEnglish
Pages (from-to)21-57
JournalMathematical Programming
Volume156
Issue number1
Early online date2016
DOIs
Publication statusPublished - Mar 2016

Fingerprint

Programming
Polynomials
Polynomial
Binary
Lift-and-project
Semidefinite Program
Cerium compounds
Exponential Growth
Efficient Algorithms
Optimal Solution
Non-negative
Valid
Converge

Keywords

  • polynomial programming
  • binary polynomial programming
  • semidefinite programming
  • inequality generation

Cite this

@article{6b2846e355274462b1726fe9f1621e23,
title = "A dynamic inequality generation scheme for polynomial programming",
abstract = "Hierarchies of semidefinite programs have been used to approximate or even solve polynomial programs. This approach rapidly becomes computationally expensive and is often tractable only for problems of small size. In this paper, we propose a dynamic inequality generation scheme to generate valid polynomial inequalities for general polynomial programs. When used iteratively, this scheme improves the bounds without incurring an exponential growth in the size of the relaxation. As a result, the proposed scheme is in principle scalable to large general polynomial programming problems. When all the variables of the problem are non-negative or when all the variables are binary, the general algorithm is specialized to a more efficient algorithm. In the case of binary polynomial programs, we show special cases for which the proposed scheme converges to the global optimal solution. We also present several examples illustrating the computational behavior of the scheme and provide comparisons with Lasserre’s approach and, for the binary linear case, with the lift-and-project method of Balas, Ceria, and Cornuejols.",
keywords = "polynomial programming, binary polynomial programming, semidefinite programming, inequality generation",
author = "B. Ghaddar and {Vera Lizcano}, J.C. and M.F. Anjos",
year = "2016",
month = "3",
doi = "10.1007/s10107-015-0870-9",
language = "English",
volume = "156",
pages = "21--57",
journal = "Mathematical Programming",
issn = "0025-5610",
publisher = "Springer",
number = "1",

}

A dynamic inequality generation scheme for polynomial programming. / Ghaddar, B.; Vera Lizcano, J.C.; Anjos, M.F.

In: Mathematical Programming, Vol. 156, No. 1, 03.2016, p. 21-57.

Research output: Contribution to journalArticleScientificpeer-review

TY - JOUR

T1 - A dynamic inequality generation scheme for polynomial programming

AU - Ghaddar, B.

AU - Vera Lizcano, J.C.

AU - Anjos, M.F.

PY - 2016/3

Y1 - 2016/3

N2 - Hierarchies of semidefinite programs have been used to approximate or even solve polynomial programs. This approach rapidly becomes computationally expensive and is often tractable only for problems of small size. In this paper, we propose a dynamic inequality generation scheme to generate valid polynomial inequalities for general polynomial programs. When used iteratively, this scheme improves the bounds without incurring an exponential growth in the size of the relaxation. As a result, the proposed scheme is in principle scalable to large general polynomial programming problems. When all the variables of the problem are non-negative or when all the variables are binary, the general algorithm is specialized to a more efficient algorithm. In the case of binary polynomial programs, we show special cases for which the proposed scheme converges to the global optimal solution. We also present several examples illustrating the computational behavior of the scheme and provide comparisons with Lasserre’s approach and, for the binary linear case, with the lift-and-project method of Balas, Ceria, and Cornuejols.

AB - Hierarchies of semidefinite programs have been used to approximate or even solve polynomial programs. This approach rapidly becomes computationally expensive and is often tractable only for problems of small size. In this paper, we propose a dynamic inequality generation scheme to generate valid polynomial inequalities for general polynomial programs. When used iteratively, this scheme improves the bounds without incurring an exponential growth in the size of the relaxation. As a result, the proposed scheme is in principle scalable to large general polynomial programming problems. When all the variables of the problem are non-negative or when all the variables are binary, the general algorithm is specialized to a more efficient algorithm. In the case of binary polynomial programs, we show special cases for which the proposed scheme converges to the global optimal solution. We also present several examples illustrating the computational behavior of the scheme and provide comparisons with Lasserre’s approach and, for the binary linear case, with the lift-and-project method of Balas, Ceria, and Cornuejols.

KW - polynomial programming

KW - binary polynomial programming

KW - semidefinite programming

KW - inequality generation

U2 - 10.1007/s10107-015-0870-9

DO - 10.1007/s10107-015-0870-9

M3 - Article

VL - 156

SP - 21

EP - 57

JO - Mathematical Programming

JF - Mathematical Programming

SN - 0025-5610

IS - 1

ER -