Interval method for special constrained global optimization problems
The basic framework in this thesis is the standard Hansen method. The standard Hansen method has become a very well-known and popular method over the last few decades in the area of Interval Arithmetic [1] for finding all solutions of optimization problem. Listed below are some strategies we have developed: a). Binary tree data structure is proposed to record all the data associated with a functional relationship. We build a tree with the nodes representing all the operations and variables based upon the given function. Then we use a backward propagation method to obtain a new subdivision direction to be bisect. This method could accelerate the convergence after choosing the dominant variable in the tree data structure. Numerical results are illustrated to show the effectiveness in Chapter 3. b). Affine arithmetic is proposed to reduce the approximations' error and can be applied to linearize the given function and also applied in dealing with linear constraints. The main use of AA is to keep track of rounding errors for each computed value. Besides, AA provides a much tighter bound. Numerical results are illustrated to show the effectiveness in Chapter 3. c). Exclusion zone functions are introduced to further reduce variables' intervals which can be added in the deletion step in the standard Hansen algorithm. Numerical results are illustrated to show the effectiveness in Chapter 3. d). For constrained global optimization problems with one linear constraint, we have developed a backward interval value detection method as noted in Chapter 4. e). The four activities outlined above were performed to support this final activity. Three different procedures are developed (coordinate descent method, cutting line method, and projection coordinate descent method) to locate a feasible sampling point for the two linear constraints. Numerical results are illustrated to show the effectiveness in Chapter 5. The three procedures referenced above are then combined with the Interval Arithmetic method [1] to compare against the standard Hansen method without using any proposed strategies. The results of all three procedures in combination with the Interval Arithmetic method [1] are found to be superior to the standard Hansen technique.
Networked Digital Library of Theses and Dissertations