Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2402.06336 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911774101471232 |
|---|---|
| author | González-Rodríguez, Brais Naoum-Sawaya, Joe |
| author_facet | González-Rodríguez, Brais Naoum-Sawaya, Joe |
| contents | This paper presents a new approach to quadrify a polynomial programming problem, i.e. reduce the polynomial program to a quadratic program, before solving it. The proposed approach, QUAD-RLT, exploits the Reformulation-Linearization Technique (RLT) structure to obtain smaller relaxations that can be solved faster and still provide high quality bounds. QUAD-RLT is compared to other quadrification techniques that have been previously discussed in the literature. The paper presents theoretical as well as computational results showing the advantage of QUAD-RLT compared to other quadrification techniques. Furthermore, rather than quadrifying a polynomial program, QUAD-RLT is generalized to reduce the degree of the polynomial to any degree. Computational results show that reducing the degree of the polynomial to a degree that is higher than two provides computational advantages in certain cases compared to fully quadrifying the problem. Finally, QUAD-RLT along with other quadrification/degree reduction schemes are implemented and made available in the freely available software RAPOSa. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_06336 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Degree reduction techniques for polynomial optimization problems González-Rodríguez, Brais Naoum-Sawaya, Joe Optimization and Control This paper presents a new approach to quadrify a polynomial programming problem, i.e. reduce the polynomial program to a quadratic program, before solving it. The proposed approach, QUAD-RLT, exploits the Reformulation-Linearization Technique (RLT) structure to obtain smaller relaxations that can be solved faster and still provide high quality bounds. QUAD-RLT is compared to other quadrification techniques that have been previously discussed in the literature. The paper presents theoretical as well as computational results showing the advantage of QUAD-RLT compared to other quadrification techniques. Furthermore, rather than quadrifying a polynomial program, QUAD-RLT is generalized to reduce the degree of the polynomial to any degree. Computational results show that reducing the degree of the polynomial to a degree that is higher than two provides computational advantages in certain cases compared to fully quadrifying the problem. Finally, QUAD-RLT along with other quadrification/degree reduction schemes are implemented and made available in the freely available software RAPOSa. |
| title | Degree reduction techniques for polynomial optimization problems |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2402.06336 |