Decision Optimization

Hi, I have run into an issue with a QCQP where CPLEX gives "CPLEX Error 5002: objective is not convex.". However, the matrices in the problem are PSD, and any of the following modifications will result in CPLEX solving the problem without throwing an error:

• Reformulating the problem along of vein of replacing (a+b)^2 in the objective with c^2, and adding an "c = a + b" constraint
• Scaling every term in the objective down by a factor of 0.1
• Scaling every term in the objective up by a factor of 10

I am running with default CPLEX Interactive Optimizer settings, and am curious if anyone could provide some insight into this behavior.  I've boiled the problem into a small example, and have attached the original, reformulated, scaled-up, and scaled-down versions of the problem. Thanks!

------------------------------
Michael
------------------------------

#DecisionOptimization

I suspect you are dealing with rounding error issues. In your example, the Q matrix in the objective has two positive eigenvalues and one eigenvalue that equals zero ... give or take. Thanks to rounding error, CPLEX may be seeing a negative eigenvalue sufficiently different from zero to make the matrix look non-PSD. The various transformations you did would all change the eigenvalues, and apparently both scaling up and scaling down results in a third eigenvalue sufficiently close to zero to get by. So in the rounding error lottery, you were unlucky in one case and lucky in the others.

------------------------------
Paul Rubin
Professor Emeritus
Michigan State University
------------------------------

Original Message:
Sent: Tue January 12, 2021 06:05 PM
From: Michael Han
Subject: Cplex Error 5002, but problem should be solvable

Hi, I have run into an issue with a QCQP where CPLEX gives "CPLEX Error 5002: objective is not convex.". However, the matrices in the problem are PSD, and any of the following modifications will result in CPLEX solving the problem without throwing an error:

• Reformulating the problem along of vein of replacing (a+b)^2 in the objective with c^2, and adding an "c = a + b" constraint
• Scaling every term in the objective down by a factor of 0.1
• Scaling every term in the objective up by a factor of 10

I am running with default CPLEX Interactive Optimizer settings, and am curious if anyone could provide some insight into this behavior.  I've boiled the problem into a small example, and have attached the original, reformulated, scaled-up, and scaled-down versions of the problem. Thanks!

------------------------------
Michael
------------------------------

#DecisionOptimization

Thanks for your thoughts and insights Paul! Sounds very plausible to me.

------------------------------
Michael Han
------------------------------

Original Message:
Sent: Wed January 13, 2021 06:26 PM
From: Paul Rubin
Subject: Cplex Error 5002, but problem should be solvable

I suspect you are dealing with rounding error issues. In your example, the Q matrix in the objective has two positive eigenvalues and one eigenvalue that equals zero ... give or take. Thanks to rounding error, CPLEX may be seeing a negative eigenvalue sufficiently different from zero to make the matrix look non-PSD. The various transformations you did would all change the eigenvalues, and apparently both scaling up and scaling down results in a third eigenvalue sufficiently close to zero to get by. So in the rounding error lottery, you were unlucky in one case and lucky in the others.

------------------------------
Paul Rubin
Professor Emeritus
Michigan State University

Original Message:
Sent: Tue January 12, 2021 06:05 PM
From: Michael Han
Subject: Cplex Error 5002, but problem should be solvable

Hi, I have run into an issue with a QCQP where CPLEX gives "CPLEX Error 5002: objective is not convex.". However, the matrices in the problem are PSD, and any of the following modifications will result in CPLEX solving the problem without throwing an error:

• Reformulating the problem along of vein of replacing (a+b)^2 in the objective with c^2, and adding an "c = a + b" constraint
• Scaling every term in the objective down by a factor of 0.1
• Scaling every term in the objective up by a factor of 10

I am running with default CPLEX Interactive Optimizer settings, and am curious if anyone could provide some insight into this behavior.  I've boiled the problem into a small example, and have attached the original, reformulated, scaled-up, and scaled-down versions of the problem. Thanks!

------------------------------
Michael
------------------------------

#DecisionOptimization