Global Optimization in Action

Global optimization is aimed at finding the best solution of constrained optimization problems which (may) also have various local optima. The objective of Part 1 (Chapters 1.1 and 1.2) is to provide a relatively short and informal survey of the spectrum of models and methods in global optimization, with a few concise references to applications, when appropriate.

The brief discussion of some problem types in global optimization, presented in Chapter 1.1, points towards the need of choosing suitable strategies to solve diverse instances of the generic GOP statement (1.1.1). Indeed, there exists a broad variety of global optimization methods. In existing monographs and surveys, these are classified following several different organizing principles: consult, for example, Dixon and Szegö (1975, 1978), Strongin (1978), Žilinskas (1986), Pardalos and Rosen (1987), Forgó (1988), Rinnooy Kan and Timmer (1989), Törn and Žilinskas (1989), Horst (1990), Horst and Thy (1990, 1993), Zhigljaysky (1991), Zhigljaysky and Žilinskas (1991), Horst and Pardalos (1995).

Consider the general continuous global optimization problem (CGOP) stated as

Let us assume that the global optimization problem CGOP (2.1.1) or LGOp (2.1.9) is to be solved by an adaptive partition strategy which, in its basic structure, follows the partition algorithm scheme (PAS) described in Section 2.1.2.

In the simplest and most frequently studied special case of the general GOP, D is a one-dimensional finite interval. Let D = [a, b], −∞ < a < b < ∞, and f a (possibly) multiextremal continuous or Lipschitz function defined on [a, b]. Applying the notation introduced in Chapter 2.1, the corresponding problem statements are And

The present chapter is devoted to the analysis of adaptive partition strategies to solve the multivariate global optimization problem Where Obviously, (2.4.1) is a special case of the general GOP stated in Section 2.1.1, if we suppose the continuity or Lipschitz-continuity of f. As earlier, X* denotes the set of globally optimal solutions to (2.4.1), and z* = f(x*) for x* ∈ X*.

The case of simplex feasible regions is common in a number of important practical applications of global optimization: examples will be discussed later, in Part 4. Typically, the simplex plays a similar role to the interval feasible set in the previous chapters of Part 2; that is, it defines the explicit (‘vague’) bounds related to the globally optimal solution which is sought. According to this interpretation, one would expect again that the optimal solution is, typically, an interior point of the simplex feasible set.

In this chapter we shall investigate the global optimization problem, specialized as In (2.6.1), D ⊂ ℝ ⁿ is a robust, bounded and convex subset of the real n-space, and the Lipschitzian objective function f: D →ℝ ¹ is (possibly) multiextremal on the set D. Observe that this problem is significantly more general than the case of interval or simplex feasible regions studied in previous chapters of Part 2: consequently, it is not obvious how a PAS type strategy could be directly realized for solving (2.6.1).

In the preceding chapter an approach was proposed to solve multiextremal optimization problems on convex (robust and compact) sets, with a direct extension applicable to star domains. To realize this method, a simply implementable extension of the objective function to an interval embedding of the feasible set was suggested. Evidently, the numerical tractability of this approach depends crucially on the uniqueness of the boundary point x _h = x _h (x) on the segment x⁰ +λ (x − x ⁰), (x ⁰ ∈ int(D) given, x ∈ D ₀\D arbitrary point, 0 ≤ λ ≤ 1).

In Part 2, a general framework was provided for analysing and constructing adaptive partition algorithms Specific instances of the generic partition algorithm scheme (PAS, as introduced in Section 2.1.2) can be applied to solve a broad class of global optimization problems with continuous or Lipschitz-continuous structure. The case of one- and multidimensional intervals and simplices, and more general convex, star and Lipschitzian feasible sets was discussed in detail.

We shall consider again the Lipschitz global optimization problem on a finite n-interval [a, b]: under the analytical conditions stated in Chapter 2.4; in particular, f is assumed to be Lipschitz-continuous with some constant L. As previously, the—not necessarily unique—optimal solution of this LGOP will be denoted by x* ∈ X*, and f* = f(x*). Additionally, the set of accumulation points generated by a PAS-type globally convergent adaptive partition algorithm will be denoted again by X ^a .

Consider now the Lipschitzian global optimization problem in the following general form: In accordance with the discussion in Chapter 2.7, we shall assume that D is the closure of a nonempty, bounded, open set in the real n-dimensional space ℝ ⁿ , and that the constraint functions f _i , i = 0,1,..., I, are all Lipschitz-continuous on D, with corresponding Lipschitz-constants L _i = L _i (D,f _i ), i = 0,1,..., I. In other words, the inequalities are assumed to hold for all pairs of x, y from D.

The general framework and underlying convergence theory of adaptive partition algorithms in global optimization leave ample room for constructing robust and effective, computationally viable algorithm-instances. The program system described below has been implemented (in gradually developed versions), extensively tested, and applied by this author in the past decade. This, of course, does not imply any notion of ‘perfection’—in fact, the program modules have often been (and surely will be) modified and improved, not infrequently in connection with new applications.

