Cell exclusion algorithms

Abstract

This dissertation will address two problems which frequently arise in applications: finding the real zeros of a nonlinear system of equations and finding the minimum real value of a function of several variables. Just to name a few, the fields of chemistry, biology, physics, robotics, and economics involve zero-finding problems. Optimization problems are also extremely prevalent. One important optimization problem is that of minimizing cost. Cell exclusion algorithms apply an exclusion condition to some region, e.g., a cell, in which we expect all zeros to be found or on which we wish to determine the global minimum. Since an exclusion condition is a necessary but not sufficient condition for a cell to contain a zero or a point at which a function achieves its global minimum, a successful algorithm bounds the number of cells which remain at each iteration. Thus, we want to get as few false positive cells, i.e., cells which satisfy the condition but do not contain a zero or a point at which a function achieves its global minimum, as possible. We develop localized conditions which are more stringent than those which have been given in previous literature. More stringent exclusion conditions discard more cells and hence are more efficient. In this dissertation we develop the theory behind zero-finding and optimization cell exclusion algorithms. We present both types of algorithms. Several different root conditions are introduced and their effectiveness upon implementation is analyzed. Indeed, we give multiple numerical examples.