Theoretical Background on BarHomogeneous parameter

Answered

Yannic Lieder

• February 26, 2021 23:54

We are currently writing on a paper in which we use Gurobi for optimization tasks. There is one QP that could not be solved with default parameters, failed with

Numerical trouble encountered
Model may be infeasible or unbounded. Consider using the
homogeneous algorithm (through parameter 'BarHomogeneous')) 

After setting the parameter BarHomogeneous to 1, the problem could be solved without issues (and it was neither infeasible nor unbounded). Unfortunately I couldn't find any information to this parameter except the little informative parameter description. 

The following questions arisen:

1. What is meant by the homogeneous barrier algorithm? Is there somewhere a description of this kind of algorithm?
2. I did some research to homogeneous interior point algorithms, but all I could find were papers tackling specific QP formulations (homogeneous problems), but as far as I understand is the BarHomogeneous parameter not restricted to a specific kind of formulation, but for any QP solved using the barrier algorithm?
3. In your PDF document on numerical issues, you write

   For models that are infeasible or unbounded, the default barrier algorithm may have numerical issues. Try setting BarHomogeneous=1.

   This sounds like the parameter BarHomogeneous is only useful in the case that the model is infeasible or unbounded. But in our case, it also helped solving the bounded and feasible problem. Is that correct?

4. Could you give me a reference to an essential publication regarding the homogeneous barrier algorithm?

It would be awesome, if you could answer this questions or maybe at least a few of them :)

Thanks in advance,

Yannic

1.  

0

• 

  Yuriy Zinchenko

  Gurobi Staff

  • March 01, 2021 15:43

  Hello Yannic:

  barHomogeneous = 1 parameter refers to using the so-called homogeneous self-dual embedding that amongst other things allows to set the initial point for the barrier (the other alternative is the so-called infeasible start IPM).  You can find some background here, https://pubsonline.informs.org/doi/10.1287/moor.19.1.53 and there are many other papers on the subject (LP is not very difficult to extend to SOCP).

  We typically see the homogeneous embedding as more numerically stable but a little bit more expensive computationally, so it is not used as the default setting.

  Hope this helps.

   

  0

Please sign in to leave a comment.