summaryrefslogtreecommitdiff
path: root/packages/glpk/src
diff options
context:
space:
mode:
Diffstat (limited to 'packages/glpk/src')
-rw-r--r--packages/glpk/src/Numeric/LinearProgramming/L1.hs63
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
11module Numeric.LinearProgramming.L1 ( 11module 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 (
16import Numeric.LinearAlgebra 17import Numeric.LinearAlgebra
17import Numeric.LinearProgramming 18import 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@
22lInfSolveO :: Matrix Double -> Vector Double -> Vector Double 23lInfSolveO :: Matrix Double -> Vector Double -> Vector Double
23lInfSolveO a b = fromList (take n x) 24lInfSolveO 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@
38l1SolveO :: Matrix Double -> Vector Double -> Vector Double 40l1SolveO :: Matrix Double -> Vector Double -> Vector Double
39l1SolveO a b = fromList (take n x) 41l1SolveO 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@
57l1SolveU :: Matrix Double -> Vector Double -> Vector Double 59l1SolveU :: Matrix Double -> Vector Double -> Vector Double
58l1SolveU a y = fromList (take n x) 60l1SolveU 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@
74l1Solve
75 :: Double -- ^ λ
76 -> Matrix Double -- ^ A
77 -> Vector Double -- ^ b
78 -> Vector Double -- ^ x
79l1Solve λ 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@
99l1SolveGT
100 :: Double -- ^ λ
101 -> Matrix Double -- ^ A
102 -> Vector Double -- ^ b
103 -> Vector Double -- ^ x
104l1SolveGT λ 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