| Optimization Toolbox | |
Linear Programming with Dense Columns in the Equalities
and you can load the matrices and vectors Aeq, beq, f, lb, and ub into the MATLAB workspace with
load densecolumns
The problem in densecolumns.mat has 1677 variables and 627 equalities with lower bounds on all the variables, and upper bounds on 399 of the variables. The equality matrix Aeq has dense columns among its first 25 columns, which is easy to see with a spy plot.
spy(Aeq)
You can use linprog to solve the problem.
[x,fval,exitflag,output] = ...
linprog(f,[],[],Aeq,beq,lb,ub,[],optimset('Display','iter'));
Since the iterative display was set using optimset, the results printed to the command line window are
Residuals: Primal Dual Upper Duality Total
Infeas Infeas Bounds Gap Rel
A*x-b A'*y+z-w-f {x}+s-ub x'*z+s'*w Error
----------------------------------------------------------------
Iter 0: 1.67e+003 8.11e+002 1.35e+003 5.30e+006 2.92e+001
Iter 1: 1.37e+002 1.33e+002 1.11e+002 1.27e+006 2.48e+000
Iter 2: 3.56e+001 2.38e+001 2.89e+001 3.42e+005 1.99e+000
Iter 3: 4.86e+000 8.88e+000 3.94e+000 1.40e+005 1.89e+000
Iter 4: 4.24e-001 5.89e-001 3.44e-001 1.91e+004 8.41e-001
Iter 5: 1.23e-001 2.02e-001 9.97e-002 8.41e+003 5.79e-001
Iter 6: 3.98e-002 7.91e-002 3.23e-002 4.05e+003 3.52e-001
Iter 7: 7.25e-003 3.83e-002 5.88e-003 1.85e+003 1.85e-001
Iter 8: 1.47e-003 1.34e-002 1.19e-003 8.12e+002 8.52e-002
Iter 9: 2.52e-004 3.39e-003 2.04e-004 2.78e+002 2.99e-002
Iter 10: 3.46e-005 1.08e-003 2.81e-005 1.09e+002 1.18e-002
Iter 11: 6.95e-007 1.53e-012 5.64e-007 1.48e+001 1.62e-003
Iter 12: 1.04e-006 2.26e-012 3.18e-008 8.32e-001 9.09e-005
Iter 13: 3.08e-006 1.23e-012 3.86e-009 7.26e-002 7.94e-006
Iter 14: 3.75e-007 1.09e-012 6.53e-012 1.11e-003 1.21e-007
Iter 15: 5.21e-008 1.30e-012 3.27e-013 8.62e-008 9.15e-010
Optimization terminated successfully.
You can see the returned values of exitflag, fval, and output.
exitflag =
1
fval =
9.1464e+003
output =
iterations: 15
cgiterations: 225
algorithm: 'lipsol'
This time the number of PCG iterations (in output.cgiterations) is nonzero because the dense columns in Aeq are detected. Instead of using a sparse Cholesky factorization, linprog tries to use the Sherman-Morrison formula to solve a linear system involving Aeq*Aeq'. If the Sherman-Morrison formula does not give a satisfactory residual, a PCG iteration is used. See the Main Algorithm section in Large-Scale Linear Programming.
| | Linear Programming with Equalities and Inequalities | Default Parameter Settings | |