(132a) 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.