I am minimising a diagonal quadratic matrix using CPLEX. All off diagonal elements are zero.

It has 500 variables and 20 linear constraints plus each variable is constrained to be within 0 and 1

All of the elements on the diagonal are greater than zero.

CPLEX complains that it is either not-optimal or unbounded depending on the values of the matrix.

I cannot see how this problem can be unbounded as it is a minimsation of a convex function. For some values CPLEX says that the solution is not optimal.

I have posted the lp file if that helps at ... http://speedy.sh/Ug76K/quadratic-fail.lp

Here is the CPLEX log

Tried aggregator 1 time.

QP Presolve eliminated 15 rows and 0 columns.

Reduced QP has 5 rows, 500 columns, and 1000 nonzeros.

Reduced QP objective Q matrix has 500 nonzeros.

Presolve time = 0.00 sec. (0.29 ticks)

Parallel mode: using up to 8 threads for barrier.

Number of nonzeros in lower triangle of A*A' = 10

Using Approximate Minimum Degree ordering

Total time for automatic ordering = 0.00 sec. (0.00 ticks)

Summary statistics for Cholesky factor:

Threads = 8

Rows in Factor = 5

Integer space required = 5

Total non-zeros in factor = 15

Total FP ops to factor = 55

Itn Primal Obj Dual Obj Prim Inf Upper Inf Dual Inf

0 2.7831848e+014 -2.7831848e+014 6.65e+001 9.07e+002 5.57e+014

1 1.8149043e+012 -1.8149043e+012 5.37e+000 7.32e+001 4.49e+013

2 1.5035906e+012 -1.5035906e+012 4.89e+000 6.67e+001 4.09e+013

3 1.1322578e+012 -1.1322578e+012 4.24e+000 5.79e+001 3.55e+013

4 7.9610680e+011 -7.9610680e+011 3.56e+000 4.85e+001 2.98e+013

5 5.5016492e+011 -5.5016491e+011 2.96e+000 4.03e+001 2.47e+013

Barrier time = 0.00 sec. (0.96 ticks)

Total time on 8 threads = 0.00 sec. (0.96 ticks)

Status = 2



Can anyone reproduce my problem using CPLEX ?

UPDATE: I have forced CPLEX to use the PRIMAL algorithm rather than the default. The optimiser now runs but I get a lot of "Markovitz threshold set to X.XX" style warnings.

  • 1
    $\begingroup$ This seems to be a CPLEX-specific problem, and is therefore better asked on a CPLEX-specific mailing list or forum. (Also, it seems you have already found the solution: stackoverflow.com/questions/24739207/…) $\endgroup$ Aug 12 '14 at 17:17

Your problem seems quite easy indeed. I tried MOSEK, another convex optimizer, instead of CPLEX and it solves in almost no time (see the log at the end).

The problem is well scaled and thee is no evident reasons for CPLEX to get fooled. My guess is that it is not able to certify optimality. Unboundness shouldn't be the issue.

MOSEK Version (Build date: 2014-4-27 19:30:42) Copyright (c) 1998-2014 MOSEK ApS, Denmark. WWW: http://mosek.com

Open file 'quadratic_fail.lp'

Read summary Type : QO (quadratic optimization problem) Objective sense : min Constraints : 20
Scalar variables : 500
Matrix variables : 0
Time : 0.0

Computer Platform : Linux/64-X86
Cores : 2

Problem Name :
Objective sense : min
Type : QO (quadratic optimization problem) Constraints : 20
Cones : 0
Scalar variables : 500
Matrix variables : 0
Integer variables : 0

