diff options
Diffstat (limited to 'packages/glpk/src/Numeric')
-rw-r--r-- | packages/glpk/src/Numeric/LinearProgramming/L1.hs | 63 |
1 files changed, 58 insertions, 5 deletions
diff --git a/packages/glpk/src/Numeric/LinearProgramming/L1.hs b/packages/glpk/src/Numeric/LinearProgramming/L1.hs index 2e8f94a..f55c721 100644 --- a/packages/glpk/src/Numeric/LinearProgramming/L1.hs +++ b/packages/glpk/src/Numeric/LinearProgramming/L1.hs | |||
@@ -9,6 +9,7 @@ Linear system solvers in the L_1 norm using linear programming. | |||
9 | ----------------------------------------------------------------------------- | 9 | ----------------------------------------------------------------------------- |
10 | 10 | ||
11 | module Numeric.LinearProgramming.L1 ( | 11 | module Numeric.LinearProgramming.L1 ( |
12 | l1Solve, l1SolveGT, | ||
12 | l1SolveO, lInfSolveO, | 13 | l1SolveO, lInfSolveO, |
13 | l1SolveU, | 14 | l1SolveU, |
14 | ) where | 15 | ) where |
@@ -16,9 +17,9 @@ module Numeric.LinearProgramming.L1 ( | |||
16 | import Numeric.LinearAlgebra | 17 | import Numeric.LinearAlgebra |
17 | import Numeric.LinearProgramming | 18 | import Numeric.LinearProgramming |
18 | 19 | ||
19 | -- | L_Inf solution of overconstrained system Ax=b. | 20 | -- | L_inf solution of overconstrained system Ax=b. |
20 | -- | 21 | -- |
21 | -- Find argmin x ||Ax-b||_inf | 22 | -- @argmin_x ||Ax-b||_inf@ |
22 | lInfSolveO :: Matrix Double -> Vector Double -> Vector Double | 23 | lInfSolveO :: Matrix Double -> Vector Double -> Vector Double |
23 | lInfSolveO a b = fromList (take n x) | 24 | lInfSolveO a b = fromList (take n x) |
24 | where | 25 | where |
@@ -31,10 +32,11 @@ lInfSolveO a b = fromList (take n x) | |||
31 | p = Sparse (c1++c2) | 32 | p = Sparse (c1++c2) |
32 | Optimal (_j,x) = simplex (Minimize (replicate n 0 ++ [1])) p (map Free [1..(n+1)]) | 33 | Optimal (_j,x) = simplex (Minimize (replicate n 0 ++ [1])) p (map Free [1..(n+1)]) |
33 | 34 | ||
35 | -------------------------------------------------------------------------------- | ||
34 | 36 | ||
35 | -- | L_1 solution of overconstrained system Ax=b. | 37 | -- | L_1 solution of overconstrained system Ax=b. |
36 | -- | 38 | -- |
37 | -- Find argmin x ||Ax-b||_1. | 39 | -- @argmin_x ||Ax-b||_1@ |
38 | l1SolveO :: Matrix Double -> Vector Double -> Vector Double | 40 | l1SolveO :: Matrix Double -> Vector Double -> Vector Double |
39 | l1SolveO a b = fromList (take n x) | 41 | l1SolveO a b = fromList (take n x) |
40 | where | 42 | where |
@@ -49,11 +51,11 @@ l1SolveO a b = fromList (take n x) | |||
49 | p = Sparse (c1++c2) | 51 | p = Sparse (c1++c2) |
50 | Optimal (_j,x) = simplex (Minimize (replicate n 0 ++ replicate m 1)) p (map Free [1..(n+m)]) | 52 | Optimal (_j,x) = simplex (Minimize (replicate n 0 ++ replicate m 1)) p (map Free [1..(n+m)]) |
51 | 53 | ||
52 | 54 | -------------------------------------------------------------------------------- | |
53 | 55 | ||
54 | -- | L1 solution of underconstrained linear system Ax=b. | 56 | -- | L1 solution of underconstrained linear system Ax=b. |
55 | -- | 57 | -- |
56 | -- Find argmin x ||x||_1 such that Ax=b. | 58 | -- @argmin_x ||x||_1 such that Ax=b@ |
57 | l1SolveU :: Matrix Double -> Vector Double -> Vector Double | 59 | l1SolveU :: Matrix Double -> Vector Double -> Vector Double |
58 | l1SolveU a y = fromList (take n x) | 60 | l1SolveU a y = fromList (take n x) |
59 | where | 61 | where |
@@ -65,3 +67,54 @@ l1SolveU a y = fromList (take n x) | |||
65 | p = Sparse (c1 ++ c2 ++ c3) | 67 | p = Sparse (c1 ++ c2 ++ c3) |
66 | Optimal (_j,x) = simplex (Minimize (replicate n 0 ++ replicate n 1)) p (map Free [1..(2*n)]) | 68 | Optimal (_j,x) = simplex (Minimize (replicate n 0 ++ replicate n 1)) p (map Free [1..(2*n)]) |
67 | 69 | ||
70 | -------------------------------------------------------------------------------- | ||
71 | -- | Solution in the L_1 norm, with L_1 regularization, of a linear system @Ax=b@. | ||
72 | -- | ||
73 | -- @argmin_x λ||x||_1 + ||Ax-b||_1@ | ||
74 | l1Solve | ||
75 | :: Double -- ^ λ | ||
76 | -> Matrix Double -- ^ A | ||
77 | -> Vector Double -- ^ b | ||
78 | -> Vector Double -- ^ x | ||
79 | l1Solve λ a b = fromList (take n x) | ||
80 | where | ||
81 | n = cols a | ||
82 | m = rows a | ||
83 | as = toRows a | ||
84 | bs = toList b | ||
85 | c1Res = zipWith3 (mkR (1)) as bs [1..m] | ||
86 | c2Res = zipWith3 (mkR (-1)) as bs [1..m] | ||
87 | mkR sign a_i b_i k = (zipWith (#) (toList (scale sign a_i)) [1..] ++ [-1#(k+2*n)]) :<=: (sign * b_i) | ||
88 | c1Sol = map (\k -> [ 1#k, -1#k+n] :<=: 0) [1..n] | ||
89 | c2Sol = map (\k -> [-1#k, -1#k+n] :<=: 0) [1..n] | ||
90 | p = Sparse (c1Res++c2Res++c1Sol++c2Sol) | ||
91 | cost = replicate n 0 ++ replicate n λ ++ replicate m 1 | ||
92 | Optimal (_j,x) = simplex (Minimize cost) p (map Free [1..(2*n+m)]) | ||
93 | |||
94 | -------------------------------------------------------------------------------- | ||
95 | |||
96 | -- | Solution in the L_1 norm, with L_1 regularization, of a system of linear inequalities @Ax>=b@. | ||
97 | -- | ||
98 | -- @argmin_x λ||x||_1 + ||step(b-Ax)||_1@ | ||
99 | l1SolveGT | ||
100 | :: Double -- ^ λ | ||
101 | -> Matrix Double -- ^ A | ||
102 | -> Vector Double -- ^ b | ||
103 | -> Vector Double -- ^ x | ||
104 | l1SolveGT λ a b = fromList (take n x) | ||
105 | where | ||
106 | n = cols a | ||
107 | m = rows a | ||
108 | as = toRows a | ||
109 | bs = toList b | ||
110 | cRes = zipWith3 mkR as bs [1..m] | ||
111 | mkR a_i b_i k = (zipWith (#) (toList a_i) [1..] ++ [1#(k+2*n)]) :>=: (b_i) | ||
112 | c1Sol = map (\k -> [ 1#k, -1#k+n] :<=: 0) [1..n] | ||
113 | c2Sol = map (\k -> [-1#k, -1#k+n] :<=: 0) [1..n] | ||
114 | p = Sparse (cRes++c1Sol++c2Sol) | ||
115 | cost = replicate n 0 ++ replicate n λ ++ replicate m 1 | ||
116 | Optimal (_j,x) = simplex (Minimize cost) p (map Free [1..(2*n)]) | ||
117 | |||
118 | -------------------------------------------------------------------------------- | ||
119 | |||
120 | |||