1 A REVIEW OF TECHNIQUES IN THE VERIFIED SOLUTION OF CONSTRAINED GLOBAL OPTIMIZATION PROBLEMS
---
paper_title: Computation of rational interval functions

paper_content:

This paper presents a general algorithm for computing interval expressions. The strategy is characterized by a subdivision of the argument intervals of the expression and a recomputation of the expression with these new intervals. The precision of the result is limited only by the actual computer.
---
paper_title: Global optimization using interval analysis ? the multi-dimensional case

paper_content:

We show how interval analysis can be used to compute the global minimum of a twice continuously differentiable function ofn variables over ann-dimensional parallelopiped with sides parallel to the coordinate axes. Our method provides infallible bounds on both the globally minimum value of the function and the point(s) at which the minimum occurs.
---
paper_title: An interval arithmetic method for global optimization

paper_content:

An interval arithmetic method is described for finding the global maxima or minima of multivariable functions. The original domain of variables is divided successively, and the lower and the upper bounds of the interval expression of the function are estimated on each subregion. By discarding subregions where the global solution can not exist, one can always find the solution with rigorous error bounds. The convergence can be made fast by Newton's method after subregions are grouped. Further, constrained optimization can be treated using a special transformation or the Lagrange-multiplier technique.
---
paper_title: Use of a Real-Valued Local Minimum in Parallel Interval Global Optimization

paper_content:

We consider a parallel method for finding the global minimum (and all of the global minimizers) of a continuous non-linear function f : D ! R, where D is an n-dimensional interval. The method combines one of the well known branch-and-bound interval search methods of Skelboe, Moore and Hansen with a real-valued optimization method. Initially we use a standard real-valued optimization method to find a local minimizer xp (or rather: a prediction of a local minimizer). Then the interval Newton method is applied to an interval Ip containing xp as its midpoint. Ip is chosen as large as possible under the restriction that the Newton interval method must converge when Ip is used as starting interval. In this way the original problem has been reduced to the problem of searching a domain DnIp which does not contain the local (and perhaps global) minimizer. The remaining domain is searched by the branch-and-bound interval method, starting by splitting the remaining domain into 2n intervals and hence avoiding Ip. This branch-and-bound search then either verifies that the point xp is the global minimizer, or the opposite is detected and it finds the global minimum (and the global minimizers) in the usual way. The combined method parallizes well. On one test case the combined method is faster than the branch-and-bound method itself. However, for another test case we get the opposite result. This is explained.
---
paper_title: Global Optimization Using Interval Analysis

paper_content:

Employing a closed set-theoretic foundation for interval computations, Global Optimization Using Interval Analysis simplifies algorithm construction and increases generality of interval arithmetic. This Second Edition contains an up-to-date discussion of interval methods for solving systems of nonlinear equations and global optimization problems. It expands and improves various aspects of its forerunner and features significant new discussions, such as those on the use of consistency methods to enhance algorithm performance. Provided algorithms are guaranteed to find and bound all solutions to these problems despite bounded errors in data, in approximations, and from use of rounded arithmetic.
---
paper_title: Optimization Software Guide

paper_content:

Preface Part I. Overview of Algorithms. 1. Optimization Problems and Software 2. Unconstrained Optimization 3.Nonlinear Least Squares 4. Nonlinear Equations 5. Linear Programming 6. Quadratic Programming 7. Bound-Constrained Optimization 8. Constrained Optimization 9. Network Optimization 10. Integer Programming Chapter 11. Miscellaneous Optimization Problems Part II: Software Packages. AMPL BQPD BT BTN CNM CONOPT CONSOL-OPTCAD CPLEX C-WHIZ DFNLP DOC DOT FortLP FSQP GAMS GAUSS GENESIS GENOS GINO GRG2 HOMPACK IMSL Fortran and C Library LAMPS LANCELOT LBFGS LINDO LINGO LNOS LPsolver LSGRG2 LSNNO LSSOL M1QN2 and M1QN3 MATLAB MINOS MINPACK-1 MIPIII MODULOPT NAG C library NAG Fortran Library NETFLOW NETSOLVE NITSOL NLPE NLPQL NLPQLB NLSFIT NLSSOL NLPSPR NPSOL OB1 ODRPACK OPSYC OptiA OPTIMA Library OPTPACK OSL PC- PROG PITCON PORT 3 PROC NLP Q01SUBS QAPP QPOPT SPEAKEASY SQP TENMIN TENSOLVE TN/TNBC TNPACK UNCMIN VE08 VE10 VIG and VIMDA What's Best! Appendix: Internet Software References.
---
paper_title: Second-Order Sufficient Optimality Conditions for Local and Global Nonlinear Programming