Optimizer started. Interior-point optimizer started. Presolve started. Linear dependency checker started. Linear dependency checker terminated. Eliminator - tries : 0 time : 0.00
Eliminator - elim's : 0
Lin. dep. - tries : 1 time : 0.00
Lin. dep. - number : 0
Presolve terminated. Time: 0.00
Matrix reordering started. Local matrix reordering started. Local matrix reordering terminated. Matrix reordering terminated. Optimizer - threads : 2
Optimizer - solved problem : the primal
Optimizer - Constraints : 5 Optimizer - Cones : 0 Optimizer - Scalar variables : 505 conic : 0
Optimizer - Semi-definite variables: 0 scalarized : 0
Factor - setup time : 0.00 dense det. time : 0.00
Factor - ML order time : 0.00 GP order time : 0.00
Factor - nonzeros before factor : 15 after factor : 15
Factor - dense dim. : 0 flops : 0.00e+00
0 1.0e+02 1.1e+03 2.0e+04 0.00e+00 9.762500000e+03 -9.762500000e+03 1.0e+00 0.00
1 2.5e+00 2.7e+01 1.3e+03 -8.24e-01 1.461547953e+03 -1.063368559e+04 1.1e-01 0.01
2 2.1e+00 2.3e+01 1.2e+03 5.90e-01 1.926066470e+03 -1.046829917e+04 1.0e-01 0.01
3 1.3e+00 1.3e+01 7.0e+02 5.10e-01 2.077327854e+03 -6.495728296e+03 6.0e-02 0.01
4 5.2e-01 5.6e+00 3.4e+02 4.24e-01 3.416151322e+03 -2.006514499e+03 2.8e-02 0.01
5 6.6e-02 7.0e-01 8.7e+01 6.41e-01 4.786227760e+03 3.147891392e+03 5.9e-03 0.01
6 6.3e-03 6.7e-02 1.4e+01 9.60e-01 4.744795814e+03 4.485405619e+03 8.3e-04 0.01
7 8.3e-06 8.8e-05 7.6e-01 9.98e-01 4.726819747e+03 4.712348560e+03 3.9e-05 0.01
8 8.0e-07 8.4e-06 1.3e-01 1.00e+00 4.723211688e+03 4.720790746e+03 6.6e-06 0.01
9 2.8e-09 3.0e-08 8.7e-03 1.00e+00 4.722531001e+03 4.722365208e+03 4.5e-07 0.01
10 1.7e-12 1.9e-11 5.5e-04 1.00e+00 4.722481461e+03 4.722470859e+03 2.9e-08 0.01
11 3.5e-15 5.9e-14 3.3e-05 1.00e+00 4.722478119e+03 4.722477487e+03 1.7e-09 0.01
12 5.7e-16 1.1e-13 1.7e-06 1.00e+00 4.722477945e+03 4.722477912e+03 8.9e-11 0.01
Interior-point optimizer terminated. Time: 0.01.

Optimizer terminated. Time: 0.03

Interior-point solution summary Problem status : PRIMAL_AND_DUAL_FEASIBLE Solution status : OPTIMAL Primal. obj: 4.7224779451e+03 Viol. con: 2e-16 var: 0e+00
Dual. obj: 4.7224779122e+03 Viol. con: 4e-12 var: 4e-13

  • $\begingroup$ Thanks. As expected there is no problem with this problem. I am not using any special settings for CPLEX and given the problem I am amazed that it does not work. $\endgroup$
    – Dom
    Jul 13 '14 at 9:09
  • $\begingroup$ Well, numerical algorithms are not perfect! I can not say anything about what CPLEX does or why it doesn't work. As my nickname may suggest, I work for MOSEK...and I know from experience that sometimes even for small problems a solver can fail. $\endgroup$ Jul 13 '14 at 15:56
  • $\begingroup$ I accept that solvers cannot be perfect. But the fact that it is a diagonal positive definite problem made think it was very solvable. I am running my optimiser within a Monte Carlo simulator and it works 99% of the time. I may look at Mosek. $\endgroup$
    – Dom
    Jul 13 '14 at 18:26
  • $\begingroup$ Solution here ibm.com/developerworks/community/forums/html/… $\endgroup$
    – Dom
    Aug 3 '14 at 16:45

Not the answer you're looking for? Browse other questions tagged or ask your own question.