Positive or negative semidefinite


(Meysam) #1

Hello,

The following is my code. I face the error “The second argument must be positive or negative semidefinite.” but I cannot find out the reason.

%==================== Problem data (parameters) (Beginning) ===============

Q = [ 3 11 10 14 15 16 7 15 14 4
11 2 3 11 20 8 13 5 16 6
10 3 12 11 15 19 20 12 4 4
14 11 11 17 6 18 6 17 6 20
15 20 15 6 20 8 5 6 13 10
16 8 19 18 8 4 8 18 13 12
7 13 20 6 5 8 12 19 7 16
15 5 12 17 6 18 19 10 16 9
14 16 4 6 13 13 7 16 1 12
4 6 4 20 10 12 16 9 12 8
];

A = [ 3 9 4 6 3 7 4 8 8 8
6 2 3 10 3 9 6 11 2 5
2 11 1 9 9 10 2 5 4 9
];

b = [10 ; 10 ; 10];

%==================== Problem data (parameters) (The end) =================

%==================== The mathematical model (The beginning) ==============

cvx_begin

cvx_solver SEDUMI

variable X(10) binary
variable S(3)

minimize ( X' * Q * X )

subject to:

    A * X + S == b;
    
    for i = 1 : 3
        
        S(i) >= 0;
        
    end

cvx_end


(Mark L. Stone) #2

Because Q is neither positive semidefinite nor negative semidefinite. I.e. it is indefinite, as can be seen here:

>> disp(eig(Q))
   1.0e+02 *
  -0.292121490579033
  -0.194422847511530
  -0.141823231023666
  -0.101307628064771
  -0.061104490307368
   0.057359503807591
   0.091694608967124
   0.156752638784293
   0.240100014778804
   1.134872921148557

Indeed, Q needs to be positive semidefinite so that the objective will be convex. Didn’t the error message give you a good clue what to look at?

You will also encounter an error trying to use SeDuMi to solve this, because it does not support integer (binary) variables.

Instead of the for loop, you can more simply write: S >= 0. However, the for loop is not wrong, and will not generate an error message. For large problems (which this is not), it is better to avoid for loops, if you can, for efficiency purposes.