NL Barrier Logging#
The NL barrier log can be divided into 4 sections: the presolve section, the NL barrier preprocessing section, the NL barrier progress section, and the summary section.
Presolve Section#
The first thing the Gurobi Optimizer does when optimizing a model is to apply a presolve algorithm in order to simplify the model. The first section of the Gurobi solver log provides information on the extent to which presolve succeeds in this effort. Consider the following example output:
Presolve removed 24947 rows and 19386 columns (presolve time = 6s)...
Presolve added 1601 rows and 0 columns
Presolve removed 0 rows and 21401 columns
Presolve time: 6.28s
Presolved: 52613 rows, 81353 columns, 125535 nonzeros
Presolved model has 55 quadratic objective terms
Presolved model has 27695 quadratic constraint(s)
Presolved model has 56172 nonlinear constraint(s)
The example output shows that presolve removed 24947 and added 1601 linear constraints and 19386 variables, and it required 6.28 seconds. The next lines show the size of the model after presolve. Here, “rows” refers only to the linear constraints. This is the size of the model that is passed to the NL barrier optimizer. Note that the solution that is computed for this model is automatically transformed into a solution for the original problem once NL barrier finishes (in a process often called uncrushing), but this uncrush step is transparent and produces no log output.
NL Barrier Preprocessing Section#
The linear system solved in each iteration of the NL barrier method can be quite large and quite expensive to compute. In order to reduce the cost of this computation, the first step of the NL barrier algorithm is to compute a fill-reducing reordering of the rows and columns of the matrix in the linear system (often called the KKT matrix). This step can be quite expensive, but the cost is recouped in the lower cost of the subsequent NL barrier iterations.
Once this fill-reducing reordering has been computed, the optimizer outputs information related to the NL barrier factor matrix:
Loaded warm-start solution
Ordering time: 0.18s
NL barrier statistics:
Hessian NZ : 1.402e+05
Jacobian NZ : 4.600e+05
Factor NZ : 3.656e+06
Factor Ops : 1.725e+08
Threads : 12
These lines indicate that a starting solution was given to the NL barrier solver and that the computation of the reordering took 0.18 seconds.
The KKT matrix consists of the Hessian matrix of the Lagrangian function and the Jacobian matrix of the constraint functions. The first and second indented lines show the number of non-zero values in the respective matrices. The KKT matrix is factored in each iteration of the NL barrier algorithm, so the structure of the factors depends on the structure of the KKT matrix. The next two lines indicate the number of non-zero values in the factor matrix, and the number of floating-point operations required to factor it.
The final line shows the number of threads that will be used to perform the NL barrier iterations.
Progress Section#
The third section of the NL barrier log provides information on the progress of the NL barrier method:
Residuals
Iter Objective Primal Dual Compl Step Time
0 5.10373474e+05 9.52e+00 1.00e+02 3.88e+01 0.00e+00 7s
1 5.25565672e+05 9.31e+00 9.97e+01 3.85e+01 2.19e-02 7s
2 5.67685432e+05 8.72e+00 9.97e+01 3.82e+01 6.30e-02 7s
3 5.88102390e+05 8.42e+00 9.57e+01 3.68e+01 3.48e-02 7s
4 6.28217155e+05 7.81e+00 8.84e+01 3.41e+01 7.27e-02 7s
5 6.69337858e+05 7.16e+00 7.36e+01 2.88e+01 8.27e-02 7s
6 7.16781057e+05 6.37e+00 6.28e+01 2.48e+01 1.10e-01 7s
7 7.72856716e+05 5.41e+00 5.38e+01 2.14e+01 1.51e-01 7s
The 7 columns in each output row show the number of NL barrier iterations performed to that point, the objective value for the current NL barrier iterate, the magnitude of the primal and dual infeasibilities for the current iterate (computed as the infinity-norms of the primal and dual residual vectors, respectively), the maximum complementarity violation of the current primal and dual iterates, the step size for the Newton step (the preferred step size is 1.0), and the amount of time expended to that point (measured using wall clock time). When the primal infeasibility, dual infeasibility, and complementarity satisfy NL barrier convergence tolerances (controlled using the NLBarPFeasTol, NLBarDFeasTol, and NLBarCFeasTol parameters), the solution is declared first-order optimal and optimization is complete.
Unlike the simplex and MIP optimizers, the NL barrier optimizer produces a log line for each iterate, independent of the value of the DisplayInterval parameter.
You may sometimes see a star after the iteration count in the NL barrier progress log:
62 1.38025639e+03 1.07e-01 1.01e+08 1.01e+00 7.81e-03 0s
63 1.38021462e+03 1.07e-01 1.19e+06 9.99e-01 1.00e+00 0s
64 1.38665339e+03 1.05e-01 1.03e+08 1.01e+00 7.81e-03 0s
65* 1.38665339e+03 1.05e-01 2.47e+07 2.94e+03 0.00e+00 0s
66* 1.38662684e+03 1.02e-01 2.47e+05 4.48e+01 9.85e-01 0s
67* 1.38666633e+03 9.23e-02 1.35e+04 2.68e+01 3.97e-01 0s
68* 1.38643393e+03 8.44e-02 1.35e+04 1.58e+01 3.97e-01 0s
This indicates that the NL barrier switched into a feas relax phase that focuses on minimizing the constraint violation. This happens when little progress has been made or the model may be (locally) infeasible. Note that the algorithm might switch back again later to regular iterations and the star may disappear.
Summary Section#
The final section of the NL barrier log provides a summary of the work that the NL barrier algorithm performed, including the iteration count and the runtime, and it provides information on the outcome of the optimization. The summary for a model that is solved to first-order optimality would look like this:
NL barrier solved model in 75 iterations and 16.22 seconds (20.25 work units)
First-order optimal solution
Solution objective 1.061683572670e+06
Other termination states produce different summaries. For example, hitting an iteration limit would produce a summary that looks like:
NL barrier performed 10000 iterations in 0.25 seconds (0.11 work units)
Iteration limit reached - feasible solution found
Solution objective 8.794585517051e+01
In this example, even though the NL barrier solver did not converge, it returns the best feasible iterate that it encountered. Such an iterate is not always available.