Global optimization of bounded factorable functions with discontinuities

A deterministic global optimization method is developed for a class of discontinuous functions. McCormick’s method to obtain relaxations of nonconvex functions is extended to discontinuous factorable functions by representing a discontinuity with a step function. The properties of the relaxations are analyzed in detail; in particular, convergence of the relaxations to the function is established given some assumptions on the bounds derived from interval arithmetic. The obtained convex relaxations are used in a branch-and-bound scheme to formulate lower bounding problems. Furthermore, convergence of the branch-and-bound algorithm for discontinuous functions is analyzed and assumptions are derived to guarantee convergence. A key advantage of the proposed method over reformulating the discontinuous problem as a MINLP or MPEC is avoiding the increase in problem size that slows global optimization. Several numerical examples for the global optimization of functions with discontinuities are presented, including ones taken from process design and equipment sizing as well as discrete-time hybrid systems.     

The theoretical and empirical rate of convergence for geometric branch-and-bound methods

Geometric branch-and-bound solution methods, in particular the big square small square technique and its many generalizations, are popular solution approaches for non-convex global optimization problems. Most of these approaches differ in the lower bounds they use which have been compared empirically in a few studies. The aim of this paper is to introduce a general convergence theory which allows theoretical results about the different bounds used. To this end we introduce the concept of a bounding operation and propose a new definition of the rate of convergence for geometric branch-and-bound methods. We discuss the rate of convergence for some well-known bounding operations as well as for a new general bounding operation with an arbitrary rate of convergence. This comparison is done from a theoretical point of view. The results we present are justified by some numerical experiments using the Weber problem on the plane with some negative weights.     

Optimal Multisections in Interval Branch-and-Bound Methods of Global Optimization

In this paper we define multisections of intervals that yield sharp lower bounds in branch-and-bound type methods for interval global optimization. A so called 'generalized kite', defined for differentiable univariate functions, is built simultaneously with linear boundary forms and suitably chosen centered forms. Proofs for existence and uniqueness of optimal cuts are given. The method described may be used either as an accelerating device or in a global optimization algorithm with an efficient pruning effect. A more general principle for decomposition of boxes is suggested.     

A Global Optimization Algorithm using Lagrangian Underestimates and the Interval Newton Method

Convex relaxations can be used to obtain lower bounds on the optimal objective function value of nonconvex quadratically constrained quadratic programs. However, for some problems, significantly better bounds can be obtained by minimizing the restricted Lagrangian function for a given estimate of the Lagrange multipliers. The difficulty in utilizing Lagrangian duality within a global optimization context is that the restricted Lagrangian is often nonconvex. Minimizing a convex underestimate of the restricted Lagrangian overcomes this difficulty and facilitates the use of Lagrangian duality within a global optimization framework. A branch-and-bound algorithm is presented that relies on these Lagrangian underestimates to provide lower bounds and on the interval Newton method to facilitate convergence in the neighborhood of the global solution. Computational results show that the algorithm compares favorably to the Reformulation–Linearization Technique for problems with a favorable structure.     

Reliable Numerical Computation in Civil Engineering

Civil engineering is a field – as are many other engineering sciences – where most of the methods used for solving optimization problems are based on experience and experiments, and models using local information, but drawn from global models. The present work outlines an interesting class of problems from this field, and initiates some possible ways to solve those problems utilizing the wide tool capabilities of interval arithmetic for error handling and interval branch-and-bound algorithms to solve the original or modified industrial models automating civil engineers' work. The investigations are in the first state but are promising both in a theoretical and in a practical sense.     

Heuristic Rejection in Interval Global Optimization

Based on the investigation carried out in Ref. 1, this paper incorporates new studies about the properties of inclusion functions on subintervals while a branch-and-bound algorithm is solving global optimization problems. It is found that the relative place of the global minimum value within the inclusion function value of the objective function at the current interval indicates mostly whether the given interval is close to a minimizer point. This information is used in a heuristic interval rejection rule that can save a considerable amount of computation. Illustrative examples are discussed and an extended numerical study shows the advantages of the new approach.     

Branch-and-Sandwich: a deterministic global optimization algorithm for optimistic bilevel programming problems. Part I: Theoretical development

