Basis factorization statistics

If Major print level 10, the following items are output to the PRINT file whenever the basis B or the rectangular matrix BS = (B S)T is factorized before solution of the next QP subproblem.

Note that BS may be factorized at the start of just some of  the major iterations.  It is immediately followed by a factorization of B itself.

Gaussian elimination is used to compute a sparse LU factorization of B or BS, where PLPT and PUQ are lower and upper triangular matrices for some permutation matrices P and Q.  Stability is ensured as described under LU factor tolerance in Description of optional parameters.

If  Minor print level >= 10, the same items are printed during the QP solution whenever the current B is factorized.

Label

Description

Factorize

The number of factorizations since the start of the run.

Demand

A code giving the reason for the present factorization.

 

Code

Meaning

0

First LU factorization.

1

The number of updates reached the Factorization Frequency.

2

The nonzeros in the updated factors have increased significantly.

7

Not enough storage to update factors.

10

Row residuals too large (see the description of Check Frequency).

11

Ill-conditioning has caused inconsistent results.

Iteration

The current iteration number.

Infeas

The current number of infeasibilities.

Objective

 If Infeas > 0, this is the current sum of infeasibilities.
 If Infeas = 0, it is the current QP objective function.

Nonlinear

The number of nonlinear variables in the current basis B (not printed if BS is factorized).

Linear

The number of linear variables in B (not printed if BS is factorized).

Slacks

The number of slack variables in B (not printed if BS is factorized).

Elems

The number of nonzero matrix elements in B.  (not printed if BS  is factorized).

Density

The percentage nonzero density of B, 100 x Elems/(m2), where m is the number of rows in the problem (m = Nonlinear + Linear + Slacks).

Comprssns

The number of times the data structure holding the partially factored matrix needed to be compressed to recover unused storage.  Ideally this number should be zero.  If it is more than 3 or 4, the amount of workspace available to SNOPT should be increased for efficiency.

Merit

The average Markowitz merit count for the elements chosen to be the diagonals of PUQ.  Each merit count is defined to be (c-1)(r-1) where c and r are the number of nonzeros in the column and row containing the element at the time it is selected to be the next diagonal.  Merit is the average of m such quantities.  It gives an indication of how much work was required to preserve sparsity during the factorization.

lenL

The number of nonzeros in L.  On most machines, each nonzero is represented by one 8-byte real and two 4-byte integer data types.

lenU

The number of nonzeros in U.  The storage required for each nonzero is the same as for the nonzeros of L.

Increase

The percentage increase in the number of nonzeros in L and U relative to the number of nonzeros in B;  i.e.,
                100 x (lenL + lenU - Elems)/Elems.

m

is m, the number of rows in the problem. Note that
                m = Ut + Lt + bp.

Ut

is the number of triangular rows of B  at the top of U.

d1

is the number of columns remaining when the density of the basis matrix being factorized reached 0.3.

Lmax

The maximum subdiagonal element in the columns of L.  This will be no larger than the LU factor tolerance.

Bmax

The maximum nonzero element in B.

Umax

The maximum nonzero element in U, excluding elements of B that remain in U  unaltered.  (For example, if a slack variable is in the basis, the corresponding row of B  will become a row of U  without alteration.  Elements in such rows will not contribute to Umax.  If the basis is strictly triangular, none of the elements of B  will contribute, and Umax will be zero.)

Ideally, Umax should not be substantially larger than  Bmax.  If it is several orders of magnitude larger, it may be advisable to reduce the LU factor tolerance to some value nearer 1.0.

Umax is  not printed if BS  is factorized.

Umin

The smallest diagonal element of PUQ in absolute magnitude.

Growth

The ratio Umax/Bmax, which should not be too large (see above).

As long as Lmax is not large (say 10.0 or less, max{Bmax,Umax}/Umin gives an estimate of the condition number of B.  If this number is extremely large, the basis is nearly singular and some numerical difficulties might occur.  (However, an effort is made to avoid near-singularity by using slacks to replace columns of B that would have made Umin extremely small.  Messages are issued to this effect, and the modified basis is refactored.)

Lt

is the number of triangular columns of B at the left of L.

bp

is the size of the "bump'' or block to be factorized nontrivially after the triangular rows and columns of B have been removed.

d2

is the number of columns remaining when the density of the basis matrix being factorized reached 0.6.