What can interval analysis do for global optimization? (Q1186266): Difference between revisions

This is a survey article on the application of interval analysis to optimization. After some introductory remarks in Section 1, a prototype algorithm is presented for finding an enclosure of all the global minimizers of a given function defined on a box. The algorithm is based on subdivisions of boxes and on an ordered list. Since interval arithmetic is used later on to enclose ranges of functions, Section 3 gives a short course in this field. Included are some remarks on machine interval arithmetic. Inclusion functions and natural interval extensions are introduced in Section 4. Section 5 is devoted to box-discarding tests such as the midpoint test, the monotonicity test, a non-convexity test and the application of interval Newton-like methods. As a particular Newton-like operator, the Krawczyk operator is discussed in greater detail in a separate section. Convergence properties of the prototype algorithm are considered in Section 7, and termination criteria for this algorithm are listed subsequently. Optimization over unbounded domains, nonsmooth optimization and constrained optimization form the contents of the three final sections. A list with numerous references concludes the paper.