paper_content:

This paper presents a new approach to the sufficient conditions of nonlinear programming. Main result is a sufficient condition for the global optimality of a Kuhn-Tucker point. This condition can be verified constructively, using a novel convexity test based on interval analysis, and is guaranteed to prove global optimality of strong local minimizers for sufficiently narrow bounds. Hence it is expected to be a useful tool within branch and bound algorithms for global optimization.
---
paper_title: Constrained Global Optimization: Algorithms and Applications

paper_content:

Convex sets and functions.- Optimality conditions in nonlinear programming.- Combinatorial optimization problems that can be formulated as nonconvex quadratic problems.- Enumerative methods in nonconvex programming.- Cutting plane methods.- Branch and bound methods.- Bilinear programming methods for nonconvex quadratic problems.- Large scale problems.- Global minimization of indefinite quadratic problems.- Test problems for global nonconvex quadratic programming algorithms.
---
paper_title: Inclusion functions and global optimization II

paper_content:

Inclusion functions combined with special subdivision strategies are an effective means of solving the global unconstrained optimization problem. Although these techniques were determined and numerically tested about ten years ago, they are nearly unknown and scarcely used. In order to make the role of inclusion functions and subdivision strategies more widespread and transparent we will discuss a related simplified basic algorithm. It computes approximations of the global minimum and, at the same time, bounds the absolute approximation error. We will show that the algorithm works and converges under more general assumptions than it has been known hitherto, that is, only appropriate inclusion functions are expected to exist. The number of minimal points (finite or infinite) is not of importance. Lipschitz conditions or continuity are not assumed. As shown in the Appendix the required inclusion functions can be constructed and programmed without difficulty in a natural way using interval analysis.
---
paper_title: Global optimization using interval analysis ? the multi-dimensional case

paper_content:

We show how interval analysis can be used to compute the global minimum of a twice continuously differentiable function ofn variables over ann-dimensional parallelopiped with sides parallel to the coordinate axes. Our method provides infallible bounds on both the globally minimum value of the function and the point(s) at which the minimum occurs.
---
paper_title: An interval arithmetic method for global optimization

paper_content:

An interval arithmetic method is described for finding the global maxima or minima of multivariable functions. The original domain of variables is divided successively, and the lower and the upper bounds of the interval expression of the function are estimated on each subregion. By discarding subregions where the global solution can not exist, one can always find the solution with rigorous error bounds. The convergence can be made fast by Newton's method after subregions are grouped. Further, constrained optimization can be treated using a special transformation or the Lagrange-multiplier technique.
---
paper_title: Global Optimization Using Interval Analysis

paper_content:

Employing a closed set-theoretic foundation for interval computations, Global Optimization Using Interval Analysis simplifies algorithm construction and increases generality of interval arithmetic. This Second Edition contains an up-to-date discussion of interval methods for solving systems of nonlinear equations and global optimization problems. It expands and improves various aspects of its forerunner and features significant new discussions, such as those on the use of consistency methods to enhance algorithm performance. Provided algorithms are guaranteed to find and bound all solutions to these problems despite bounded errors in data, in approximations, and from use of rounded arithmetic.
---
paper_title: A Review of Preconditioners for the Interval Gauss–Seidel Method

paper_content:

Interval Newton methods in conjunction with generalized bisection can form the basis of algorithms that find all real roots within a specified box X ⊂ Rn of a system of nonlinear equations F (X) = 0 with mathematical certainty, even in finite-precision arithmetic. In such methods, the system F (X) = 0 is transformed into a linear interval system 0 = F (M) + F′(X)(X −M); if interval arithmetic is then used to bound the solutions of this system, the resulting box X contains all roots of the nonlinear system. We may use the interval Gauss–Seidel method to find these solution bounds. In order to increase the overall efficiency of the interval Newton / generalized bisection algorithm, the linear interval system is multiplied by a preconditioner matrix Y before the interval Gauss–Seidel method is applied. Here, we review results we have obtained over the past few years concerning computation of such preconditioners. We emphasize importance and connecting relationships, and we cite references for the underlying elementary theory and other details.
---
paper_title: The Cluster Problem in Global Optimization -- The Univariate Case

paper_content:

The Cluster Problem in Global Optimization the Univariate Case. We consider a branch and bound method for enclosing all global minimizers of a nonlinearC 2 or C 1 objective function. In particular, we consider bounds obtained with interval arithmetic, along with the “midpoint test,” but no acceleration procedures. Unless the lower bound is exact, the algorithm without acceleration procedures in general gives an undesirable Cluster of intervals around each minimizer. In this article, we analyze this problem in the one dimensional case. Theoretical results are given which show that the problem is highly related to the behavior of the objective function near the global minimizers and to the order of the corresponding interval extension.
---
paper_title: Nonlinear parameter estimation by global optimization—efficiency and reliability

