Interval Computations,
Final Exam for the course
CS 5391/CS 6391, Fall 2015

Name: ___________________________________________________________

General comments:

Good luck!

1 (30 points) We want to estimate the range of a function (1 + 2 * x) * (2 − x) on the interval [−2, 0]. Do the following:

1a. Find the exact range by using calculus.

1b. Estimate the range by applying naive (straightforward) interval computations to the original interval.

1c. Use bisection and check monotonicity of the function on each of the sub-intervals, applying naive interval computations only if the function is not monotonic.

1d. Use bisection and apply the centered form (with checking monotonicity first) to both sub-intervals.

1e. Apply affine arithmetic to estimate the desired range.

1f. Use two linearlization algorithms that we studied (Algorithm 1 that use partial derivatives and Algorithm 2 that does not use partial derivatives) to estimate this range.

2 (10 points) Find the range of a function f(x1, x2) = (x1)2 − x1 * x2 − x22 − x2 when x1 is in the interval [−1, 1], and x2 is in the interval [−2, 2]:

2a. by using calculus

2b. by using naive interval computations.

3 (5 points) Use the interval-based optimization algorithm to locate the maximum of the function
f(x) = (1 + 2 * x) * (2 − x)
on the interval [−0.8, 0]. Divide this interval into two, then divide each of the remaining intervals into two again, etc. Stop when you get intervals of width 0.1.

4 (10 points) Use the constraints method to solve the following two problems:

4a. Find x1 and x2, both from the interval [0, 1], that satisfy the system of equations x1 + x2 = 1 and
x1 * x2 = 0.16.

4b. Find x1 and x2, both from the interval [0, 1], that satisfy the system of equations x1 + x2 = 1 and
x1 * x2 = 0.7.

5 (15 points)

5a. If use the simplest "and"- and "or"-operations min and max, and our degrees of belief in A, B, and C are, correspondingly, 0.3, 0.8, and 0.5, what is our degree of belief in (A \/ B) & C?

5b. For a membership function μ(x) = max(0, 1 − |2 − x|, 0), what are the α-cuts corresponding to α = 0.5? to α = 0.9?

5c. Let us assume that the quantity x is described by the membership function μ(x) = 1 − |x|, and the quantity y is described by the membership function μ(y) = 1 − |2 − y|. Use the values α = 0.2, 0.4, 0.6, 0.8, and 1.0 to form membership functions for z = x + y and t = x * y.

6 (5 points) Follow the first three steps of bisection to locate the square root of 11, i.e., the solution to the equation x2 − 11 = 0 on the interval [0, 4].

7 (5 points) Write down a Java method that, given a function f, values x1, ..., xn, and a number h, computes the sum (c1)2 + ... + (cn)2, where
ci = (f(x1, ..., xi − 1, xi + h, xi + 1, ..., xn) − f(x1, ..., xi − 1, xi, xi + 1, ..., xn)) / h.

8 (15 points) Suppose that we have three alternatives, for which the gains are in the intervals [0, 100], [−80, −20], and [−60, 200].

8a. Is there an alternative which is guaranteed to be optimal (i.e., for which the gain is the largest)?

8b. List all alternatives which can be optimal.

8c. Which alternative(s) should we select if we use Hurwicz optimism-pessimism criterion with α = 0, 0.5, and 1.

9 (10 points)

9a. Write down an expression for which an optimizing compiler improves the estimates provided by straightforward interval computations. This expression should be different from the examples that I gave; minor difference is OK.

9b. Write down an expression for which an optimizing compiler worsens improves the estimates provided by straightforward interval computations. This expression should be different from the examples that I gave; minor difference is OK.

10 (5 points) If we use 2-digit decimal numbers, and what to get guaranteed bounds, what will be the result of multiplying the intervals [0.13, 0.54] and [0.67, 1.30]?