QP Hessian is not positive semi-definite.

[lin jiaxin]

Hi All,

I am new to AMPL and could not identify why my code below receives QP Hessian is not positive semi-definite.

Your help is much appreciated

param m;

param n;

param o;

set I={1..m};#large ship

set J={1..n}; #base

set K={1..o}; #small ship

param a{1..m};

var x{I,J} integer >=0 ; 

var y{K,J} integer >=0 ; 

var s{K} integer >=0 ; 

var l{I} integer >=0 ;

minimize z: sum {i in I,k in K}

((s[k]*(2.5*a[k]+4700))+(l[i]*(3*a[i]+11000)));

subject to

ConstraintType1:

(sum {k in K} s[k])<=7;

ConstraintType2:

(sum {i in I} l[i])<=5;

ConstraintType3 {k in K, j in J}:

y[k,j]<=200;

ConstraintType4 {i in I, j in J}:

x[i,j]<=500;

ConstraintType5:

(y[1,1]*s[1]+y[2,1]*s[2]+y[6,1]*s[6]+x[1,1]*l[1]+x[2,1]*l[2]+x[6,1]*l[6]+x[7,1]*l[7])>=1000;

ConstraintType6:

(y[2,2]*s[2]+y[3,2]*s[3]+y[4,2]*s[4]+x[2,2]*l[2]+x[3,2]*l[3]+x[4,2]*l[4]+x[7,2]*l[7])>=600;

ConstraintType7:

(y[3,3]*s[3]+y[5,3]*s[5]+y[6,3]*s[6]+x[3,3]*l[3]+x[5,3]*l[5]+x[6,3]*l[6]+x[7,3]*l[7])>=700;

data;

param m:=7;

param n:=3;

param o:=6;

param a:= 1 350 2 515 3 665 4 450 5 600 6 650 7 720;

option solver cplex; solve;

display z,x,y,s,l;

[Robert Fourer]

Your problem is a QP (quadratic program) -- it has quadratic terms like y[1,1]*s[1] and x[7,1]*l[7] in the constraints. However, CPLEX can only handle certain convex quadratic constraints. The "QP Hessian is not positive semi-definite" message is basically telling you that your constraint has not passed CPLEX's convexity test, and so your problem cannot be solved by CPLEX.

Since your s and l variables are small integers, you could express them as sums of zero-one variables -- for example, in place of s[k], use s1[k] + 2*s2[k] + 4*s3[k] where s1, s2, s3 are zero-one. Then in your constraints you would have products of zero-one variables and other variables, which can be linearized as described for example at https://orinanobworld.blogspot.com/2010/10/binary-variables-and-quadratic-terms.html. This will make your model bigger and more complicated, however.

Another option is to use BARON (http://ampl.com/products/solvers/solvers-we-sell/baron/) or Couenne (http://ampl.com/products/solvers/open-source/) which can find globally optimal solutions to various nonlinear problems with integer variables. I found that for your problem, BARON worked quite well; Couenne found the optimal solution but was having trouble proving optimality when I stopped it.

Bob Fourer
am...@googlegroups.com

=======

From: am...@googlegroups.com [mailto:am...@googlegroups.com] On Behalf Of lin jiaxin
Sent: Wednesday, October 25, 2017 12:19 PM
To: AMPL Modeling Language
Subject: [AMPL 14959] QP Hessian is not positive semi-definite.

I am new to AMPL and could not identify why my code below receives QP Hessian is not positive semi-definite.
Your help is much appreciated

...

var x{I,J} integer >=0 ;
var y{K,J} integer >=0 ;
var s{K} integer >=0 ;
var l{I} integer >=0 ;

...