paper_content:

In this paper we first show that the objective function of a least squares type nonlinear parameter estimation problem can be any non- negative real function, and therefore this class of problems corre- sponds to global optimization. Two non-derivative implementations of a global optimization method are presented; with nine standard test functions applied to measure their efficiency. A new nonlinear test problem is then presented for testing the reliability of global op- timization algorithms. This test function has a countable infinity of local minima and only one global minimizer. The region of attraction of the global minimum is of zero measure. The results of efficiency and reliability tests are given.
---
paper_title: Algorithm 681: INTBIS, a portable interval Newton/bisection package

paper_content:

We present a portable software package for finding all real roots of a system of nonlinear equations within a region defined by bounds on the variables. Where practical, the package should find all roots with mathematical certainty. Though based on interval Newton methods, it is self-contained. It allows various control and output options and does not require programming if the equations are polynomials; it is structured for further algorithmic research. Its practicality does not depend in a simple way on the dimension of the system or on the degree of nonlinearity.
---
paper_title: Box-Splitting strategies for the interval Gauss-Seidel step in a global optimization method

paper_content:

We consider an algorithm for computing verified enclosures for all global minimizersx* and for the global minimum valuef*=f(x*) of a twice continuously differentiable functionf:ℝ n →→ within a box [x]∈I→. Our algorithm incorporates the interval Gauss-Seidel step applied to the problem of finding the zeros of the gradient off. Here, we have to deal with the gaps produced by the extended interval division. It is possible to use different box-splitting strategies for handling these gaps, producing different numbers of subboxes. We present results concerning the impact of these strategies on the interval Gauss-Seidel step and therefore on our global optimization method. First, we give an overview of some of the techniques used in our algorithm, and we describe the modifications improving the efficiency of the interval Gauss-Seidel step by applying a special box-splitting strategy. Then, we have a look on special preconditioners for the Gauss-Seidel step, and we investigate the corresponding results for different splitting strategies. Test results for standard global optimization problems are discussed for different variants of our method in its portable PASCAL-XSC implementation. These results demonstrate that there are many cases in which the splitting strategy is more important for the efficiency of the algorithm than the use of preconditioners.
---
paper_title: (1) THE CLUSTER PROBLEM IN MULTIVARIATE GLOBAL OPTIMIZATION

paper_content:

We consider branch and bound methods for enclosing all unconstrained global minimizers of a nonconvex nonlinear twice-continuously differentiable objective function. In particular, we consider bounds obtained with interval arithmetic, with the “midpoint test,” but no acceleration procedures. Unless the lower bound is exact, the algorithm without acceleration procedures in general gives an undesirable cluster of boxes around each minimizer. In a previous paper, we analyzed this problem for univariate objective functions. In this paper, we generalize that analysis to multi-dimensional objective functions. As in the univariate case, the results show that the problem is highly related to the behavior of the objective function near the global minimizers and to the order of the corresponding interval extension.
---
paper_title: An Interval Branch and Bound Algorithm for Bound Constrained Optimization Problems

paper_content:

In this paper, we propose modifications to a prototypical branch and bound algorithm for nonlinear optimization so that the algorithm efficiently handles constrained problems with constant bound constraints. The modifications involve treating subregions of the boundary identically to interior regions during the branch and bound process, but using reduced gradients for the interval Newton method. The modifications also involve preconditioners for the interval Gauss-Seidel method which are optimal in the sense that their application selectively gives a coordinate bound of minimum width, a coordinate bound whose left endpoint is as large as possible, or a coordinate bound whose right endpoint is as small as possible. We give experimental results on a selection of problems with different properties.
---
paper_title: Subdivision Direction Selection In Interval Methods For Global Optimization

paper_content:

The role of the interval subdivision-selection rule is investigated in branch-and-bound algorithms for global optimization. The class of rules that allows convergence for the model algorithm is characterized, and it is shown that the four rules investigated satisfy the conditions of convergence. A numerical study with a wide spectrum of test problems indicates that there are substantial differences between the rules in terms of the required CPU time, the number of function and derivative evaluations, and space complexity, and two rules can provide substantial improvements in efficiency.
---
paper_title: Parallel global optimization using interval analysis

paper_content:

