I used the cvxopt example implementation of L1 norm minimization on
this page. fmin_cobyla
I exported the A and b (revised) matrices to CSV files and used the following script:
Code:
import argparse
import numpy as np
from l1 import l1
import cvxopt
def main():
parser = argparse.ArgumentParser(description="Find the 'x' with minimum abs error for Ax-b=0.")
parser.add_argument("a_file", help="The CSV file containing the 'A' matrix.")
parser.add_argument("b_file", help="The CSV file containing the 'b' vector.")
args = parser.parse_args()
a_mat = np.genfromtxt(args.a_file, delimiter=',')
b_vec = np.genfromtxt(args.b_file, delimiter=',')
x = l1(cvxopt.matrix(a_mat), cvxopt.matrix(b_vec))
print np.array(x)
if __name__ == '__main__':
main()
Result:
Code:
pcost dcost gap pres dres k/t
0: 8.7743e+03 2.9247e+03 6e+03 0e+00 3e-15 1e+00
1: 8.9318e+03 4.9739e+03 4e+03 1e-16 8e-15 2e+00
2: 8.3896e+03 6.1401e+03 2e+03 3e-16 5e-15 2e+00
3: 7.8324e+03 6.8913e+03 9e+02 2e-16 2e-15 1e+00
4: 7.4882e+03 7.1498e+03 3e+02 3e-16 9e-16 5e-01
5: 7.3762e+03 7.2315e+03 1e+02 2e-16 7e-16 2e-01
6: 7.3177e+03 7.2699e+03 5e+01 2e-16 1e-15 8e-02
7: 7.2992e+03 7.2823e+03 2e+01 2e-16 2e-15 3e-02
8: 7.2918e+03 7.2869e+03 5e+00 3e-16 3e-15 9e-03
9: 7.2895e+03 7.2884e+03 1e+00 2e-16 4e-15 2e-03
10: 7.2889e+03 7.2887e+03 1e-01 2e-16 3e-15 2e-04
11: 7.2888e+03 7.2888e+03 2e-02 2e-16 2e-14 5e-05
12: 7.2888e+03 7.2888e+03 6e-03 2e-16 2e-13 1e-05
Optimal solution found.
[[ 40.85472072]
[ 54.50362792]
[ 57.5105164 ]
[ 75.75089537]
[ 121.94860251]
[ 46.52666963]
[ 58.57712428]
[ 30.90475117]
[ 36.04659762]
[ 73.62493218]
[ 51.12644449]
[ 51.248826 ]
[ 42.37621978]
[ 3.94520428]
[ 78.67860326]
[ 37.77162505]
[ 38.81927895]
[ 29.40909155]
[ 44.89222214]
[ 86.02462292]
[ 64.98284056]
[ 65.17634379]
[ 78.69920606]
[ 57.15841432]
[ 57.00407176]
[ 98.82612034]
[ 35.16978323]
[ 68.48203503]
[ 91.06996332]
[ 40.08103217]
[ 56.89136308]
[ 48.42120165]
[ 30.41951755]
[ 38.14178871]
[ 38.78992582]
[ 55.06826228]
[ 23.35460718]
[ 43.32600518]
[ 46.55423128]
[ 61.66252831]
[ 31.49935873]
[ 35.06424312]
[ 96.31845687]
[ 51.16348017]
[ 53.45403994]
[ 52.65396522]
[ 42.75751957]
[ 57.49749418]
[ 108.39757194]
[ 81.67409568]
[ 53.09710197]
[ 90.24598119]
[ 66.6702275 ]
[ 46.93615142]
[ 61.9347642 ]
[ 56.08362874]
[ 19.47767745]
[ 45.29674652]
[ 47.34223078]
[ 63.39464624]
[ -48.796162 ]
[ 47.35556574]
[ 87.12906013]
[ 50.71256405]]
I also got an implementation using fmin_cobyla working, but it is much slower (and/or needs some parameter tuning). Minutes instead of sub-second. Here are the results I got from fmin_cobyla after 5000 objective function evaluations:
Code:
[ 40.85566343 54.50291262 57.51132686 74.48562198 121.75464378
46.52686084 58.57605178 30.90550162 36.04789644 73.62653722
51.12556634 51.24789644 42.37605178 3.94692557 78.67702265
37.77087379 38.81812298 29.41100324 45.26634529 86.02524272
64.98252427 65.17540453 78.69838188 57.1605178 57.0038835
98.82653722 35.16957929 67.45066719 91.06860841 40.08220065
56.89061489 48.42006472 30.42006472 38.14174757 38.78964401
55.06860841 23.35533981 43.32621359 46.55469256 61.66213592
31.49773463 35.06213592 96.31909385 51.16245955 53.45436893
52.65501618 43.26409911 57.49838188 105.8154998 81.67443366
53.09708738 90.24530744 66.67055016 46.93527508 61.93656958
56.08478964 19.47702265 45.29773463 47.34174757 56.6887101
-48.7961165 47.35469256 87.12815534 50.71132686]