Tolerance and constraint parameters

Answered

Soufyan Zayou

• January 12, 2020 12:31

Hi,

I am using Gurobi and Quadprog in Matlab. I want to verify that both optimization software give me the same result. Quadprog is using the interior-point-convex and Gurobi the barrier method. I think these methods are the same, because the names are just synonyms of each other. Correct me if I am wrong, please. However, Gurobi is using other default values for the tolerance and constraint parameters then Quadprog. I found that the default value of the OptimalityTolerance is different, but I don't know which parameters I should check further and which are important. Furthermore, Quadprog is using a StepTolerance (Termination tolerance on x; a positive scalar.), but I don't know which parameter this fits from Gurobi. I have already found a list of which parameters Gurobi is using, but I am not really into it even if I read the descriptions of the parameters.

Furthermore, I am solving a MPC (Model Predictive control) QP problem with different formulations (sparse and dense) using Gurobi. The sparse formulation is gives lower computations times (using tic toc) at larger horizons then the dense formulation. This is the other way around when I am using Quadprog. Does anyone have an idea why this is the case? Could Gurobi handle sparse matrice structures much more easier then Quadprog? How could I verify that the results are good?

I would be really thankfull if someone could answer these questions. If you have any sources about this, I would also be very happy. Thanks in advance.

Kind regards,

2

• 

  Yuriy Zinchenko

  Gurobi Staff

  • February 07, 2020 00:33

  Hello Soufyan:

  the names "interior-point" and "barrier" are often synonymous when referring to optkmizaiotn algorithms, although I cannot guarantee that this is exactly what Matlab's solver is using.

  If you are solving QP with Gurobi's barrier, you may want to look into

  https://www.gurobi.com/documentation/9.0/refman/barqcpconvtol.html

  as this parameter is used to determine the convergence criterion for our barrier.

  For models where the data structures are sparse, it is often (very) advantageous to specify those as such, without the artificial step of making a full matrix filled with many 0's; indeed, linear algebra --a driving engine, so to speak-- behind the barrier is often more efficient with sparse matrices.

   

  Hope this helps,

   

  0
• 

  Soufyan Zayou

  • February 10, 2020 11:19

  

  

  

  Hello Yuriy,

  Thanks for your reply. 

  I don't really understand the last sentence of your answer: ''indeed, linear algebra --a driving engine, so to speak-- behind the barrier is often more efficient with sparse matrices.''

  Could you elaborate more on this?

  Furthermore, if I understand your answer correctly the data structures that Gurobi uses, are sparse. And due to that, it can handle sparse matrices more easy.

  Regards,

  0
• 

  Yuriy Zinchenko

  Gurobi Staff

  • February 10, 2020 18:10

  At every iteration of the barrier one solves a system of linear equations, and this is often the most expensive part.

   

  >> the data structures that Gurobi uses, are sparse

  yes, you can think of it this way.

   

  Hope this helps.

   

   

  0

Please sign in to leave a comment.