Finding the global minimum for an arbitrary differentiable function over an n-dimensional rectangle is an important problem in computational science, with applications in many disciplines. Ongoing research in this area has led to many exhaustive search methods that require significant computational effort. Our current research is aimed at identifying opportunities for parallelizing the search wherever possible so that the computing time is reduced, and the global minimum is obtained reliably for a wide variety of objective functions commonly explored in the literature. Our approach is to use a branch of applied mathematics known as Interval Analysis, which is a commonly used tool in obtaining lower and upper bounds for machine computations for the purpose of automatic error bounding. This ensures the reliability of the solutions obtained. We present a depth-first parallel branch and bound algorithm with acceleration methods that provides a significant reduction in run time compared to a popular breadth-first search algorithm. Our algorithm reliably obtains global minima for numerous test functions reported in the literature, with the highest speedup achieved for highly multimodal functions. Our algorithm possesses desirable properties of reliability, robustness, scalability, and load balancing, all of which will be demonstrated.
---
paper_title: Use of a Real-Valued Local Minimum in Parallel Interval Global Optimization

paper_content:

We consider a parallel method for finding the global minimum (and all of the global minimizers) of a continuous non-linear function f : D ! R, where D is an n-dimensional interval. The method combines one of the well known branch-and-bound interval search methods of Skelboe, Moore and Hansen with a real-valued optimization method. Initially we use a standard real-valued optimization method to find a local minimizer xp (or rather: a prediction of a local minimizer). Then the interval Newton method is applied to an interval Ip containing xp as its midpoint. Ip is chosen as large as possible under the restriction that the Newton interval method must converge when Ip is used as starting interval. In this way the original problem has been reduced to the problem of searching a domain DnIp which does not contain the local (and perhaps global) minimizer. The remaining domain is searched by the branch-and-bound interval method, starting by splitting the remaining domain into 2n intervals and hence avoiding Ip. This branch-and-bound search then either verifies that the point xp is the global minimizer, or the opposite is detected and it finds the global minimum (and the global minimizers) in the usual way. The combined method parallizes well. On one test case the combined method is faster than the branch-and-bound method itself. However, for another test case we get the opposite result. This is explained.
---
paper_title: Global Optimization Using Interval Analysis

paper_content:

Employing a closed set-theoretic foundation for interval computations, Global Optimization Using Interval Analysis simplifies algorithm construction and increases generality of interval arithmetic. This Second Edition contains an up-to-date discussion of interval methods for solving systems of nonlinear equations and global optimization problems. It expands and improves various aspects of its forerunner and features significant new discussions, such as those on the use of consistency methods to enhance algorithm performance. Provided algorithms are guaranteed to find and bound all solutions to these problems despite bounded errors in data, in approximations, and from use of rounded arithmetic.
---
paper_title: Epsilon-inflation in verification algorithms

paper_content:

Epsilon-inflation is often used in verification numerics to find an interval vector [x] e such that some interval function [f] maps [x] e into itself. We recall algorithms which use epsilon-inflation to verify this subset property [f] ([x] e ) ⊆ [x] e , and we derive criteria which guarantee that already finitely many inflation steps are sufficient to prove it. These criteria require [f] to be a P-contraction. We recall results on P-contractions, and we derive rules to verify them. We also introduce local P-contractions, and we use this concept to guarantee again the subset property above when using epsilon-inflation.
---
paper_title: Optimal centered forms

paper_content:

A simple expression for an “optimal” center of a centered form is presented. Among all possible centers within a given interval this center yields the greatest lower bound or the lowest upper bound of a centered form, respectively. It is also shown that one-sided isotonicity holds for such centered forms.
---
paper_title: Use of a Real-Valued Local Minimum in Parallel Interval Global Optimization

paper_content:

We consider a parallel method for finding the global minimum (and all of the global minimizers) of a continuous non-linear function f : D ! R, where D is an n-dimensional interval. The method combines one of the well known branch-and-bound interval search methods of Skelboe, Moore and Hansen with a real-valued optimization method. Initially we use a standard real-valued optimization method to find a local minimizer xp (or rather: a prediction of a local minimizer). Then the interval Newton method is applied to an interval Ip containing xp as its midpoint. Ip is chosen as large as possible under the restriction that the Newton interval method must converge when Ip is used as starting interval. In this way the original problem has been reduced to the problem of searching a domain DnIp which does not contain the local (and perhaps global) minimizer. The remaining domain is searched by the branch-and-bound interval method, starting by splitting the remaining domain into 2n intervals and hence avoiding Ip. This branch-and-bound search then either verifies that the point xp is the global minimizer, or the opposite is detected and it finds the global minimum (and the global minimizers) in the usual way. The combined method parallizes well. On one test case the combined method is faster than the branch-and-bound method itself. However, for another test case we get the opposite result. This is explained.
---
paper_title: Quadratic programming with one negative eigenvalue is NP-hard