In deterministic management models it is assumed that all relevant problem characteristics are known with certainty (or that with respect to these characteristics sufficiently exact point estimates can be provided). Although this assumption can be essentially valid in connection with many engineering problems, it certainly does not hold automatically, for instance, in the context of environmental modelling and decision making. To illustrate this point, note that—even in reasonably ‘well-defined’ engineering systems—the expert estimates of system failure probabilities and consequences may differ by several orders of magnitude (especially in the case of ‘rare’ events with unforeseeable serious consequences).

Consider the following stochastic programming problem: In (3.6.1), x is a decision vector to be selected from a closed, bounded subset D ₀ of the n-dimensional real Euclidean space ℝ ⁿ ; y is a q-dimensional vector valued random variable; f _i , i = 0, 1,...,I, are respectively defined measurable functions; E is the symbol of mathematical expectation (the expected values are supposed to exist). Note that (3.6.1) is a fairly general stochastic programming model form; it encompasses—under suitable transformations—the ‘model block’ and types discussed in the previous chapter.

As discussed in the previous two chapters, in stochastic optimization problems some or all of the defining functions (that is, objective and constraints in the model (3.6.1)) depend not only on the decision variables, but also on certain random factors. In such cases the optimization procedure needs to be combined with some—usually time-consuming—function value estimation method, such as experiments or Monte Carlo simulation. Stochastic programming formulations of various engineering or economic design problems (Prékopa, 1980; Ermoliev and Wets, 1988, etc.) may serve as examples of this situation. Obviously, in such cases it is desirable to decrease the number of necessary realizations of the involved random factors as much as possible, while prescribing accuracy and reliability levels (confidence intervals) of the estimated function values: this issue will be addressed below.

The best approximation of a function h by means of a (parameterized) family of functions H has a great many applications in numerical analysis, natural sciences, engineering, and economics. Below we shall consider this problem in a fairly general setting (Pintér, 1992b), and then show the relevance of Lipschitzian global optimization for its solution.

Numerous decision problems related, for example, to environmental monitoring, regional solid waste management, manufacturing systems, transportation services, and so forth, depend essentially on the choice of a relatively small number of ‘primary facilities’ (such as, for example, water quality analysis laboratories, waste disposal sites, warehouses, bus terminals or other facilities serving customers, or multipurpose machines in a workshop environment). Once the strategic facility design/location decision is made, the long-term operational characteristics of the system depend on the assignment of a—usually (much) larger—number of given entities (data to be grouped, water quality measurement sites in a region, population affected by the waste disposal sites, customers, users of public transport, jobs in a workshop, etc.) to the ‘primary facilities’ selected at the first stage. In many such cases, the primary (strategic) locational decisions are to be optimized, while the overall system performance (for example, total investment/setup costs plus long-term discounted operational costs) can be assessed—for each primary decision—via ‘expensive’ evaluation methods: algorithmic solution of embedded optimization problems, stochastic simulation, and so forth. For related discussions and examples, the reader is referred, for example, to Cormack (1971), Hartigan (1975), Jacobsen and Madsen (1980), Dempster, Fisher, Jansen, Lageweg, Lenstra and Rinnooy Kan (1981), Gordon (1981), Muroga (1982), Bodin, Golden, Assad and Ball (1983), Florian (1984), Golden and Assad (1986), Nitti and Speranza (1987), Pintér and Somlyódy (1987), Ermoliev (1988), Laporte (1988), Wallace (1988), Deininger and Lee (1989), Kaufman and Rousseeuw (1990), Galvão (1993), Ghost and Harche (1993). In a sense, the analysed system can be conceived as some ‘black box’ or ‘oracle’ that reacts in a complicated manner to decisions on the primary facility configuration setting. Naturally, there is no prior guarantee for unimodality of the overall performance indicator associated with such problems (since even its analytical form may be unknown). On the other hand, Lipschitz-continuity of the performance indicator—as depending on the basic design parameters—holds in many cases.

There are many reasons to combine expert assessments and opinions. To list a diversity of areas, where such combinations are relevant, one may think of the weather forecast at a particular location and time, the estimated yield of a natural resources exploration project, the reliability/risk of a new device or technology, the location of a new shopping centre or a waste disposal site, the real-time response of an expert system in a given situation, and so forth. As reflected by these examples, the words ‘expert’, ‘assessment’, and ‘opinion’ will be used here in the broadest possible sense. The aim of this chapter is to propose a unifying framework to analyse and solve problems of aggregating opinions in an objective, quantitatively established manner. The discussion draws on Pintér and Cooke (1987), providing model extensions, much improved solution methodology, and nontrivial numerical examples.

In this chapter we shall discuss a rather general global optimization problem originating from product design in mixing and processing industries. (The subsequent exposition draws on Hendrix and Pintér, 1991; Pintér, 1991c; and Chapter 2.5.)

