nach oben

1996 | Buch

Kapitel lesen Erstes Kapitel lesen

Rigorous Global Search: Continuous Problems

verfasst von: R. Baker Kearfott

Verlag: Springer US

Buchreihe : Nonconvex Optimization and Its Applications

Enthalten in: Professional Book Archive

Einloggen, um Zugang zu erhalten

Über dieses Buch

This work grew out of several years of research, graduate seminars and talks on the subject. It was motivated by a desire to make the technology accessible to those who most needed it or could most use it. It is meant to be a self-contained introduction, a reference for the techniques, and a guide to the literature for the underlying theory. It contains pointers to fertile areas for future research. It also serves as introductory documentation for a Fortran 90 software package for nonlinear systems and global optimization. The subject of the monograph is deterministic, automatically verified or r- orous methods. In such methods, directed rounding and computational fix- point theory are combined with exhaustive search (branch and bound) te- niques. Completion of such an algorithm with a list of solutions constitutes a rigorous mathematical proof that all of the solutions within the original search region are within the output list. The monograph is appropriate as an introduction to research and technology in the area, as a desk reference, or as a graduate-level course reference. Kno- edge of calculus, linear algebra, and elementary numerical analysis is assumed.

Inhaltsverzeichnis

Frontmatter

1. Preliminaries

Abstract

The main purpose of this book is to introduce techniques and software for the verified solution of nonlinear systems of equations and for rigorous, deterministic unconstrained and constrained global optimization. Specifically, global optima or solutions of nonlinear equations will be sought within the box

$$ X = \left\{ {{{({x_1},{x_2},...,{x_n})}^T} \in {R^n}/{{\underline x }_i} \le {x_i} \le \overline {{x_i}} ,1 \le i \le n} \right\}$$

(1.1)

for some set of lower bounds $ \left\{ {{{\underline x }_i}} \right\}_i^n = 1$ and upper bounds $ \left\{ {{{\overline x }_i}} \right\}_i^n = 1$.

R. Baker Kearfott

2. Software Environments

Abstract

This chapter deals with implementations of the interval arithmetic concepts described in Chapter 1. Such software is, in turn, used in later chapters to construct higher-level software systems to solve nonlinear systems of equations and for global optimization. A FORTRAN-77 library and a set of Fortran 90 modules built upon this library are described here. Although some information here is specific, underlying principles and philosophy are emphasized, and the packages are readily available, free of cost, to readers.

R. Baker Kearfott

3. On Preconditioning

Abstract

As mentioned in §1.2, it is usually necessary to precondition an interval linear system to obtain meaningful bounds on the solution set. This is clear for the interval Gauss-Seidel method, since it reduces to the classical Gauss-Seidel method when the coefficients of the system of equations are thin, and since the classical Gauss-Seidel method in general does not converge without preconditioning. However, preconditioning is also necessary and useful for the Krawczyk method and interval Gaussian elimination. For example, if interval Gaussian elimination, i.e. Algorithm 1 is applied to the system $AX = B$ of (1.19) on page 20, the result is

$$ \left( {\frac{{\left[ {2,4} \right]\left| {\left[ { - 2,1} \right]} \right|\left[ { - 2,2} \right]}}{{\left[ { - 1,2} \right]\left| {\left[ {2,4} \right]} \right|\left[ { - 2,2} \right]}}} \right)\left( {\frac{{\left[ {2,4} \right]\left| {\left[ { - 2,1} \right]} \right|\left[ { - 2,2} \right]}}{{0\left| {\left[ {2,4} \right] - \frac{{\left[ { - 2,1} \right]}}{{\left[ {2,4} \right]}}\left[ {2,4} \right]} \right|\left[ { - 2,2} \right] - \frac{{\left[ { - 2,2} \right]}}{{\left[ {2,4} \right]}}\left[ { - 2,2} \right]}}} \right) = \left( {\frac{{\left[ {2,4} \right]\left| {\left[ { - 2,1} \right]} \right|\left[ { - 2,2} \right]}}{{\left[ { - 1,2} \right]\left| {\left[ { - 4,4} \right]} \right|\left[ { - 6,6} \right]}}} \right) $$