paper_content:

We show that the problem of minimizing a concave quadratic function with one concave direction is NP-hard. This result can be interpreted as an attempt to understand exactly what makes nonconvex quadratic programming problems hard. Sahni in 1974 [8] showed that quadratic programming with a negative definite quadratic term (n negative eigenvalues) is NP-hard, whereas Kozlov, Tarasov and Hačijan [2] showed in 1979 that the ellipsoid algorithm solves the convex quadratic problem (no negative eigenvalues) in polynomial time. This report shows that even one negative eigenvalue makes the problem NP-hard.
---
paper_title: An Interval Branch and Bound Algorithm for Bound Constrained Optimization Problems

paper_content:

In this paper, we propose modifications to a prototypical branch and bound algorithm for nonlinear optimization so that the algorithm efficiently handles constrained problems with constant bound constraints. The modifications involve treating subregions of the boundary identically to interior regions during the branch and bound process, but using reduced gradients for the interval Newton method. The modifications also involve preconditioners for the interval Gauss-Seidel method which are optimal in the sense that their application selectively gives a coordinate bound of minimum width, a coordinate bound whose left endpoint is as large as possible, or a coordinate bound whose right endpoint is as small as possible. We give experimental results on a selection of problems with different properties.
---
paper_title: Global Optimization Using Interval Analysis

paper_content:

Employing a closed set-theoretic foundation for interval computations, Global Optimization Using Interval Analysis simplifies algorithm construction and increases generality of interval arithmetic. This Second Edition contains an up-to-date discussion of interval methods for solving systems of nonlinear equations and global optimization problems. It expands and improves various aspects of its forerunner and features significant new discussions, such as those on the use of consistency methods to enhance algorithm performance. Provided algorithms are guaranteed to find and bound all solutions to these problems despite bounded errors in data, in approximations, and from use of rounded arithmetic.
---
paper_title: A Review of Preconditioners for the Interval Gauss–Seidel Method

paper_content:

Interval Newton methods in conjunction with generalized bisection can form the basis of algorithms that find all real roots within a specified box X ⊂ Rn of a system of nonlinear equations F (X) = 0 with mathematical certainty, even in finite-precision arithmetic. In such methods, the system F (X) = 0 is transformed into a linear interval system 0 = F (M) + F′(X)(X −M); if interval arithmetic is then used to bound the solutions of this system, the resulting box X contains all roots of the nonlinear system. We may use the interval Gauss–Seidel method to find these solution bounds. In order to increase the overall efficiency of the interval Newton / generalized bisection algorithm, the linear interval system is multiplied by a preconditioner matrix Y before the interval Gauss–Seidel method is applied. Here, we review results we have obtained over the past few years concerning computation of such preconditioners. We emphasize importance and connecting relationships, and we cite references for the underlying elementary theory and other details.
---
paper_title: An interval algorithm for constrained global optimization

paper_content:

Abstract An interval algorithm for bounding the solutions of a constrained global optimization problem is described. The problem functions are assumed only to be continuous. It is shown how the computational cost of bounding a set which satisfies equality constraints can often be reduced if the equality constraint functions are assumed to be continuously differentiable. Numerical results are presented.
---
paper_title: On Verifying Feasibility in Equality Constrained Optimization Problems, preprint

paper_content:

Techniques for verifying feasibility of equality constraints are presented. The underlying verification procedures are similar to a proposed algorithm of Hansen, but various possibilities, as well as additional procedures for handling bound constraints, are investigated. The overall scheme differs from some algorithms in that it rigorously verifies exact (rather than approximate) feasibility. The scheme starts with an approximate feasible point, then constructs a box (i.e. a set of tolerances) about this point within which it is rigorously verified that a feasible point exists. Alternate ways of proceeding are compared, and numerical results on a set of test problems appear.
---
paper_title: Global Optimization Using Interval Analysis

paper_content:

Employing a closed set-theoretic foundation for interval computations, Global Optimization Using Interval Analysis simplifies algorithm construction and increases generality of interval arithmetic. This Second Edition contains an up-to-date discussion of interval methods for solving systems of nonlinear equations and global optimization problems. It expands and improves various aspects of its forerunner and features significant new discussions, such as those on the use of consistency methods to enhance algorithm performance. Provided algorithms are guaranteed to find and bound all solutions to these problems despite bounded errors in data, in approximations, and from use of rounded arithmetic.
---
paper_title: On Verifying Feasibility in Equality Constrained Optimization Problems, preprint

paper_content:

Techniques for verifying feasibility of equality constraints are presented. The underlying verification procedures are similar to a proposed algorithm of Hansen, but various possibilities, as well as additional procedures for handling bound constraints, are investigated. The overall scheme differs from some algorithms in that it rigorously verifies exact (rather than approximate) feasibility. The scheme starts with an approximate feasible point, then constructs a box (i.e. a set of tolerances) about this point within which it is rigorously verified that a feasible point exists. Alternate ways of proceeding are compared, and numerical results on a set of test problems appear.
---
paper_title: Quadratic programming with one negative eigenvalue is NP-hard

paper_content:

We show that the problem of minimizing a concave quadratic function with one concave direction is NP-hard. This result can be interpreted as an attempt to understand exactly what makes nonconvex quadratic programming problems hard. Sahni in 1974 [8] showed that quadratic programming with a negative definite quadratic term (n negative eigenvalues) is NP-hard, whereas Kozlov, Tarasov and Hačijan [2] showed in 1979 that the ellipsoid algorithm solves the convex quadratic problem (no negative eigenvalues) in polynomial time. This report shows that even one negative eigenvalue makes the problem NP-hard.
---
paper_title: An Interval Branch and Bound Algorithm for Bound Constrained Optimization Problems

paper_content:

In this paper, we propose modifications to a prototypical branch and bound algorithm for nonlinear optimization so that the algorithm efficiently handles constrained problems with constant bound constraints. The modifications involve treating subregions of the boundary identically to interior regions during the branch and bound process, but using reduced gradients for the interval Newton method. The modifications also involve preconditioners for the interval Gauss-Seidel method which are optimal in the sense that their application selectively gives a coordinate bound of minimum width, a coordinate bound whose left endpoint is as large as possible, or a coordinate bound whose right endpoint is as small as possible. We give experimental results on a selection of problems with different properties.
---
paper_title: Global Optimization Using Interval Analysis

paper_content:

Employing a closed set-theoretic foundation for interval computations, Global Optimization Using Interval Analysis simplifies algorithm construction and increases generality of interval arithmetic. This Second Edition contains an up-to-date discussion of interval methods for solving systems of nonlinear equations and global optimization problems. It expands and improves various aspects of its forerunner and features significant new discussions, such as those on the use of consistency methods to enhance algorithm performance. Provided algorithms are guaranteed to find and bound all solutions to these problems despite bounded errors in data, in approximations, and from use of rounded arithmetic.
---
paper_title: An Interval Branch and Bound Algorithm for Bound Constrained Optimization Problems

paper_content:

In this paper, we propose modifications to a prototypical branch and bound algorithm for nonlinear optimization so that the algorithm efficiently handles constrained problems with constant bound constraints. The modifications involve treating subregions of the boundary identically to interior regions during the branch and bound process, but using reduced gradients for the interval Newton method. The modifications also involve preconditioners for the interval Gauss-Seidel method which are optimal in the sense that their application selectively gives a coordinate bound of minimum width, a coordinate bound whose left endpoint is as large as possible, or a coordinate bound whose right endpoint is as small as possible. We give experimental results on a selection of problems with different properties.
---
paper_title: Empirical Evaluation of Innovations in Interval Branch and Bound Algorithms for Nonlinear Algebraic Systems

paper_content:

Interval branch and bound algorithms for finding all roots use a combination of a computational existence/uniqueness procedure and a tessellation process (generalized bisection). Such algorithms identify, with mathematical rigor, a set of boxes that contains unique roots and a second set within which all remaining roots must lie. Though each root is contained in a box in one of the sets, the second set may have several boxes in clusters near a single root. Thus, the output is of higher quality if there are relatively more boxes in the first set. In contrast to previously implemented similar techniques, a box expansion technique in this paper, based on using an approximate root finder, $\epsilon$-inflation, and exact set complementation, decreases the size of the second set, increases the size of the first set, and never loses roots. ::: In addition to the expansion technique, use of second-order extensions to eliminate small boxes that do not contain roots, and interval slopes versus interval derivative matrices are studied. These items are evaluated empirically on a significant test problem set, within a Fortran-90 environment designed for such purposes. The results are compared with previous results and show that careful incorporation of the techniques yields both quantitatively and qualitatively superior computer codes.
---
paper_title: Bounds for lagrange multipliers and optimal points

paper_content:

Abstract We describe two methods for use in constrained optimization problems. One method computes guaranteed bounds on both the Lagrange multipliers and on the location of the optimal points. The other method bounds the Lagrange multipliers only. Both methods provide bounds for perturbed problems. The methods can prove (in the presence of rounding) the existence or nonexistence of a solution in a given region.
---
paper_title: A Review of Preconditioners for the Interval Gauss–Seidel Method

