Here we use the augmented Lagrangian method to solve the standard LP Problem. We implement first order methods (grad / fgrad), semi-smooth Newton method and Douglas-Rachford splitting(DRS) method to solve the problem.
The dataset is generated by the following core,
n = 100;
m = 20;
A = rand(m, n);
xs = full(abs(sprandn(n, 1, m / n)));
b = A * xs;
y = randn(m, 1);
s = rand(n, 1) .* (xs == 0);
c = A' * y + s;
| objective value | time(s) | err to true sol | sqrt((Ax-b)^T(Ax-b)) | iter(outer) | |
|---|---|---|---|---|---|
| cvx-mosek | -24.736639679 | 0.62 | 3.16e-15 | 1.28e-14 | nan |
| cvx-gurobi | -24.736639679 | 0.22 | 2.22e-15 | 6.34e-15 | nan |
| mosek | -24.736639689 | 0.46 | 1.14e-07 | 6.68e-07 | nan |
| gurobi | -24.736639679 | 0.09 | 2.59e-15 | 6.22e-15 | nan |
| alm | -24.736633679 | 1.71 | 6.74e-06 | 7.48e-06 | 500 |
| alm-fgrad | -24.736639692 | 0.07 | 8.03e-09 | 6.02e-09 | 128 |
| alm-newton | -24.736639868 | 0.09 | 9.48e-09 | 9.48e-08 | 2 |
| admm | -24.736639679 | 0.25 | 7.85e-12 | 1.69e-11 | 11788 |
| drs | -24.736639682 | 0.12 | 7.75e-09 | 9.04e-09 | 10000 |
| drs-newton | -24.736639679 | 0.09 | 4.42e-09 | 1.06e-08 | 215 |
| dataset | m | n | objective ratio | time(s) | err to cvx-gurobi | pfeasibility | dfeasibility | iter(outer) |
|---|---|---|---|---|---|---|---|---|
| sebapre | 19 | 36 | -3.17e-11 | 0.02 | 5.20e-11 | 4.19e-09 | 5.57e-12 | 2 |
| sc50bpre | 34 | 90 | 4.44e-15 | 0.01 | 4.40e-15 | 5.87e-12 | 4.10e-16 | 2 |
| sc50apre | 31 | 92 | -1.48e-13 | 0.01 | 1.03e-13 | 6.51e-10 | 3.96e-13 | 4 |
| afiropre | 29 | 78 | -8.88e-16 | 0.01 | 1.96e-02 | 2.75e-12 | 1.15e-15 | 4 |
| sc105pre | 61 | 182 | 1.11e-15 | 0.04 | 9.97e-16 | 1.36e-12 | 2.78e-16 | 13 |
| beaconfdpre | 70 | 188 | -7.77e-16 | 0.18 | 3.44e-01 | 1.62e-11 | 5.40e-15 | 20 |
| vtp_basepre | 168 | 324 | -1.31e-12 | 0.68 | 3.52e-01 | 1.23e-07 | 3.70e-12 | 4 |
| sc205pre | 124 | 362 | 1.83e-12 | 1.74 | 1.80e-12 | 1.02e-07 | 4.82e-11 | 170 |
| recipepre | 177 | 380 | 3.77e-15 | 0.22 | 1.88e-01 | 3.79e-12 | 1.73e-15 | 15 |
| scagr7pre | 247 | 532 | -3.48e-08 | 7.85 | 1.41e-01 | 8.56e-08 | 5.59e-04 | 40 |
| kb2pre | 76 | 194 | -3.93e-06 | 17.64 | 6.04e-01 | 9.60e-09 | 1.15e-04 | 1001 |
| scorpionpre | 172 | 446 | -2.05e-07 | 1.23 | 1.17e+00 | 1.39e-06 | 1.09e-04 | 5 |
| stocfor1pre | 122 | 324 | 4.32e-12 | 0.36 | 9.57e-01 | 4.77e-06 | 3.16e-09 | 3 |
| adlittlepre | 162 | 482 | 4.20e-11 | 0.37 | 1.49e+00 | 7.10e-08 | 2.65e-12 | 3 |
| share2bpre | 188 | 502 | -2.54e-12 | 2.83 | 2.50e-01 | 1.74e-07 | 9.30e-13 | 12 |
| lotfipre | 480 | 1362 | 1.91e-09 | 37.40 | 2.77e-01 | 3.51e-04 | 1.28e-12 | 44 |
| standatapre | 677 | 1652 | 5.25e-12 | 19.62 | 4.92e+00 | 1.16e-05 | 7.74e-09 | 10 |
| standgubpre | 677 | 1652 | -4.91e-12 | 27.77 | 3.18e+01 | 1.10e-06 | 7.92e-10 | 11 |
| sctap1pre | 608 | 1894 | -1.79e-11 | 18.43 | 3.87e+00 | 1.74e-06 | 1.34e-09 | 12 |
| bore3dpre | 142 | 320 | -1.52e-07 | 77.04 | 6.63e-01 | 5.55e-06 | 1.12e-09 | 678 |
| scagr25pre | 949 | 2044 | -8.15e-13 | 231.54 | 1.13e-01 | 1.78e-07 | 3.46e-12 | 49 |
| boeing2pre | 374 | 884 | -1.02e-11 | 186.65 | 3.49e-01 | 4.56e-06 | 1.01e-12 | 320 |
| scsd1pre | 914 | 3194 | -2.99e-13 | 29.50 | 9.75e-01 | 3.17e-10 | 5.31e-11 | 5 |
| aggpre | 313 | 756 | -2.89e-15 | 39.81 | 9.57e-01 | 1.40e-04 | 2.14e-13 | 148 |
| brandypre | 360 | 900 | -1.11e-16 | 6.50 | 1.96e-03 | 8.56e-09 | 5.17e-13 | 17 |
| standmpspre | 1481 | 4232 | -8.76e-13 | 764.85 | 2.15e+00 | 2.32e-06 | 2.32e-08 | 140 |
| degen2pre | 1077 | 2656 | 2.83e-12 | 140.54 | 1.38e+02 | 5.60e-06 | 3.75e-09 | 14 |
| finnispre | 716 | 2038 | 2.88e-09 | 90.27 | 4.58e+00 | 9.89e-08 | 1.02e-05 | 59 |
| share1bpre | 357 | 962 | -1.92e-03 | 89.53 | 6.05e-02 | 1.82e+04 | 1.18e-02 | 101 |
| gangespre* | 1715 | 3406 | -2.16e-14 | 328.96 | 8.59e-02 | 4.45e-09 | 4.27e-13 | 9 |
| finnispre* | 716 | 2038 | 1.71e-08 | 27.06 | 8.34e-01 | 2.12e-06 | 1.15e-05 | 10 |
| capripre* | 487 | 1096 | 1.11e-12 | 93.54 | 4.23e-02 | 8.46e-08 | 2.23e-13 | 38 |
| degen2pre* | 1077 | 2656 | 8.00e-13 | 190.22 | 2.13e+02 | 3.51e-09 | 3.76e-05 | 9 |