We present a global optimization algorithm, Branch-and-Sandwich, for optimistic bilevel programming problems that satisfy a regularity condition in the inner problem. The functions involved are assumed to be nonconvex and twice continuously differentiable. The proposed approach can be interpreted as the exploration of two solution spaces (corresponding to the inner and the outer problems) using a single branch-and-bound tree. A novel branching scheme is developed such that classical branch-and-bound is applied to both spaces without violating the hierarchy in the decisions and the requirement for (global) optimality in the inner problem. To achieve this, the well-known features of branch-and-bound algorithms are customized appropriately. For instance, two pairs of lower and upper bounds are computed: one for the outer optimal objective value and the other for the inner value function. The proposed bounding problems do not grow in size during the algorithm and are obtained from the corresponding problems at the parent node.     

Duality Bound Method for the General Quadratic Programming Problem with Quadratic Constraints

The purpose of this article is to develop a branch-and-bound algorithm using duality bounds for the general quadratically-constrained quadratic programming problem and having the following properties: (i) duality bounds are computed by solving ordinary linear programs; (ii) they are at least as good as the lower bounds obtained by solving relaxed problems, in which each nonconvex function is replaced by its convex envelope; (iii) standard convergence properties of branch-and-bound algorithms for nonconvex global optimization problems are guaranteed. Numerical results of preliminary computational experiments for the case of one quadratic constraint are reported.     

On interval branch-and-bound for additively separable functions with common variables

Interval branch-and-bound (B&B) algorithms are powerful methods which look for guaranteed solutions of global optimisation problems. The computational effort needed to reach this aim, increases exponentially with the problem dimension in the worst case. For separable functions this effort is less, as lower dimensional sub-problems can be solved individually. The question is how to design specific methods for cases where the objective function can be considered separable, but common variables occur in the sub-problems. This paper is devoted to establish the bases of B&B algorithms for separable problems. New B&B rules are presented based on derived properties to compute bounds. A numerical illustration is elaborated with a test-bed of problems mostly generated by combining traditional box constrained global optimisation problems, to show the potential of using the derived theoretical basis.     

Combined bound-grid-factor constraints for enhancing RLT relaxations for polynomial programs

This paper studies the global optimization of polynomial programming problems using Reformulation-Linearization Technique (RLT)-based linear programming (LP) relaxations. We introduce a new class of bound-grid-factor constraints that can be judiciously used to augment the basic RLT relaxations in order to improve the quality of lower bounds and enhance the performance of global branch-and-bound algorithms. Certain theoretical properties are established that shed light on the effect of these valid inequalities in driving the discrepancies between RLT variables and their associated nonlinear products to zero. To preserve computational expediency while promoting efficiency, we propose certain concurrent and sequential cut generation routines and various grid-factor selection rules. The results indicate a significant tightening of lower bounds, which yields an overall reduction in computational effort for solving a test-bed of polynomial programming problems to global optimality in comparison with the basic RLT procedure as well as the commercial software BARON.     

Geometric branch-and-bound methods for constrained global optimization problems

Geometric branch-and-bound methods are popular solution algorithms in deterministic global optimization to solve problems in small dimensions. The aim of this paper is to formulate a geometric branch-and-bound method for constrained global optimization problems which allows the use of arbitrary bounding operations. In particular, our main goal is to prove the convergence of the suggested method using the concept of the rate of convergence in geometric branch-and-bound methods as introduced in some recent publications. Furthermore, some efficient further discarding tests using necessary conditions for optimality are derived and illustrated numerically on an obnoxious facility location problem.     

Multisection in Interval Branch-and-Bound Methods for Global Optimization II. Numerical Tests

We have investigated variants of interval branch-and-bound algorithms for global optimization where the bisection step was substituted by the subdivision of the current, actual interval into many subintervals in a single iteration step. The results are published in two papers, the first one contains the theoretical investigations on the convergence properties. An extensive numerical study indicates that multisection can substantially improve the efficiency of interval global optimization procedures, and multisection seems to be indispensable in solving hard global optimization problems in a reliable way.     

New methods for calculating \alpha BB-type underestimators

Most branch-and-bound algorithms in global optimization depend on convex underestimators to calculate lower bounds of a minimization objective function. The $\alpha $ BB methodology produces such underestimators for sufficiently smooth functions by analyzing interval Hessian approximations. Several methods to rigorously determine the $\alpha $ BB parameters have been proposed, varying in tightness and computational complexity. We present new polynomial-time methods and compare their properties to existing approaches. The new methods are based on classical eigenvalue bounds from linear algebra and a more recent result on interval matrices. We show how parameters can be optimized with respect to the average underestimation error, in addition to the maximum error commonly used in $\alpha $ BB methods. Numerical comparisons are made, based on test functions and a set of randomly generated interval Hessians. The paper shows the relative strengths of the methods, and proves exact results where one method dominates another.     

