Debian Codegraph @

Formal_ineqs/docs/FormalVerifier.tex

raw
1 \documentclass[a4paper]{article}
2
3 \usepackage{amsmath}
4 \usepackage{amssymb}
5 \usepackage{hyperref}
6 \usepackage{graphicx}
7 \usepackage{geometry}
8
9 \geometry{
10 letterpaper,
11 left= 1.5in,
12 right= 1.5in,
13 top= 1.3in,
14 bottom= 1.4in
15 }
16
17 \newcommand{\partd}[2]{\frac{\partial #1}{\partial #2}}
18 \newcommand{\dih}{\mathrel{\rm dih}}
19
20
21 \parindent=0mm
22 \parskip=5pt
23
24 \title{A Tool for Formal Verification of Nonlinear Inequalities}
25
26 \author{Alexey Solovyev}
27
28 % Document
29 \begin{document}
30 % Title
31 \maketitle
32
33 % Content
34 \tableofcontents
35
36 \pagebreak
37 % References
38 \begin{thebibliography}{9}
39 \bibitem{HOL} HOL Light home page\\
40 \url{http://www.cl.cam.ac.uk/~jrh13/hol-light}
41
42 \bibitem{HOL-repo} HOL Light repository\\
43 \url{https://github.com/jrh13/hol-light}
44
45 \bibitem{HOL-tutorial} HOL Light tutorial\\
46 \url{http://www.cl.cam.ac.uk/~jrh13/hol-light/tutorial_220.pdf}
47
48 \bibitem{flyspeck} The Flyspeck project\\
49 \url{https://github.com/flyspeck/flyspeck}
50
51 \bibitem{bernstein}C\'esar Mu\~noz and Anthony Narkawicz, {\it Formalization of a Representation of Bernstein Polynomials and Applications to Global Optimization}, Journal of Automated Reasoning, DOI: 10.1007/s10817-012-9256-3\\
52 \url{http://shemesh.larc.nasa.gov/people/cam/Bernstein/}
53 \end{thebibliography}
54
55 % Introduction
56 \section{Introduction}
57 This document describes a tool for verification of nonlinear inequalities in HOL Light proof assistant~\cite{HOL, HOL-tutorial}. This tool was developed as a part of the Flyspeck project (a formal proof of the Kepler conjecture)~\cite{flyspeck}. The tool is capable to verify multivariate nonlinear strict inequalities on rectangular domains. More specifically, the tool can handle inequalities in the form
58 \[\forall {\bf x} \in D \implies f({\bf x}) < g({\bf x}),\]
59 where $D = \{(x_1, \ldots, x_n)\ |\ a_i \le x_i \le b_i\}$ and $f$, $g$ are functions which may include all usual arithmetic operations, square roots, arccosines, and arctangents. The maximal number of variables is 8. Future releases of the tool will include all elementary functions and will have no restriction on the number of variables. Moreover, it will be possible to verify inequalities on non-rectangular domains.
60
61 Internally, the tool uses interval arithmetic with Taylor approximations (with second-order error terms).
62
63 The document is organized as follows. The next section describes the installation process. Then a quick introduction of tool functions is presented. After that, a more detailed description of tool functions is given and special options are described. The last two sections describe several examples and test cases.
64
65
66 % Installation
67 \section{Installation}
68 First of all, if you don't have OCaml and HOL Light installed, then you need to install them. The verification tool was tested with Ocaml 3.09.3 and Ocaml 3.12.1 and with one of the latest versions of HOL Light (r149 in the HOL Light repository). HOL Light installation instructions can be found in John Harrison's HOL Light tutorial~\cite{HOL-tutorial}.
69
70 Alternatively, one can download and run the following script written by Alex Krauss: \url{https://bitbucket.org/akrauss/hol-light-workbench}. This script will download and install the latest version of HOL Light and other necessary programs.
71
72 The installation of the tool for verification of nonlinear inequalities is very simple. Download the distribution from
73
74 \vspace{-5pt}
75 \url{http://code.google.com/p/flyspeck/downloads/list}
76
77 \vspace{-5pt}
78 or get the latest version from the Flyspeck repository with the shell command
79
80 \vspace{-5pt}
81 \verb|svn co http://flyspeck.googlecode.com/svn/trunk/formal_ineqs|
82
83
84 The tool can be placed in any directory on your computer. It is important to inform HOL Light about tool's location. It can be done with the following OCaml command:
85
86 \verb|load_path := "path to the tool directory" :: !load_path;;|
87
88 After the path is set, the tool can be loaded with the command
89
90 \verb|needs "verifier/m_verifier_main.hl";;|
91
92 The tool loads the standard HOL Light library \verb|Multivariate/realanalysis.ml|. The loading process of this library could take pretty long time, so it is recommended to use a checkpointed version of HOL Light with preloaded multivariate analysis libraries.
93
94 Before loading the tool, it is also possible to change some global options. These options are described in section \ref{global}.
95
96
97 % Examples
98 \section{Quick Start}
99
100 The polynomial inequality
101 \begin{multline*}
102 -\frac{1}{\sqrt{3}} \le x \le \sqrt{2},\ -\sqrt{\pi} \le y \le 1
103 \implies x^2 y - x y^4 + y^6 + x^4 - 7 > -7.17995
104 \end{multline*}
105 can be verified with the following script
106
107 \begin{verbatim}
108 (* make sure that load_path contains the path to formal_ineqs *)
109 needs "verifier/m_verifier_main.hl";;
110 open M_verifier_main;;
111
112 let ineq =
113 `-- &1 / sqrt(&3) <= x /\ x <= sqrt(&2) /\
114 -- sqrt(pi) <= y /\ y <= &1
115 ==> x pow 2 * y - x * y pow 4 + y pow 6 - &7 + x pow 4 > -- #7.17995`;;
116
117 let th, stats = verify_ineq default_params 5 ineq;;
118 \end{verbatim}
119
120 The first parameter of the verification function \verb|verify_ineq| contains verification options. We use default values given by the constant \verb|default_params|. Available options are described in section \ref{verification}.
121
122 The second parameter specifies the precision of formal floating point operations. This parameter determines the maximal number of significant digits of any result returned by a formal floating point operation. Here, digits are not decimal. Internally all natural numbers are represented using a fixed base (see section \ref{global} for more details). This base is relatively large (the default value is 100) to speed up arithmetic operations. Actual precision of formal floating point operations depends on the precision parameter and on the base of the internal representation of natural numbers. If the base value is 100 and the precision parameter is 5 as in the example above, then the precision of formal floating point operations is 10 decimal digits: $100^5 = 10^{10}$. Note that the verification of the example will fail if the precision parameter is 4 or less. On the other hand, if the precision parameter is 10, the verification will succeed but it will take a little more time.
123
124 The third parameter is the inequality itself given as a HOL Light term. The format of this term is simple: it is an implication with bounds of variables in the antecedent and an inequality in the consequent. The bounds of all variables should be in the form $\text{\it a constant expression} <= x$ or $x <= \text{\it a constant expression}$. For each variable, upper and lower bounds must be given. The inequality must be a strict inequality ($<$ or $>$). The inequality may include \verb|sqrt|, \verb|atn|, and \verb|acs| functions. The constant \verb|pi| ($\pi$) is also allowed.
125
126 The verification function returns a HOL Light theorem and a record with some verification information which includes verification time.
127
128
129 % Verification Functions
130 \section{Verification Functions}\label{verification}
131 The main verification function \verb|verify_ineq| is contained in \verb|M_verifier_main| module defined in \verb|verifier/m_verifier_main.hl|. The function has 3 arguments and its type is
132 \begin{verbatim}
133 verify_ineq : verification_parameters -> int -> term -> thm * verification_stats
134 \end{verbatim}
135
136 The first parameter contains verification options defined in the following record
137 \begin{verbatim}
138 type verification_parameters =
139 {
140 (* If true, then monotonicity properties can be used *)
141 (* to reduce the dimension of a problem *)
142 allow_derivatives : bool;
143 (* If true, then convexity can be used *)
144 (* to reduce the dimension of a problem *)
145 convex_flag : bool;
146 (* If true, then verification on internal subdomains can be skipped *)
147 (* for a monotone function *)
148 mono_pass_flag : bool;
149 (* If true, then raw interval arithmetic can be used *)
150 (* (without Taylor approximations) *)
151 raw_intervals_flag : bool;
152 (* If true, then an informal procedure is used to determine *)
153 (* the optimal precision for the formal verification *)
154 adaptive_precision : bool;
155 (* This parameter might be used in cases when the certificate search *)
156 (* procedure returns a wrong result due to rounding errors *)
157 (* (this parameter will be eliminated when the search procedure is corrected) *)
158 eps : float;
159 };;
160 \end{verbatim}
161 A detailed description of these parameter is omitted in this document. In most cases, it is enough to use the constant \verb|default_params| which turns all verification flags on and sets \verb|eps = 0|. In rare cases, it is necessary to adjust \verb|eps| to get a result. This can be done with the command
162 \begin{verbatim}
163 verify_ineq {default_params with eps = 1e-10} 5 ineq_tm;;
164 \end{verbatim}
165
166 The second parameter of the verification function specifies the precision of formal floating point operations. This parameter determines the maximal number of significant digits of any result returned by a formal floating point operation. Here, digits are not decimal. Internally all natural numbers are represented using a fixed base (see section \ref{global} for more details). This base is relatively large (the default value is 100) to speed up arithmetic operations. Actual precision of formal floating point operations depends on the precision parameter and on the base of the internal representation of natural numbers. In many cases, if the verification function fails, it is enough to increase the precision parameter to get a result.
167
168 The third parameter of the verification function is a HOL Light term which specifies an inequality itself. The format of this term is the following:
169 \begin{verbatim}
170 bounds of variables ==> an inequality
171 \end{verbatim}
172 The bounds of all variables should be in the form $\text{\it a constant expression} <= x$ or $x <= \text{\it a constant expression}$. For each variable, upper and lower bounds must be provided. The order in which the bounds are given is irrelevant. Bounds of variables may be connected with \verb|/\| or with \verb|==>|. The inequality must be a strict inequality ($<$ or $>$). The inequality may include \verb|sqrt|, \verb|atn|, and \verb|acs| functions. The constant \verb|pi| ($\pi$) is also allowed.
173
174 The verification function returns a theorem and some verification information defined in the record
175 \begin{verbatim}
176 type verification_stats =
177 {
178 total_time : float;
179 formal_verification_time : float;
180 certificate : Verifier.certificate_stats;
181 };;
182 \end{verbatim}
183 The field \verb|total_time| contains total verification time. The field \verb|formal_verification_time| contains time taken by the formal verification procedure only (this time doesn't include time for constructing a solution certificate and for other preparations). The last field \verb|certificate| contains information about a solution certificate.
184
185 The conclusion of the returned theorem is not exactly the same as the third parameter of the verification function: the order of bounds of variables may be altered and variables which are not used in the inequality are eliminated. For example, commands
186 \begin{verbatim}
187 let th1, _ = verify_ineq default_params 3
188 `&1 <= y /\ y <= &2 /\ &1 <= x /\ x <= &3 ==> x + y < &6`;;
189 let th2, _ = verify_ineq default_params 3
190 `&1 <= y /\ y <= &2 /\ &1 <= x /\ x <= &3 ==> y < &3`;;
191 \end{verbatim}
192 return
193 \begin{verbatim}
194 th1 = |- (&1 <= x /\ x <= &3) /\ &1 <= y /\ y <= &2 ==> x + y < &6
195 th2 = |- &1 <= y /\ y <= &2 ==> y < &3
196 \end{verbatim}
197
198
199
200 % Options
201 \section{Global Options}\label{global}
202 The options which affect the arithmetic operations with natural and floating point numbers must be set before the verification tool is loaded. After the verification tool is loaded, arithmetic options may not be changed. To set arithmetic options, load the file \verb|arith_options.hl| located in the root directory of the tool. The available options are listed below.
203
204 \begin{enumerate}
205 % base
206 \item[\bf base] Determines the base for representing natural numbers. Default HOL Light
207 representation of natural numbers is binary (i.e., its base is 2). A higher base increases speed of arithmetic operations but it also requires more memory to remember additional theorems. The default value of the base is \verb|100|. To set a new base, use the command
208
209 \verb|Arith_options.base := 200;;|
210
211 % min_exp
212 \item[\bf min\_exp] Determines the minimal exponent in the representation of floating point numbers. Each floating point number is represented as a triple $(s, n, e)$ where $s$ is a boolean value which determines the sign of the number, $n$ and $e$ are natural numbers which represent the mantissa and the exponent. The value corresponding to $(s, n, e)$ is given by
213
214 \[f = (-1)^{\text{if $s$ then $1$ else $0$}} \times n \times b^{e - min\_exp}\]
215 where $b$ is the base of the representation of natural numbers.
216
217 % cached
218 \item[\bf cached] If this value is true, then results of all natural number operations are cached. The default value is \verb|true|.
219
220 % float_cached
221 \item[\bf float\_cached] If this value is true, then results of all floating point operations are cached. The default value is \verb|true|.
222
223 % init_cache_size
224 \item[\bf init\_cache\_size] Determines the initial size of the cache for results of arithmetic operations. The default value is \verb|10000|.
225
226 % max_cache_size
227 \item[\bf max\_cache\_size] Determines the maximal size of the cache for results of arithmetic operations. The default value is \verb|20000|. Note: each cached operation has its own cache.
228
229 \end{enumerate}
230
231 The file \verb|verifier_options.hl| contains the option \verb|info_print_level| which controls the amount of information printed by a verification process. This option can be changed at any time:
232
233 \verb|Verifier_options.info_print_level := 0;;|
234
235 Possible values are: 0~(no information is printed); 1~(all essential information is printed); 2~(all information is printed). The default value is 1.
236
237 The next example shows how to change default options:
238 \begin{verbatim}
239 (* The arithmetic options must be set before loading the verification tool *)
240 needs "arith_options.hl";;
241
242 (* Increase the arithmetic base *)
243 Arith_options.base := 200;;
244
245 (* Increase the cache size *)
246 Arith_options.max_cache_size = 40000;;
247
248 (* Load the verification tool *)
249 needs "verifier/m_verifier_main.hl";;
250
251 (* The verification option can be changed at any time *)
252 Verifier_options.info_print_level := 2;;
253
254 open M_verifier_main;;
255 \end{verbatim}
256
257 % Additional Examples
258 \section{Additional Examples}
259 The verification tool distribution contains several example files. The file \verb|examples_poly.hl| contains polynomial inequalities from the paper \cite{bernstein}. The command
260
261 \verb|needs "examples_poly.hl";;|
262
263 will load this file and run all polynomial inequality tests. To run all tests again, type \verb|run_tests();;|
264
265 To run a specific test, type \verb|run_{test_name}();;| where \verb|{test_name}| is one of the following: \verb|schwefel|, \verb|rd|, \verb|caprasse|, \verb|lv|, \verb|butcher|, \verb|magnetism|, \verb|heart|.
266
267 Here is the list of all examples.
268 \begin{itemize}
269 % schwefel
270 \item[\bf schwefel]
271 \begin{eqnarray*}
272 &-5.8806 \times 10^{-10} < (x_1 - x_2^2)^2 + (x_2 - 1)^2 + (x_1 - x_3^2)^2 + (x_3 - 1)^2\\
273 &(x_1, x_2, x_3) \in [(-10,-10,-10),(10,10,10)]
274 \end{eqnarray*}
275
276 % rd
277 \item[\bf rd]
278 \begin{eqnarray*}
279 &-36.7126907 < -x_1 + 2 x_2 - x_3 - 0.835634534\, x_2 (1 + x_2)\\
280 &(x_1, x_2, x_3) \in [(-5,-5,-5),(5,5,5)]
281 \end{eqnarray*}
282
283 % caprasse
284 \item[\bf caprasse]
285 \begin{eqnarray*}
286 &-3.1801 < -x_1 x_3^3 + 4 x_2 x_3^2 x_4 + 4 x_1 x_3 x_4^2 + 2 x_2 x_4^3 + 4 x_1 x_3 + 4 x_3^2 - 10 x_2 x_4 - 10 x_4^2 + 2\\
287 &(x_1, x_2, x_3, x_4) \in [(-0.5,-0.5,-0.5,-0.5),(0.5,0.5,0.5,0.5)]
288 \end{eqnarray*}
289
290 % lv
291 \item[\bf lv]
292 \begin{eqnarray*}
293 &-20.801 < x_1 x_2^2 + x_1 x_3^2 + x_1 x_4^2 - 1.1 x_1 + 1\\
294 &(x_1, x_2, x_3, x_4) \in [(-2,-2,-2,-2), (2,2,2,2)]
295 \end{eqnarray*}
296
297 % butcher
298 \item[\bf butcher]
299 \begin{eqnarray*}
300 &-1.44 < x_6 x_2^2 + x_5 x_3^2 - x_1 x_4^2 + x_4^2 - \frac{1}{3} x_1 + \frac{4}{3} x_4\\
301 &(x_1, x_2, x_3, x_4, x_5, x_6) \in [(-1,-0.1, -0.1, -1, -0.1, -0.1), (0,0.9,0.5,-0.1,-0.05,-0.03)]
302 \end{eqnarray*}
303
304 % magnetsim
305 \item[\bf magnetism]
306 \begin{eqnarray*}
307 &-0.25001 < x_1^2 + 2 x_2^2 + 2 x_3^2 + 2 x_4^2 + 2 x_5^2 + 2 x_6^2 + 2 x_7^2 - x_1\\
308 &(x_1,x_2,x_3,x_4,x_5,x_6,x_7) \in [(-1,-1,-1,-1,-1,-1,-1), (1,1,1,1,1,1,1)]
309 \end{eqnarray*}
310
311 % heart
312 \item[\bf heart]
313 \begin{equation*}
314 \begin{split}
315 &-1.7435 < -x_1 x_6^3 + 3 x_1 x_6 x_7^2 - x_3 x_7^3 + 3 x_3 x_7 x_6^2 - x_2 x_5^3 + 3 x_2 x_5 x_8^2 - x_4 x_8^3 + 3 x_4 x_8 x_5^2 - 0.9563453\\
316 &(x_1,x_2,x_3,x_4,x_5,x_6,x_7,x_8) \in [(-0.1, 0.4, -0.7, -0.7, 0.1, -0.1, -0.3, -1.1),\\ &\phantom{(x_1,x_2,x_3,x_4,x_5,x_6,x_7,x_8) \in [ }(0.4, 1, -0.4, 0.4, 0.2, 0.2, 1.1, -0.3)]
317 \end{split}
318 \end{equation*}
319 \end{itemize}
320
321 The file \verb|examples_flyspeck.hl| contains some inequalities from the Flyspeck project~\cite{flyspeck}. The command
322
323 \verb|needs "examples_flyspeck.hl";;|
324
325 will load this file and run some easy inequality tests. To rerun these tests, use the command \verb|test_easy();;|. To run more difficult tests, type \verb|test_medium();;| or \verb|test_hard();;|.
326 (Warning: medium tests require about 30 minutes, hard tests require more than 5 hours.)
327
328 Some Flyspeck inequalities are listed below.
329 \begin{eqnarray*}
330 \Delta(x_1,\ldots,x_6) &= &x_1 x_4(-x_1 + x_2 + x_3 - x_4 + x_5 + x_6)\\
331 && + x_2 x_5(x_1 - x_2 + x_3 + x_4 - x_5 + x_6)\\
332 && + x_3 x_6(x_1 + x_2 - x_3 + x_4 + x_5 - x_6)\\
333 && - x_2 x_3 x_4 - x_1 x_3 x_5 - x_1 x_2 x_6 - x_4 x_5 x_6,\\[6pt]
334 \Delta_4 &=& \partd{\Delta}{x_4},\\[6pt]
335 \dih_x(x_1,\ldots,x_6) &=& \frac{\pi}{2} - \arctan\left(\frac{-\Delta_4(x_1,\ldots,x_6)}{\sqrt{4 x_1 \Delta(x_1,\ldots,x_6)}}\right),\\[6pt]
336 \dih_y(y_1,\ldots,y_6) &=& \dih_x(y_1^2, \ldots, y_6^2).
337 \end{eqnarray*}
338
339 \begin{itemize}
340 % 1
341 \item[\bf 4717061266]
342 \begin{eqnarray*}
343 \Delta(x_1, x_2, x_3, x_4, x_5, x_6) > 0,\quad 4 \le x_i \le 6.3504
344 \end{eqnarray*}
345
346 % 2
347 \item[\bf 7067938795]
348 \begin{eqnarray*}
349 &\dih_x (x_1, \ldots, x_6) - \pi/2 + 0.46 < 0,\\
350 &4 \le x_{1,2,3} \le 6.3504,\ x_4 = 4,\ 3.01^2 \le x_{5,6} \le 3.24^2
351 \end{eqnarray*}
352
353 % 3
354 \item[\bf 3318775219]
355 \begin{eqnarray*}
356 &\begin{split}
357 0 < &\dih_y (y_1, \ldots, y_6) - 1.629 + 0.414 (y_2 + y_3 + y_5 + y_6 - 8.0)\\
358 &- 0.763 (y_4 - 2.52) - 0.315 (y_1 - 2.0),
359 \end{split}\\
360 &2 \le y_i \le 2.52
361 \end{eqnarray*}
362
363 \end{itemize}
364
365 % Test Results
366 \section{Test Results}
367 This section contains time test results for inequalities described in the previous section. All tests were performed on Intel Core i5, 2.67GHz running Ubuntu 9.10 inside Virtual Box 4.2.0 on a Windows 7 host; the Ocaml version was 3.09.3; the base of arithmetic was 200; the caching was turned on.
368
369 \begin{center}
370 Polynomial inequalities
371
372 \begin{tabular}{l@{\quad} r r r r r}
373 %{r@{\quad}rl}
374 \hline
375 \multicolumn{1}{l}{\rule{0pt}{12pt}Inequality ID}&
376 \multicolumn{1}{l}{\phantom{x}\# variables}&
377 \multicolumn{1}{l}{\phantom{x}precision}&
378 \multicolumn{1}{l}{\phantom{x}total time (s)}&
379 \multicolumn{1}{l}{\phantom{x}formal verification (s)}\\
380 \hline\rule{0pt}{12pt}%
381 schwefel & 3 & 5 & 26.329 & 19.145 \\
382 rd & 3 & 5 & 1.593 & 0.017 \\
383 caprasse & 4 & 5 & 8.057 & 1.286 \\
384 lv & 4 & 5 & 1.875 & 0.030 \\
385 butcher & 6 & 5 & 3.609 & 0.035 \\
386 magnetism & 7 & 5 & 7.007 & 1.347 \\
387 heart & 8 & 5 & 17.298 & 1.277 \\
388 \hline
389 \end{tabular}
390 \end{center}
391
392 \begin{center}
393 Flyspeck inequalities
394
395 \begin{tabular}{l@{\quad} r r r r r}
396 %{r@{\quad}rl}
397 \hline
398 \multicolumn{1}{l}{\rule{0pt}{12pt}Inequality ID}&
399 \multicolumn{1}{l}{\phantom{x}precision}&
400 \multicolumn{1}{l}{\phantom{x}total time (s)}&
401 \multicolumn{1}{l}{\phantom{x}formal verification (s)}\\
402 \hline\rule{0pt}{12pt}%
403 2485876245a & 4 & 5.530 & 0.058 \\
404 4559601669b & 4 & 4.679 & 0.048 \\
405 4717061266 & 4 & 27.1 & 0.250 \\
406 5512912661 & 4 & 8.860 & 0.086 \\
407 6096597438a & 4 & 0.071 & 0.071 \\
408 6843920790 & 4 & 2.824 & 0.076 \\
409 SDCCMGA b & 4 & 9.012 & 0.949 \\
410 TSKAJXY-TADIAMB\footnotemark[1] & 4 & 75.9 & 21.2 \\
411 7067938795 & 4 & 431 & 387 \\
412 5490182221 & 4 & 1726 & 1533 \\
413 3318775219 & 4 & 17091 & 15226 \\
414 \hline
415 \end{tabular}
416 \end{center}
417 \footnotetext[1]{Reduced to a polynomial inequality}
418
419 \end{document}
420
421
422