Convex Relaxation for Solving Polynomial Programs through Quadratization Technique

Abstract:

In this paper, we study convex quadratic relaxation in polynomial programming. The goal is to solve polynomial programs through quadratic reformulation with the factorization method. The quadratization of monomials of degree more than two is carried out by replacing each pair of factors of the monomial with auxiliary variables. In this paper, each pair of factors of a monomial will be considered. The quadratic program obtained is convexified by using eigenvalues. As a result, the quadratic reformulation involving all factors of the monomial strengthens the information of the polynomial function but increases the dimensionality of the variables significantly. The next work is to develop a strategy to reduce the dimensions of the auxiliary variables.

• Periodical: Construction Technologies and Architecture (Volume 11)
• Pages: 73-77
• DOI: https://doi.org/10.4028/p-fMZqL0
• Online since: February 2024
• Authors: Lasker P. Sinaga*, Tulus Tulus, Elvina Herawati, Sawaluddin Nasution
• Keywords: Convex, Polynomial Programming, Quadratic Reformulation, Quadratization, Relaxation

References

[1] F.A. Al-Kayyal, C. Larsen, T.V. Voorhis, A relaxation method for nonconvex quadratically constrained quadratic programs, Journal of Global Optimization, 6 (1995) 215-230.

DOI: 10.1007/bf01099462

[2] X.L. Sun, J.L. Li & H.Z. Luo, Convex relaxation and lagrangian decomposition for indefinite integer quadratic programming, Optimization A Journal of Mathematical Programming and Operations Research, 59:5 (2010), 627-641.

DOI: 10.1080/02331930801987607

[3] H.D. Sherali, C.H. Tuncbilek, A global optimization algorithm for polynomial programming problems using a reformulation-linearization technique. Journal of Global Optimization 2 (1992) 101-112.

DOI: 10.1007/bf00121304

[4] E. Dalkiran, H.D. Sherali, Theoretical filtering of RLT bound-factor constraints for solving polynomial programming problems to global optimality, J. Glob Optim (2013).

DOI: 10.1007/s10898-012-0024-z

[5] E. Dalkiran, L. Ghalami, On linear programming relaxations for solving polynomial programming problems. Journal of Computer and Operational Research (2018).

DOI: 10.1016/j.cor.2018.06.010

[6] S. Elloumi, A. Lambert, A. Lazare, Solving unconstrained 0-1 polynomial programs through quadratic convex reformulation, Journal of Global Optimization, (2021).

DOI: 10.1007/s10898-020-00972-2

[7] T. Karia, C.s. Adjiman, B. Chachuat, Assesment of a two-step approach for global optimization of mixed-integer polynomial programs using quadratic reformulation. Journal of Computers and Chemical Engineering, 165 (2022) 107909.

DOI: 10.1016/j.compchemeng.2022.107909

[8] S. Elloumi, A. Lambert, A. Lazare, Semidefinite programming relaxations through quadratic reformulation for box-constrained polynomial optimization problems, International Conference on Control, Decision Information Technologies (2019).

DOI: 10.1109/codit.2019.8820690