MATLab-Gurobi infeasible/unbounded solution when I introduce a quadratic constraint

[Jesse Dixon]

Hi all,

I have been able to successfully solve an optimization problem of the following structure: 

min: xt*Q*x + C*x              (where xt = x transpose)

Q is 7152 by 7152

C is 7152 by 1

x is 1 by 7152

Inequality constraints:

A*x <= b

A is 17204 by 7152

b is 17204 by 1

Equality constraints:

Aeq*x = beq

Aeq is 4060 by 7152

beq is 4060 by 1

I got a solution by solving. 

Now I have entered a quadratic constraint as follows:

xt*Aquad*x = bquad

Aquad is 7160 by 7160

bquad is 7160

Since these new quadratic constraint matrices are larger than the other matrices, I had to add 8 rows/columns to each of the non-quadratic matrix (simply adding rows of zeros). This shouldn't affect the solution. 

Now that I am trying to solve, it runs around 110 iterations until it stops and says something like this: 

"Barrier performed 110 iterations in 9.37 seconds

Numerical trouble encountered

Model may be infeasible or unbounded.  Consider using the

homogeneous algorithm (through parameter 'BarHomogeneous')"

I try to take MATLabs advice, I input the following:

params.BarHomogeneous = 1;

params.method = 2;

I run it again, it doesn't seem to have changed the way that it solves. Spits out the same error. Am I doing this right? Does anyone else have experience with infeasible or unbounded solutions? 

Thanks!

[Jakob Sch.]

Hi Jesse,

gurobi can not solve equality constraints which involve quadratic terms. It should have thrown an error that the problem is non-convex... How did you input your data?

Best regards,
Jakob

[Jesse Dixon]

Jakob,

Sorry for the late reply, for some reason I never got a notification that someone replied. I had no idea that Gurobi cannot solve a quadratic equality constraint, it does not mention that anywhere. 

My input looks like this: 

model.Q = 0.5*Q_1;

model.obj = C_1;

model.A = [A_1; Aeq_1];

model.rhs = [b; beq];

model.sense = [repmat('<', size(A_1,1), 1); repmat('=', size(Aeq_1,1),1)];

model.objcon = 0;

model.quadcon.Qc = A_quadratic;

model.quadcon.q = B_quadratic;

model.quadcon.rhs = 0;

model.quadcon.sense = '=';

params.BarHomogeneous = 1;

params.method = -1; 

model.lb = -inf(size(A_1,2),1);

model.ub = inf(size(A_1,2),1);

result = gurobi(model,params);

 

[Jakob Sch.]

Hi Jesse,

The manual clearly states only quadratic constraints as inequalities (see http://www.gurobi.com/documentation/5.6/reference-manual/matlab_solving_models_with)
Note that your model statement above generates the constraint
x^T * A_quadratic * x + B_quadratic^T x <= 0

Can you write our your problem (see http://www.gurobi.com/documentation/5.6/reference-manual/matlab_gurobi_write) and post the corresponding LP file?

Best regards,
Jakob

[Jesse Dixon]

Jakob,

I changed model.quadcon.sense to '<=', it still won't solve. However, the solution that it appears to approach is smaller than the solution without the quadratic constraint (which should be impossible; the solution with the quadratic constraint should be significantly larger than without the quadratic constraints). 

I have attached the LP file. 

[Sonja Mars]

Hi,

your model has sever numerical issues and Gurobi is not able to solve it. One reason for this numerical issues is the following:

Matrix coefficient range : [ 0.333333, 2.5e+09 ]

A good rule of thumb is to try and keep all the coefficient ranges within 6 orders of magnitude. So a range like [1e-6, 1e12] would be
considered extremely large. Your range is large and you should consider rescaling your model.

Best regards,
Sonja

-----------------------------------------------------------------
Dr. Sonja Mars
Gurobi Optimization

> --
>
> ---
> You received this message because you are subscribed to the Google Groups "Gurobi Optimization" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to gurobi+un...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.
> <jesse_model.lp>