Global Optimization of Discontinuous Functions

Although discontinuities are common to many optimization problems, e.g., process synthesis with discontinuous investment costs, batch production scheduling, and hybrid dynamic optimization problems with discontinuities, available deterministic optimization methods are not capable of solving such problems directly. Smoothness assumptions are essential when using efficient local optimization algorithms, and current global optimization methods lack convex relaxation techniques that can cope with discontinuities. Therefore, different ideas need to be pursued to allow for optimization of problems with discontinuous functions. In the past, researchers have generalized the notion of the gradient to discontinuous functions in an attempt to derive local optimality conditions. Others have approximated the problem by replacing the discontinuous function with a smooth approximation or by convolving it with mollifiers. While the former leads to approximation errors and numerical difficulties, the latter results in quadrature problems of possibly high dimensionality. Another possibility often pursued is to reformulate the problem as a mixed-integer program. Depending on the structure of the problem, such a reformulation can increase the number of variables drastically. Branch-and-bound algorithms used in global optimization are known to scale exponentially with the number of variables and thus it may be beneficial if the discontinuous problem can be solved directly.

A different idea is introduced here to tackle discontinuous optimization problems by developing a method to construct continuous convex and concave relaxations of discontinuous functions. Equipped with this tool, discontinuous optimization problems can be solved to guaranteed global optimality using a branch-and-bound framework. Hence, it may be conceptually simpler to solve discontinuous optimization problems to global optimality than it is to identify locally optimal solutions.

We consider problems

inf_x∈X f(x)

where f: X→ℝ is a factorable bounded function with discontinuities and X⊂ℝⁿ. To obtain convex relaxations of f, we build upon McCormick's well-known technique [2] for the derivation of convex and concave relaxations of a factorable function, which is currently utilized in global optimization of continuous optimization problems [3, 5]. We demonstrate how this method can be extended to bounded factorable, but not necessarily continuous, functions by modeling discontinuities using a step function [6]. We show that most theoretical results developed for the continuous case [4] hold even when the assumption of continuity is dropped.

The proposed method has been implemented by adding the step function as an intrinsic function to the open-source C++ library libMC [1]. It uses operator overloading to construct objects propagating bounds and relaxations alongside each real-valued variable of a computer program. The nonsmooth (but continuous) convex programs in the lower bounding problem are solved using a bundle method whereas upper bounds are obtained by evaluating the original function at a solution of the lower bounding problem. A branch-and-bound scheme converges to an optimal solution.

Examples will be presented to demonstrate the proposed method. Aside from showcasing the method on generic mathematical problems, we will also consider problems derived from optimal design and sizing of heat exchanger networks where capital cost varies discontinuously depending on equipment size.

References

[1] B. Chachuat, A. Mitsos, and P. I. Barton. libMC – A numeric library for McCormick relaxation of factorable functions. http://yoric.mit.edu/libMC/, 2007.

[2] G. P. McCormick. Computability of global solutions to factorable nonconvex programs: Part I – Convex underestimating problems. Mathematical Programming, 10:147–175, 1976.

[3] A. Mitsos, B. Chachuat, and P. I. Barton. McCormick-based relaxations of algorithms. SIAM Journal on Optimization, 20:573–601, 2009.

[4] J. K. Scott, M. D. Stuber, and P. I. Barton. Generalized McCormick relaxations. Submitted. 2009.

[5] M. Tawarmalani and N. V. Sahinidis. Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming. Kluwer Academic Publishers, Dordrecht, 2002.

[6] I. Zang. Discontinuous Optimization by Smoothing. Mathematics of Operations Research, 6:140–152, 1981.