which gives only ${x_2} \in \frac{{\left[ { - 6,6} \right]}}{{\left[ { - 4,4} \right]}} = {\kern 1pt} and{\kern 1pt} {x_1} \in $, whereas, as is seen in Gigure 1.1, the smallest possible interval enclosure of the solution set is $ \sum {(A,B) = {{\left( {\left[ { - 4,4} \right],\left[ { - 4,4} \right]} \right)}^T}} $. Similarly, applying the interval Gauss-Seidel method results in $ \overline {{x_1}} \leftarrow \frac{{\left[ { - 2,2} \right] - \left[ { - 2,1} \right]\left[ { - 10,10} \right]}}{{\left[ {2,4} \right]}} = \left[ { - 11,11} \right] \supset \left[ { - 10,10} \right]{\kern 1pt} and{\kern 1pt} \overline {{x_2}} \leftarrow \frac{{\left[ { - 2,2} \right] - \left[ { - 1,2} \right]\left[ { - 10,10} \right]}}{{\left[ {2,4} \right]}} = \left[ { - 11,11} \right] \supset \left[ { - 10,10} \right]$. Finally, the Krawczyk method only makes sense in the context of presconditioners.

R. Baker Kearfott

4. Verified Solution of Nonlinear Systems

Abstract

Recall that a main goal of this book is solution of Problem 1.2, that is, finding all solutions of an equation F(X)=0, F:ℝ ⁿ→ℝ ⁿ) within a box X ∈Iℝ ⁿ. In previous chapters, techniques useful in parts of the solution of this problem have been explained. Here, tessellation processes appear that combine these pieces into an overall algorithm. The output to this overall algorithm will be a list ℜ of small boxes that have been verified to contain unique roots and a list U of small boxes that have neither been verified to contain roots nor verified to not contain roots¹.

R. Baker Kearfott

5. Optimization

Abstract

Here, the techniques explained so far will be used to construct solution algorithms to Problem (1.3), that is, to the problem

R. Baker Kearfott

6. Non-Differentiable Problems

Abstract

In previous chapters, interval extensions and interval Newton methods were developed for verified global solution of nonlinear systems of equations and for global optimization. In Chapters 1 and 2, it was shown how to compute and use such interval extensions and interval Newton methods when the functions were given by smooth expressions, without conditional branches. In fact, however, many practical problems, in particular those containing expressions such as |E(X)| and }E(X),F(X){, E, F : ℝⁿ → ℝ or functions defined by IF-THEN-ELSE branches, result in functions whose derivatives have jump discontinuities. However, if the function itself is continuous, order-1 interval extensions can be computed within the automatic differentiation framework of §1.4 and §2.2.

R. Baker Kearfott

7. Use of Intermediate Quantities in the Expression Values

Abstract

Code lists as described in §1.4.4 and §2.2.2 contain complete information about the relationships among the intermediate quantities computed during evaluation of a particular natural interval extension. These relationships can sometimes be used to reduce the amount of overestimation in such interval extensions, or to help in the solution of nonlinear systems of equations.

R. Baker Kearfott

Backmatter

Titel: Rigorous Global Search: Continuous Problems
verfasst von: R. Baker Kearfott
Verlag: Springer US
Electronic ISBN: 978-1-4757-2495-0
Print ISBN: 978-1-4419-4762-8
DOI: https://doi.org/10.1007/978-1-4757-2495-0

Springer Professional

Über dieses Buch

Inhaltsverzeichnis

Frontmatter

1. Preliminaries

2. Software Environments

3. On Preconditioning

4. Verified Solution of Nonlinear Systems

5. Optimization

6. Non-Differentiable Problems

7. Use of Intermediate Quantities in the Expression Values

Backmatter