diff options
author | Alberto Ruiz <aruiz@um.es> | 2014-06-12 14:13:05 +0200 |
---|---|---|
committer | Alberto Ruiz <aruiz@um.es> | 2014-06-12 14:13:05 +0200 |
commit | 302a220b636d510ccf654e3671e8a93391c13523 (patch) | |
tree | 65380fdbaaa22ceadde5fabee645fd0ada3a218a /packages/glpk | |
parent | ab6d7efb73bcfa3b331cc7f2abce75430f7cff09 (diff) |
add L1 and LInf solvers
Diffstat (limited to 'packages/glpk')
-rw-r--r-- | packages/glpk/hmatrix-glpk.cabal | 5 | ||||
-rw-r--r-- | packages/glpk/src/C/glpk.c (renamed from packages/glpk/lib/Numeric/LinearProgramming/glpk.c) | 0 | ||||
-rw-r--r-- | packages/glpk/src/Numeric/LinearProgramming.hs (renamed from packages/glpk/lib/Numeric/LinearProgramming.hs) | 0 | ||||
-rw-r--r-- | packages/glpk/src/Numeric/LinearProgramming/L1.hs | 67 |
4 files changed, 70 insertions, 2 deletions
diff --git a/packages/glpk/hmatrix-glpk.cabal b/packages/glpk/hmatrix-glpk.cabal index 5f3b34e..533ee2d 100644 --- a/packages/glpk/hmatrix-glpk.cabal +++ b/packages/glpk/hmatrix-glpk.cabal | |||
@@ -24,11 +24,12 @@ extra-source-files: examples/simplex1.hs | |||
24 | library | 24 | library |
25 | Build-Depends: base, hmatrix | 25 | Build-Depends: base, hmatrix |
26 | 26 | ||
27 | hs-source-dirs: lib | 27 | hs-source-dirs: src |
28 | 28 | ||
29 | Exposed-modules: Numeric.LinearProgramming | 29 | Exposed-modules: Numeric.LinearProgramming |
30 | Numeric.LinearProgramming.L1 | ||
30 | 31 | ||
31 | c-sources: lib/Numeric/LinearProgramming/glpk.c | 32 | c-sources: src/C/glpk.c |
32 | 33 | ||
33 | ghc-options: -Wall | 34 | ghc-options: -Wall |
34 | 35 | ||
diff --git a/packages/glpk/lib/Numeric/LinearProgramming/glpk.c b/packages/glpk/src/C/glpk.c index bfbb435..bfbb435 100644 --- a/packages/glpk/lib/Numeric/LinearProgramming/glpk.c +++ b/packages/glpk/src/C/glpk.c | |||
diff --git a/packages/glpk/lib/Numeric/LinearProgramming.hs b/packages/glpk/src/Numeric/LinearProgramming.hs index 25cdab2..25cdab2 100644 --- a/packages/glpk/lib/Numeric/LinearProgramming.hs +++ b/packages/glpk/src/Numeric/LinearProgramming.hs | |||
diff --git a/packages/glpk/src/Numeric/LinearProgramming/L1.hs b/packages/glpk/src/Numeric/LinearProgramming/L1.hs new file mode 100644 index 0000000..2e8f94a --- /dev/null +++ b/packages/glpk/src/Numeric/LinearProgramming/L1.hs | |||
@@ -0,0 +1,67 @@ | |||
1 | {- | | ||
2 | Module : Numeric.LinearProgramming.L1 | ||
3 | Copyright : (c) Alberto Ruiz 2011-14 | ||
4 | Stability : provisional | ||
5 | |||
6 | Linear system solvers in the L_1 norm using linear programming. | ||
7 | |||
8 | -} | ||
9 | ----------------------------------------------------------------------------- | ||
10 | |||
11 | module Numeric.LinearProgramming.L1 ( | ||
12 | l1SolveO, lInfSolveO, | ||
13 | l1SolveU, | ||
14 | ) where | ||
15 | |||
16 | import Numeric.LinearAlgebra | ||
17 | import Numeric.LinearProgramming | ||
18 | |||
19 | -- | L_Inf solution of overconstrained system Ax=b. | ||
20 | -- | ||
21 | -- Find argmin x ||Ax-b||_inf | ||
22 | lInfSolveO :: Matrix Double -> Vector Double -> Vector Double | ||
23 | lInfSolveO a b = fromList (take n x) | ||
24 | where | ||
25 | n = cols a | ||
26 | as = toRows a | ||
27 | bs = toList b | ||
28 | c1 = zipWith (mk (1)) as bs | ||
29 | c2 = zipWith (mk (-1)) as bs | ||
30 | mk sign a_i b_i = (zipWith (#) (toList (scale sign a_i)) [1..] ++ [-1#(n+1)]) :<=: (sign * b_i) | ||
31 | p = Sparse (c1++c2) | ||
32 | Optimal (_j,x) = simplex (Minimize (replicate n 0 ++ [1])) p (map Free [1..(n+1)]) | ||
33 | |||
34 | |||
35 | -- | L_1 solution of overconstrained system Ax=b. | ||
36 | -- | ||
37 | -- Find argmin x ||Ax-b||_1. | ||
38 | l1SolveO :: Matrix Double -> Vector Double -> Vector Double | ||
39 | l1SolveO a b = fromList (take n x) | ||
40 | where | ||
41 | n = cols a | ||
42 | m = rows a | ||
43 | as = toRows a | ||
44 | bs = toList b | ||
45 | ks = [1..] | ||
46 | c1 = zipWith3 (mk (1)) as bs ks | ||
47 | c2 = zipWith3 (mk (-1)) as bs ks | ||
48 | mk sign a_i b_i k = (zipWith (#) (toList (scale sign a_i)) [1..] ++ [-1#(k+n)]) :<=: (sign * b_i) | ||
49 | p = Sparse (c1++c2) | ||
50 | Optimal (_j,x) = simplex (Minimize (replicate n 0 ++ replicate m 1)) p (map Free [1..(n+m)]) | ||
51 | |||
52 | |||
53 | |||
54 | -- | L1 solution of underconstrained linear system Ax=b. | ||
55 | -- | ||
56 | -- Find argmin x ||x||_1 such that Ax=b. | ||
57 | l1SolveU :: Matrix Double -> Vector Double -> Vector Double | ||
58 | l1SolveU a y = fromList (take n x) | ||
59 | where | ||
60 | n = cols a | ||
61 | c1 = map (\k -> [ 1#k, -1#k+n] :<=: 0) [1..n] | ||
62 | c2 = map (\k -> [-1#k, -1#k+n] :<=: 0) [1..n] | ||
63 | c3 = zipWith (:==:) (map sp $ toRows a) (toList y) | ||
64 | sp v = zipWith (#) (toList v) [1..] | ||
65 | p = Sparse (c1 ++ c2 ++ c3) | ||
66 | Optimal (_j,x) = simplex (Minimize (replicate n 0 ++ replicate n 1)) p (map Free [1..(2*n)]) | ||
67 | |||