We propose interval arithmetic and interval constraint algorithms for global optimization. Both of these compute lower and upper bounds of a function over a box,
and return a lower and an upper bound for the global minimum. In interval arithmetic methods, the bounds are computed using interval arithmetic evaluations. Interval constraint methods instead use domain reduction operators and consistency algorithms.
The usual interval arithmetic algorithms
for global optimization suffer from at least one of the following drawbacks:
- Mixing the fathoming problem, in which we ask for the global minimum only, with the localization problem, in which we ask for the set of points at which the global minimum occurs.
- Not handling the inner and outer approximations for epsilon-minimizer,
which is the set of points at which
the objective function is within epsilon
of the global minimum.
- Nothing is said about the quality for their results in actual computation. The properties of the algorithms are stated only in the limit for infinite running time, infinite memory, and infinite precision of the floating-point number system.
To handle these drawbacks, we propose interval arithmetic algorithms for fathoming problems and for localization problems. For these algorithms we state properties that can be verified in actual executions of the algorithms. Moreover, the algorithms proposed return the best results
that can be computed with given expressions
for the objective function and the conditions, and a given hardware.
Interval constraint methods combine interval arithmetic and constraint processing techniques, namely consistency algorithms, to obtain tighter bounds for the objective function over a box.
The basic building block of interval constraint methods is the generic propagation algorithm. This explains our efforts to improve the generic propagation algorithm as much as possible. All our algorithms, namely dual, clustered,
deterministic, and selective propagation algorithms, are developed as an attempt to improve the efficiency of the generic propagation algorithm.
The relational box-consistency algorithm is
another key algorithm in interval constraints. This algorithm keeps squashing the left and right bounds of the intervals of the variables until no further narrowing is possible. A drawback of this way of squashing is that as we proceed further, the process of squashing becomes slow.
Another drawback is that, for some cases, the actual narrowing occurs late.
To address these problems, we propose the following algorithms:
- Dynamic Box-Consistency algorithm: instead of pruning the left and then the right bound of each domain, we alternate the pruning between all the domains.
- Adaptive Box-Consistency algorithm: the idea behind this algorithm is to get rid of the boxes as soon as possible: start with small boxes and extend them or shrink them depending on the pruning outcome. This adaptive behavior makes this algorithm very suitable for quick squashing.
Since the efficiency of interval constraint optimization methods depends heavily on the sharpness of the upper bound for the global minimum, we must make some effort to find the appropriate point or box to use for computing the upper bound, and not to randomly pick one as is commonly done.
So, we introduce interval constraints with exploration. These methods use non-interval methods as an exploratory step in
solving a global optimization problem.
The results of the exploration are then used to guide interval constraint algorithms, and thus improve their efficiency.
| Identifer | oai:union.ndltd.org:uvic.ca/oai:dspace.library.uvic.ca:1828/198 |
| Date | 22 August 2007 |
| Creators | Moa, Belaid |
| Contributors | van Emden, Maarten H., Wadge, William W. |
| Source Sets | University of Victoria |
| Language | English, English |
| Detected Language | English |
| Type | Thesis |
| Rights | Available to the World Wide Web |
Page generated in 0.0477 seconds