Debian Codegraph @

Formal_ineqs/informal/informal_search.hl

raw
1 (* ========================================================================== *)
2 (* Formal verification of nonlinear inequalities in HOL Light *)
3 (* *)
4 (* Copyright (c) 2014 Alexey Solovyev *)
5 (* *)
6 (* This file is distributed under the terms of the MIT licence *)
7 (* ========================================================================== *)
8
9 (* -------------------------------------------------------------------------- *)
10 (* Informal certificate search *)
11 (* -------------------------------------------------------------------------- *)
12
13 needs "Formal_ineqs/informal/informal_taylor.hl";;
14 needs "Formal_ineqs/verifier/certificate.hl";;
15 needs "Formal_ineqs/verifier_options.hl";;
16
17 module Informal_search = struct
18
19 open List;;
20 open Informal_float;;
21 open Informal_interval;;
22 open Informal_taylor;;
23 open Certificate;;
24 open Verifier_options;;
25
26 type search_options = {
27 raw_intervals0 : bool;
28 max_width : float;
29 max_depth : int;
30 mono_depth : int;
31 pp : int;
32 };;
33
34
35 (* Returns the maximum element of s and its index *)
36 let find_max s =
37 let rec find m mi i s =
38 match s with
39 | [] -> m, mi
40 | x :: t ->
41 if x > m then
42 find x i (i + 1) t
43 else
44 find m mi (i + 1) t in
45 find (hd s) 0 1 (tl s);;
46
47 (* split_domain *)
48 let split_domain pp j domain =
49 let n = length domain.w in
50 let t = nth domain.y (j - 1) in
51 let vv = map (fun i -> if i = j then t else nth domain.hi (i - 1)) (1--n) in
52 let uu = map (fun i -> if i = j then t else nth domain.lo (i - 1)) (1--n) in
53 mk_m_center_domain pp domain.lo vv, mk_m_center_domain pp uu domain.hi;;
54
55
56 (* restrict_domain *)
57 let restrict_domain j left_flag domain =
58 let replace list j v = map (fun i -> if i = j then v else nth list (i - 1)) (1--length list) in
59 let t = nth (if left_flag then domain.lo else domain.hi) (j - 1) in
60 let lo = if left_flag then domain.lo else replace domain.lo j t in
61 let hi = if left_flag then replace domain.hi j t else domain.hi in
62 let w = replace domain.w j float_0 in
63 let y = replace domain.y j t in
64 {lo = lo; hi = hi; w = w; y = y};;
65
66
67 type function_info = {
68 eval0 : int -> ifloat list -> ifloat list -> interval;
69 taylor : int -> int -> m_cell_domain -> m_taylor_interval;
70 index : int;
71 };;
72
73 type result =
74 | Cell_inconclusive
75 | Cell_false
76 | Cell_result of result_tree
77 | Cell_pass of bool * function_info;;
78
79
80
81 exception Construction_error of string * m_cell_domain * function_info list;;
82
83 let error msg dom fs = raise (Construction_error (msg, dom, fs));;
84
85 let init_vol, update_verified_vol =
86 let compute_vol dom =
87 let fw = map float_of_ifloat dom.w in
88 itlist ( *. ) fw 1.0 in
89 let total_vol = ref 0.0 and
90 verified_vol = ref 0.0 and
91 last_report = ref 0 in
92 let init_vol dom =
93 total_vol := compute_vol dom;
94 verified_vol := 0.0;
95 last_report := 0 in
96 let update_verified_vol dom =
97 if !info_print_level > 0 && !total_vol > 0.0 then
98 let _ = verified_vol := !verified_vol +. compute_vol dom in
99 let verified = int_of_float (!verified_vol /. !total_vol *. 100.5) in
100 if verified > !last_report then
101 let _ = last_report := verified in report0 (Printf.sprintf "%d " !last_report)
102 else ()
103 else () in
104 init_vol, update_verified_vol;;
105
106
107 (* Checks one cell *)
108 let rec check_cell opt dom =
109 let pp = opt.pp in
110 let rec check flag fs =
111 match fs with
112 | [] ->
113 if not flag then Cell_false else Cell_inconclusive
114 | f :: rest ->
115 begin
116 try
117 let raw_fail, raw_pass =
118 if opt.raw_intervals0 then
119 begin
120 try
121 let interval = f.eval0 pp dom.lo dom.hi in
122 let lo, hi = dest_interval interval in
123 ge0_float lo, lt0_float hi
124 with Failure _ | Division_by_zero ->
125 false, false
126 end
127 else
128 false, false in
129 if raw_pass then
130 Cell_pass (true, f)
131 else if raw_fail then
132 check flag rest
133 else
134 let ti = f.taylor pp pp dom in
135 let upper = eval_m_taylor_upper_bound pp ti in
136 if lt0_float upper then
137 Cell_pass (false, f)
138 else
139 let lower = eval_m_taylor_lower_bound pp ti in
140 if ge0_float lower then
141 check flag rest
142 else
143 (if opt.mono_depth > 0 then
144 try
145 try_mono {opt with max_depth = opt.mono_depth} dom f ti
146 with Failure _ | Division_by_zero | Construction_error _ ->
147 check true rest
148 else
149 check true rest)
150 with Failure _ | Division_by_zero ->
151 check true rest
152 end
153 in
154 fun fs ->
155 check false fs
156 (* Tries monotonicity for a single function *)
157 and try_mono opt dom f ti =
158 let pp = opt.pp in
159 let rec mono acc indices_ws =
160 match indices_ws with
161 | [] -> acc
162 | (i, w) :: rest ->
163 if gt0_float w then
164 let upper = eval_m_taylor_partial_upper pp i ti in
165 if lt0_float upper then
166 let status = {variable = i; decr_flag = true; df0_flag = false; ti_flag = true} in
167 mono (status :: acc) rest
168 else
169 let lower = eval_m_taylor_partial_lower pp i ti in
170 if ge0_float lower then
171 let status = {variable = i; decr_flag = false; df0_flag = false; ti_flag = true} in
172 mono (status :: acc) rest
173 else
174 mono acc rest
175 else
176 mono acc rest in
177 let restrict status dom =
178 restrict_domain status.variable status.decr_flag dom in
179 let st = mono [] (zip (1--ti.n) dom.w) in
180 if length st = 0 then
181 failwith "Not monotonic"
182 else
183 let dom2 = itlist (fun st d -> restrict st d) st dom in
184 let result = construct_certificate0 opt dom2 [f] in
185 Cell_result (Result_mono (st, result))
186 (* Splits the domain if necessary *)
187 and construct_certificate0 opt =
188 let pp = opt.pp in
189 let rec construct depth dom fs =
190 if depth >= opt.max_depth then
191 error (Printf.sprintf "depth (%d) > max_depth (%d)" depth opt.max_depth) dom fs
192 else
193 let result = check_cell opt dom fs in
194 match result with
195 | Cell_false ->
196 error "False result" dom fs
197 | Cell_result r -> r
198 | Cell_pass (raw_flag, f) ->
199 let _ = update_verified_vol dom in
200 Result_pass (f.index, raw_flag)
201 | Cell_inconclusive ->
202 let ws = map float_of_ifloat dom.w in
203 let _, j = find_max ws in
204 let dom1, dom2 = split_domain pp (j + 1) dom in
205 let r1 = construct (depth + 1) dom1 fs and
206 r2 = construct (depth + 1) dom2 fs in
207 Result_glue (j, false, r1, r2)
208 in
209 fun dom fs ->
210 let _ = init_vol dom in
211 construct 0 dom fs;;
212
213 let construct_certificate opt dom fs_informal =
214 let mk_f (f0, ft) i = {
215 eval0 = f0;
216 taylor = ft;
217 index = i
218 } in
219 let fs = map2 mk_f fs_informal (0--(length fs_informal - 1)) in
220 construct_certificate0 opt dom fs;;
221
222 end;;
223
224
225
226 (*
227 (*******************)
228
229 needs "Formal_ineqs/informal/informal_taylor.hl";;
230 needs "Formal_ineqs/verifier/m_verifier_build.hl";;
231 open M_verifier_build;;
232
233 #install_printer Informal_float.print_ifloat;;
234 #install_printer Informal_interval.print_interval;;
235
236 open M_taylor_arith2;;
237 open M_taylor;;
238 open More_float;;
239 open Informal_search;;
240
241 let opt = {
242 mono_depth = 0;
243 max_depth = 100;
244 max_width = 1e-10;
245 pp = 8;
246 };;
247
248
249 let x_list = mk_list ([mk_float (-10) 0; mk_float (-10) 0; mk_float (-10) 0], `:real`);;
250 let z_list = mk_list ([mk_float 10 0; mk_float 10 0; mk_float 10 0], `:real`);;
251
252 let x_inf = [Informal_float.mk_float (Num.num_of_int (-10)) 0; Informal_float.mk_float (Num.num_of_int (-10)) 0; Informal_float.mk_float (Num.num_of_int (-10)) 0];;
253 let z_inf = [Informal_float.mk_float (Num.num_of_int 10) 0; Informal_float.mk_float (Num.num_of_int 10) 0; Informal_float.mk_float (Num.num_of_int 10) 0];;
254
255 let dom_th = mk_m_center_domain 3 5 x_list z_list;;
256 let dom_inf = Informal_taylor.mk_m_center_domain 5 x_inf z_inf;;
257
258 let schwefel_poly = `\x:real^3. -- #0.0000001 - ((x$1 - x$2 pow 2) pow 2 + (x$2 - &1) pow 2 +
259 (x$1 - x$3 pow 2) pow 2 + (x$3 - &1) pow 2)`;;
260
261 let f1, f2 = mk_verification_functions_poly 5 schwefel_poly;;
262 (*
263 let _, _, f3 = mk_verification_functions_poly 5 `\x:real^2. #1.5 - x$1`;;
264 let fs0 = [f2.Informal_verifier.taylor; f3.Informal_verifier.taylor];;
265 *)
266
267 let fs0 = [f2.Informal_verifier.taylor];;
268
269 let mk_f f i = {taylor = f; index = i};;
270 let fs = map2 mk_f fs0 (0--(length fs0 - 1));;
271
272 let c = construct_certificate {opt with pp = 5; mono_depth = 200} dom_inf fs0;;
273 result_stats c;;
274
275 (***)
276
277 let x_inf = [Informal_float.mk_float (Num.num_of_int 1) 0];;
278 let y_inf = [Informal_float.mk_float (Num.num_of_int 3) 0];;
279
280 let dom_inf = Informal_taylor.mk_m_center_domain 5 x_inf y_inf;;
281
282 let f1, _, f2 = mk_verification_functions_poly 5 `\x:real^1. x$1 - &2`;;
283 let _, _, f3 = mk_verification_functions_poly 5 `\x:real^1. #1.5 - x$1`;;
284 let fs0 = [f2.Informal_verifier.taylor; f3.Informal_verifier.taylor];;
285
286 let mk_f f i = {taylor = f; index = i};;
287 let fs = map2 mk_f fs0 (0--(length fs0 - 1));;
288
289 construct_certificate {opt with pp = 3} dom_inf fs0;;
290
291
292 0 <= 100 || (1 / 0 = 0);;
293 100 <= 0 && (1 / 0 = 0);;
294
295 let t_th = f1.taylor 5 5 dom_th;;
296 let t_inf = f2.Informal_verifier.taylor 5 5 dom_inf;;
297
298 let pp = 5;;
299 Informal_taylor.eval_m_taylor_lower_bound pp t_inf;;
300
301 let ws = map float_of_ifloat dom_inf.w;;
302 let _, j = find_max ws;;
303 let dom1, dom2 = split_domain pp j dom_inf;;
304 *)