Deterministic global optimization. Geometric branch-and-bound methods and their applications (Q642467)

Geometric branch-and-bound methods are prominent tools to solve global optimization problems arising in many areas. The book provides a general theory, the rate of convergence, for lower bounding operations of these algorithms in the context of unconstrained global optimization. Chapter 1 provides background material on convexity, location theory, d.c. functions and interval analysis. In Chapter 2, the prototype geometric branch-and-bound algorithm is introduced and the rate of convergence is defined. Chapter 3 investigates the rate of convergence of nine bounding operations (from the literature and new ones). In numerical tests, empirical rates of convergence are computed to verify the theoretical results. In Chapter 4, the geometric branch-and-bound algorithm is extended to multicriteria optimization, and again, its convergence is analyzed theoretically and tested empirically for location problems. Chapter 5 further extends this work by developing discarding tests for differentiable problems, again tested on location problems. The topic of Chapter 6 is an extension of the geometric branch-and-bound algorithm to problems with combinatorial variables. It covers a presentation of the algorithm, convergence theory, mixed bounding operations, exact optimal solutions, and numerical results. Chapter 7 is dedicated to a specific application, circle detection, a global optimization problem in image processing. The second application is an integrated scheduling and location problem, discussed in Chapter 8. This is a problem with mixed variables as in Chapter 6. Finally, the problem of optimally locating a line with respect to a median objective function is addressed in Chapter 9. Chapter 10 provides a brief summary.