paper_content:

Interval Newton methods in conjunction with generalized bisection can form the basis of algorithms that find all real roots within a specified box X ⊂ Rn of a system of nonlinear equations F (X) = 0 with mathematical certainty, even in finite-precision arithmetic. In such methods, the system F (X) = 0 is transformed into a linear interval system 0 = F (M) + F′(X)(X −M); if interval arithmetic is then used to bound the solutions of this system, the resulting box X contains all roots of the nonlinear system. We may use the interval Gauss–Seidel method to find these solution bounds. In order to increase the overall efficiency of the interval Newton / generalized bisection algorithm, the linear interval system is multiplied by a preconditioner matrix Y before the interval Gauss–Seidel method is applied. Here, we review results we have obtained over the past few years concerning computation of such preconditioners. We emphasize importance and connecting relationships, and we cite references for the underlying elementary theory and other details.
---
paper_title: Use of a Real-Valued Local Minimum in Parallel Interval Global Optimization

paper_content:

We consider a parallel method for finding the global minimum (and all of the global minimizers) of a continuous non-linear function f : D ! R, where D is an n-dimensional interval. The method combines one of the well known branch-and-bound interval search methods of Skelboe, Moore and Hansen with a real-valued optimization method. Initially we use a standard real-valued optimization method to find a local minimizer xp (or rather: a prediction of a local minimizer). Then the interval Newton method is applied to an interval Ip containing xp as its midpoint. Ip is chosen as large as possible under the restriction that the Newton interval method must converge when Ip is used as starting interval. In this way the original problem has been reduced to the problem of searching a domain DnIp which does not contain the local (and perhaps global) minimizer. The remaining domain is searched by the branch-and-bound interval method, starting by splitting the remaining domain into 2n intervals and hence avoiding Ip. This branch-and-bound search then either verifies that the point xp is the global minimizer, or the opposite is detected and it finds the global minimum (and the global minimizers) in the usual way. The combined method parallizes well. On one test case the combined method is faster than the branch-and-bound method itself. However, for another test case we get the opposite result. This is explained.
---
paper_title: Optimal centered forms

paper_content:

A simple expression for an “optimal” center of a centered form is presented. Among all possible centers within a given interval this center yields the greatest lower bound or the lowest upper bound of a centered form, respectively. It is also shown that one-sided isotonicity holds for such centered forms.
---
paper_title: On Verifying Feasibility in Equality Constrained Optimization Problems, preprint

paper_content:

Techniques for verifying feasibility of equality constraints are presented. The underlying verification procedures are similar to a proposed algorithm of Hansen, but various possibilities, as well as additional procedures for handling bound constraints, are investigated. The overall scheme differs from some algorithms in that it rigorously verifies exact (rather than approximate) feasibility. The scheme starts with an approximate feasible point, then constructs a box (i.e. a set of tolerances) about this point within which it is rigorously verified that a feasible point exists. Alternate ways of proceeding are compared, and numerical results on a set of test problems appear.
---
paper_title: Bounds for lagrange multipliers and optimal points

paper_content:

Abstract We describe two methods for use in constrained optimization problems. One method computes guaranteed bounds on both the Lagrange multipliers and on the location of the optimal points. The other method bounds the Lagrange multipliers only. Both methods provide bounds for perturbed problems. The methods can prove (in the presence of rounding) the existence or nonexistence of a solution in a given region.
---
paper_title: On Verifying Feasibility in Equality Constrained Optimization Problems, preprint

paper_content:

Techniques for verifying feasibility of equality constraints are presented. The underlying verification procedures are similar to a proposed algorithm of Hansen, but various possibilities, as well as additional procedures for handling bound constraints, are investigated. The overall scheme differs from some algorithms in that it rigorously verifies exact (rather than approximate) feasibility. The scheme starts with an approximate feasible point, then constructs a box (i.e. a set of tolerances) about this point within which it is rigorously verified that a feasible point exists. Alternate ways of proceeding are compared, and numerical results on a set of test problems appear.
---
paper_title: Global Optimization Using Interval Analysis

paper_content:

Employing a closed set-theoretic foundation for interval computations, Global Optimization Using Interval Analysis simplifies algorithm construction and increases generality of interval arithmetic. This Second Edition contains an up-to-date discussion of interval methods for solving systems of nonlinear equations and global optimization problems. It expands and improves various aspects of its forerunner and features significant new discussions, such as those on the use of consistency methods to enhance algorithm performance. Provided algorithms are guaranteed to find and bound all solutions to these problems despite bounded errors in data, in approximations, and from use of rounded arithmetic.
---
paper_title: A Collection of Test Problems for Constrained Global Optimization Algorithms