The predominantly incomplete or poor understanding of environmental (as well as many other complex) systems calls for model development as an essential tool of the related scientific and applied research. For discussions—in the context of environmental management—see, for instance, Kneese and Bower (1968), Kneese, Ayres and d’Arge (1970), Brubaker (1973), Rich (1973), Park et al. (1974), United States Environmental Protection Agency (1974, 1980), Munn (1975), Parvin and Grammas (1976), Bower (1977), Russell and Spofford (1977), Rolling (1978), Nijkamp (1980), Loucks, Stedinger and Haith (1981), Haith (1982), Novotny and Chesters (1982), Jørgensen (1983), Orlob (1983), Beck (1985a, 1987a,b), Beck and van Straten (1986), Somlyódy and van Straten (1986), Kleindorfer and Kunreuther (1987), Pintér (1987a, 1990c,e, 1991a), Richardson (1988), Stokoe, Lane, Côté and Wright (1989).

We shall consider now important—from a practical point of view—specifications of the general calibration model stated by (4.5.1)–(4.5.4). The discretized model form will be studied, noting that the continuous case could be discussed analogously. (The exposition draws on Pintér and Van der Molen, 1991.)

The analysis of nutrient release from sediments in shallow eutrophic lakes is an important stage in properly describing such ecological systems. (On the subject of lake ecosystem modelling, consult, for instance, Park et al., 1974; Scavia, 1980; Orlob, 1983; Somlyódy and van Straten, 1986; Riley and Stefan, 1988; and also Chapters 4.6 and 4.11.) SED is a dynamic model that was developed (and tested on Lake Veluwe, Netherlands data) for describing the release of phosphorus from lake sediments (Van der Molen, 1991). The model includes three environmental state variables: dissolved phosphorus, organic particulate sediment phosphorus, and active sediment layer. It considers only the basic relationships between these variables. Specifically, processes of the diffusive transport of dissolved phosphorus to the overlying water body, mineralization of organic phosphorus in the sediment, and adsorption/desorption and fixation of inorganic phosphorus are modelled by SED. To describe this model, the following notation is introduced:

The opening of the Atlantic Ocean during the Triassic period also resulted in the formation of rift valleys along the eastern border of the North American continental plate. Subsequent infilling of these basins by terrestrial sediments has resulted in the formation of high yielding aquifers of excellent quality. To obtain model parameters that can be subsequently used to characterize these aquifers, the best approach would probably be an intensive drilling program. However, due to the immense size and thickness of the sediments, this cannot be considered a viable strategy; instead, one may turn to the application of a suitable groundwater model and a corresponding automatic calibration procedure.

Major industries typically have a substantial impact on environmental quality. Facing increasing public concern and more stringent environmental legislation, these industries have to find appropriate methods of waste management, while acting under the financial constraints of market realities.

The issue of establishing efficient regional water quality management strategies has been the subject of investigations for several decades: consult, for example, Deininger (1965, 1972, 1977), Howe (1971), Dorfman, Jacoby and Thomas (1972), Marks (1975), Bower (1977), Loucks, Stedinger and Haith (1981), Haith (1982), Beck (1985a, 1987a,b), Thomann and Mueller (1987), Loucks and da Costa (1991), Patry and Chapman (1991), Tebbutt (1992), Kularathna and Somlyódy (1994). In spite of the inherent uncertainties related to this problem, mostly deterministic system models have been analysed. Recognizing, however, the significance of partially unknown, uncertain, or statistically fluctuating processes in the environment, and making use of developments in modelling and numerical solution approaches, an increasing number of stochastic models have been introduced in recent years. Beck (1987a) provides a review of descriptive water quality studies, briefly referring also to the issue of decision making under uncertainty. Among the more recent studies in stochastic (river, lake, or subsurface) water quality modelling and management, one may refer, for example, to Brill, Eheart and Liebman (1979), Lohani and Thanh (1979), Padgett and Papadopoulos (1979), Beck and van Straten (1983), Burn and McBean (1985), Fujiwara, Gnanendran and Ohgaki (1986, 1987), Pintér and Somlyódy (1986), Somlyódy and van Straten (1986), Ellis (1987), Kutas and Herodek (1987),Massmann and Freeze (1987), Wagner and Gorelick (1987), Chen and Papadopoulos (1988), Eheart (1988), Somlyódy and Wets (1988), Tung and Hathhorn (1988), Gorelick (1990), De Lange and Pintér (1991a,b).

As already discussed in previous chapters, due to the worldwide danger of environmental degradation, water quality management has attracted increasing attention in the last decades. A large number of descriptive (simulation, assessment) and management (scenario analysis, optimization) models have been developed and applied to assist decision-making. The interrelated (sub)models frequently have very different temporal and/or spatial scaling and underlying information structure, so that their proper combination poses a significant challenge. Moreover, even recognizing the inherent stochasticity of the management problems studied—and analysing them in detail by descriptive submodels—most optimization models are formulated as deterministic: this transition requires a carefully balanced approach.

In this chapter a fairly general risk assessment and management approach is proposed for analysing and controlling accidental—as opposed to chronic, long-term—environmental pollution events. This concept is illustrated by a simplified case study, describing (hypothetical) point-source toxic pollution of a large European river (River Danube) and its estimated effect on the downstream bank-filtered well system. A numerical example indicates the viability of the suggested approach, and shows the potentials of applying advanced optimization techniques in risk management.