What can interval analysis do for global optimization?

An overview of interval arithmetical tools and basic techniques is presented that can be used to construct deterministic global optimization algorithms. These tools are applicable to unconstrained and constrained optimization as well as to nonsmooth optimization and to problems over unbounded domains. Since almost all interval based global optimization algorithms use branch-and-bound methods with iterated bisection of the problem domain we also embed our overview in such a setting.     

Global Solution of Optimization Problems with Parameter-Embedded Linear Dynamic Systems

This paper develops a theory for the global solution of nonconvex optimization problems with parameter-embedded linear dynamic systems. A quite general problem formulation is introduced and a solution is shown to exists. A convexity theory for integrals is then developed to construct convex relaxations for utilization in a branch-and-bound framework to calculate a global minimum. Interval analysis is employed to generate bounds on the state variables implied by the bounds on the embedded parameters. These bounds, along with basic integration theory, are used to prove convergence of the branch-and-bound algorithm to the global minimum of the optimization problem. The implementation of the algorithm is then considered and several numerical case studies are examined thoroughly     

Computing closely matching upper and lower bounds on textile nesting problems

We consider an industrial cutting problem in textile manufacturing and report on algorithms for computing cutting images and lower bounds on waste for this problem. For the upper bounds we use greedy strategies based on hodographs and global optimization based on simulated annealing. For the lower bounds we use branch-and-bound methods for computing optimal solutions of placement subproblems that determine the performance of the overall subproblem. The upper bounds are computed in less than an hour on a common-day workstation and are competitive in quality with results obtained by human nesters. The lower bounds take a few hours to compute and are within 0.4% of the upper bound for certain types of clothing (e.g., for pants).     

Interval bounds on the solutions of semi-explicit index-one DAEs. Part 1: analysis

This article presents two methods for computing interval bounds on the solutions of nonlinear, semi-explicit, index-one differential-algebraic equations (DAEs). Part 1 presents theoretical developments, while Part 2 discusses implementation and numerical examples. The primary theoretical contributions are (1) an interval inclusion test for existence and uniqueness of a solution, and (2) sufficient conditions, in terms of differential inequalities, for two functions to describe componentwise upper and lower bounds on this solution, point-wise in the independent variable. The first proposed method applies these results sequentially in a two-phase algorithm analogous to validated integration methods for ordinary differential equations. The second method unifies these steps to characterize bounds as the solutions of an auxiliary system of DAEs. Efficient implementations of both are described using interval computations and demonstrated on numerical examples.     

Interval bounds on the solutions of semi-explicit index-one DAEs. Part 2: computation

This article presents two methods for computing interval bounds on the solutions of nonlinear, semi-explicit, index-one differential-algebraic equations (DAEs). Part 1 presents theoretical developments, while Part 2 discusses implementation and numerical examples. The primary theoretical contributions are (1) an interval inclusion test for existence and uniqueness of a solution, and (2) sufficient conditions, in terms of differential inequalities, for two functions to describe componentwise upper and lower bounds on this solution, point-wise in the independent variable. The first proposed method applies these results sequentially in a two-phase algorithm analogous to validated integration methods for ordinary differential equations (ODEs). The second method unifies these steps to characterize bounds as the solutions of an auxiliary system of DAEs. Efficient implementations of both are described using interval computations and demonstrated on numerical examples.     

Branch and probability bound methods in multi-objective optimization

An approach to non-convex multi-objective optimization problems is considered where only the values of objective functions are required by the algorithm. The proposed approach is a generalization of the probabilistic branch-and-bound approach well applicable to complicated problems of single-objective global optimization. In the present paper the concept of probabilistic branch-and-bound based multi-objective optimization algorithms is discussed, and some illustrations are presented.     

Dual Bounds and Optimality Cuts for All-Quadratic Programs with Convex Constraints

A central problem of branch-and-bound methods for global optimization is that often a lower bound do not match with the optimal value of the corresponding subproblem even if the diameter of the partition set shrinks to zero. This can lead to a large number of subdivisions preventing the method from terminating in reasonable time. For the all-quadratic optimization problem with convex constraints we present optimality cuts which cut off a given local minimizer from the feasible set. We propose a branch-and-bound algorithm using optimality cuts which is finite if all global minimizers fulfill a certain second order optimality condition. The optimality cuts are based on the formulation of a dual problem where additional redundant constraints are added. This technique is also used for constructing tight lower bounds. Moreover we present for the box-constrained and the standard quadratic programming problem dual bounds which have under certain conditions a zero duality gap.