paper_content:

Quadratic programming test problems.- Quadratically constrained test problems.- Nonlinear programming test problems.- Distillation column sequencing test problems.- Pooling/blending test problems.- Heat exchanger network synthesis test problems.- Phase and chemical reaction equilibrium test problems.- Comlpex chemical reactor network test problems.- Reactor-seperator-recycle system test problems.- Mechanical design test problems.- VLSI design test problems.
---
paper_title: Computation of the solutions of nonlinear polynomial systems

paper_content:

Abstract: A fundamental problem in computer aided design is the efficient computation of all roots of a system of nonlinear polynomial equations inn variables which lie within ann-dimensional @?. We present two techniques designed to solve such problems, which rely on representation of polynomials in the multivariate Bernstein basis and subdivision. In order to isolate all of the roots within the given domain, each method uses a different scheme for constructing a series of bounding @?es; the first method projects control polyhedra onto a set of coordinate planes, and the second employs linear optimization. We also examine in detail the local convergence properties of the two methods, proving that the former is quadratically convergent forn=1 and linearly convergent forn 1, while the latter is quadratically convergent for alln. Worst-case complexity analysis, as well as analysis of actual running times are performed.
---
paper_title: Algorithm 681: INTBIS, a portable interval Newton/bisection package

paper_content:

We present a portable software package for finding all real roots of a system of nonlinear equations within a region defined by bounds on the variables. Where practical, the package should find all roots with mathematical certainty. Though based on interval Newton methods, it is self-contained. It allows various control and output options and does not require programming if the equations are polynomials; it is structured for further algorithmic research. Its practicality does not depend in a simple way on the dimension of the system or on the degree of nonlinearity.
---
paper_title: Interval Methods for Processing Geometric Objects

paper_content:

In this approach, the parametric form is applied without the usual computational nightmare. The key is to view the parametric range as an interval, relying on subdivision algorithms.
---
paper_title: Comparison of three curve intersection algorithms

paper_content:

This paper treats the problem of how one can best compute the points of intersection of two planar rational curves. Three different algorithms are compared: the well known Bezier subdivision algorithm, a subdivision algorithm based on interval arithmetic, and the implicitization approach. Implementation considerations are discussed, with particular focus on how to make the implicitization method robust and fast. Report is made on a test in which the algorithms solved hundreds of randomly generated problems to eight digits of accuracy. The implicitization algorithm was faster than the others by a factor of five for degree two curves; by a factor of four for cubic curves; by a factor of three for quartic curves; and the interval method was faster for quintic curves by a factor of two.
---
paper_title: Global Optimization Using Interval Analysis

paper_content:

Employing a closed set-theoretic foundation for interval computations, Global Optimization Using Interval Analysis simplifies algorithm construction and increases generality of interval arithmetic. This Second Edition contains an up-to-date discussion of interval methods for solving systems of nonlinear equations and global optimization problems. It expands and improves various aspects of its forerunner and features significant new discussions, such as those on the use of consistency methods to enhance algorithm performance. Provided algorithms are guaranteed to find and bound all solutions to these problems despite bounded errors in data, in approximations, and from use of rounded arithmetic.
---

Title: A Review of Techniques in the Verified Solution of Constrained Global Optimization Problems

Section 1: Introduction, Basic Ideas and Literature
Description 1: This section introduces the main concepts and reviews the literature on constrained global optimization problems.

Section 2: Early and Simplified Algorithms
Description 2: This section discusses the early and simplified interval global optimization algorithms.

Section 3: Recent Practical Algorithms
Description 3: This section reviews more recent algorithms and their practical implementations.

Section 4: Notation
Description 4: This section explains the notation used throughout the paper.

Section 5: On Constrained Optimization Problems
Description 5: This section elaborates on fundamental methods and techniques for handling constrained optimization problems.

Section 6: Checking Feasibility / Infeasibility
Description 6: This section discusses methods for verifying feasibility or infeasibility with respect to constraints.

Section 7: Handling Bound Constraints
Description 7: This section focuses on techniques to handle bound constraints in optimization problems.

Section 8: On Use of Interval Newton Methods
Description 8: This section explains how interval Newton methods are utilized in the context of optimization.

Section 9: Fritz-John Conditions
Description 9: This section introduces the Fritz-John conditions for verifying feasibility and local optimality.

Section 10: Applications
Description 10: This section reviews successful applications of verified global optimization codes.

Section 11: Summary and Present Work
Description 11: This section summarizes the findings and outlines ongoing and future work related to the topic.