An enhanced response surface methodology (RSM) algorithm using gradient deflection and second-order search strategies

Abstract

In the optimization of complex systems where at best one can only evaluate the function being optimized, often via a simulation experimental process, Response Surface Methodology (RSM) is frequently the method of choice. However, RSM invariably employs a first-order steepest descent method, presumably because of the prohibitive cost of employing second-order designs, except for the canonical analysis that is conducted at termination. In this paper, we suggest the use of deflected/conjugate gradient approaches that can be gainfully employed to improve the performance of RSM. These methods involve the same effort per iteration and require only first-order designs. However, instead of discarding previously generated information, the method utilizes these computations to advantageously build upon accumulated knowledge regarding the second-order curvature of the function being optimized, hence accelerating convergence by circumventing the characteristic zigzagging of steepest descent methods. The proposed scheme is illustrated using various test examples from the literature for which optimal solutions are known and that serve the purpose of exhibiting the potential of the recommended methodology.

This paper attempts to improve the search techniques being currently used in standard Response Surface Methodology (RSM) algorithms. RSM is a collection of mathematical and statistical techniques for experimental optimization. This work presents a novel RSM algorithm that incorporates certain gradient deflection methods, augmented with appropriate restarting criteria, as opposed to using the path of steepest descent as the only search direction. In order to investigate the use of the new RSM algorithm in comparison with the standard existing RSM techniques, a set of standard test functions is used, both with and without random perturbations. Computational results exhibit the improvements achieved under the proposed algorithm.

Introduction

The focus of this paper is on improving the simulation-optimization technique known as response surface methodology (RSM). First proposed by Box and Wilson[3] in the context of optimization problems concerned with chemical process engineering, RSM is a collection of mathematical and statistical techniques for experimental optimization. The search procedures currently employed by RSM algorithms use the method of steepest descent only. This paper develops a novel RSM algorithm that incorporates certain gradient deflection methods, augmented with suitable restarting criteria, as opposed to using the path of steepest descent as the only search direction. In order to empirically investigate the use of the new RSM algorithm in contrast with the existing one, a set of standard test functions from the literature is used. Computational results exhibit the improvements achieved under the proposed algorithm, both with and without random perturbations on functional evaluations.

This paper is organized as follows. The remainder of this section presents an overview of RSM along with a statement of a standard RSM algorithm, and discusses various competitive gradient deflection techniques that we will be using in our approach. Section 2develops the new RSM algorithm. Empirical studies are described in Section 3, and Section 4presents conclusions and recommendations for future research.

Throughout this paper, it is assumed that the problem at hand is an unconstrained minimization problem, and that the functional form of the objective function is unknown. Typically, to start the RSM procedure, an experiment is designed in a small sub-region of the factor space, and a low degree polynomial (usually first-order) is used to represent the data obtained from the responses. This helps the practitioner deduce which region should be explored next, by conducting a search along the estimated direction of steepest descent. If the goal is to minimize the response, this method aims at climbing down the response surface rather than exploring the whole region, and its success depends on the assumption that the ultimate minimum can be reached via such a path of descent (see p. 503 of Davies[4]). That is, as the search moves down the surface (decreasing response), it is assumed that at some point, a curvature will become evident, after which the response will no longer improve or will start increasing. At this point another experiment is designed to detect curvature and determine effects up to second-order. A canonical analysis is then performed to locate the stationary point of the fitted surface, and to ascertain whether any further exploration needs to be conducted. For example, if the stationary point is found to be a saddle point, then a ridge analysis is performed, whereby the experimenter formulates a k-variable response surface problem in two dimensions and collects observations along the falling ridge. If the stationary point is found to be a minimum, then the region around this point is explored a bit further via some discrete step sizes and the incumbent solution is reported.

If the experimenter has a prior notion of the general vicinity of the location of the optimum, then Myers[7] gives a stepwise procedure that can be generally described as follows (see p. 88 of Myers[7]).

Step 1: The experimenter fits a first-order response model in some restricted region of the variables x₁, x₂, …, x_k.

Step 2: The information from Step 1 is used to locate a path of steepest descent.

Step 3: A series of experiments is conducted along the path until no additional decrease in response is evident.

Step 4: Steps 1, 2, and 3 are repeated over the region about the current incumbent solution. However, if curvature is evident, and the experimenter is satisfied that little or no additional information can be obtained from the ongoing searches, a more elaborate experiment and analysis is conducted via the use of a second-order design.

In Step 1, typically, replications of a factorial or fractional factorial experiment are performed. The unknown parameters of the fitted linear model are then computed. A judicious selection of the experimental design having desirable properties such as minimum variance is needed in order to obtain better estimates of the unknown parameters. The first-order linear model is represented as

$$\text{y}{}_{\mathrm{ij}}\text{=β}{}_0\text{+}\text{∑}\text{l=1}\text{k}\text{β}{}_{\mathrm{l}}\text{x}{}_{\mathrm{l}}\text{+ε}{}_{\mathrm{ij}}$$

where y_ij is the response at the jth replication and the ith design point, x₁, x₂, …, x_k are the k factor variables, β_l, for l=1, …, k, are the unknown parameters of the linear model, and ε_ij is the error term at the ith design point and the jth replication (i=1, 2, …, m, j=1, 2, …, r, l=1, 2, …, k).

If a full 2^k factorial experiment is used at Step 1, then estimates of the unknown parameters β_l in Eq. (1)can be obtained. Denote these estimates by b_l (for l=1, 2, …, k), respectively. These estimates are then used in Step 2 to locate the path of steepest descent, which is given by the vector d=(−b₁, −b₂, …, −b_k). Responses are observed along this path using some prescribed search strategy until there is no improvement. In the standard approach, a simple sequence of fixed steps along the direction d are explored. If curvature is evident, then a second-order model is derived as,

$$\text{y}{}_{\mathrm{ij}}\text{=β}{}_0\text{+}\text{∑}\text{l=1}\text{k}\text{β}{}_{\mathrm{l}}\text{x}{}_{\mathrm{l}}\text{+}\text{∑}\text{h>l}\text{β}{}_{\mathrm{hl}}\text{x}{}_{\mathrm{h}}\text{x}{}_{\mathrm{l}}\text{+}\text{∑}\text{l=1}\text{k}\text{β}{}_{\mathrm{ll}}\text{x}{}^2{}_{\mathrm{l}}\text{+ε}{}_{\mathrm{ij}}\text{.}$$

Here, β_l, β_hl and β_ll are the unknown parameters of the second-order model (l=1, 2, … k, h>l), and the remaining terms are as defined for Eq. (1). This model is used to evaluate a stationary point of the response surface. A canonical analysis is performed that involves, among other things, locating the stationary point of the system, and determining the nature of this point. Using this analysis, an optimum is reported, perhaps following some additional investigation in the case of a detected ridge system.

The principal shortcomings of the foregoing standard RSM approach are two-fold. First, the initial (pure) gradient search can be prone to zigzagging and can be slow to converge (see[1]). Moreover, there is no information from previous iterations that is successively employed to provide improved search directions and the process is essentially memoryless. Second, after curvature is detected, there is no attempt to conduct a continuous iterative second-order search using the information available from the canonical analysis. Our intent in this paper is to rectify these shortcomings.

This sub-section discusses the gradient deflection methods to be used in the present study in order to address the first shortcoming of the standard RSM approach as cited above. Originally developed by Hestenes and Stiefel[6], conjugate gradient, or gradient deflection methods, were first applied to unconstrained minimization problems by Fletcher and Reeves[5]. In this approach, a sequence of points x_j+1, and a sequence of directions d_j, are generated iteratively as

$$\text{x}{}_{\mathrm{j+1}}\text{=x}{}_{\mathrm{j}}\text{+λ}{}_{\mathrm{j}}\text{d}{}_{\mathrm{j}}\text{,}$$

where

$$\text{d}{}_{\mathrm{j}}\text{=−g}{}_{\mathrm{j}}\text{+ψ}{}_{\mathrm{j}}\text{d}{}_{\mathrm{j-1}}$$

and where d₀=0, ψ_j is a multiplier that scales the direction vector of the previous iteration, being calculated differently for different gradient deflection methods, g_j is the gradient of the objective function at the operating point x_j (assumed to be nonzero, or else, the method is terminated), and λ_j is the step-length adopted along the (descent) direction, d_j. As seen from Eq. (4), a deflected direction d_j at the jth iteration is composed as a linear combination of the negative gradient at the jth iteration and the direction vector of the previous iteration. This implies a possible advantage of this method over the method of steepest descent, since the deflection strategy attempts to capture the second-order curvature effects over successive iterations. Indeed, for a quadratic function in k variables, this approach can be made to converge to an optimum within k iterations (see[1]).

Various gradient deflection methods use different techniques for computing the deflection parameters ψ_j at the jth iteration. In particular, one gradient deflection method proposed by Sherali and Ulular[9] that was found to be promising even for nondifferentiable functions (wherein g_j represents a subgradient of the function) uses the average direction strategy and is denoted here as GD1. The deflected direction at the jth iteration for this method is given by

$$\text{d}{}_{\mathrm{j}}\text{=−g}{}_{\mathrm{j}}\text{+}\text{‖g}{}_{\mathrm{j}}\text{‖}\text{‖d}{}_{\mathrm{j-1}}\text{‖}\text{d}{}_{\mathrm{j-1}}\text{,}$$

where d_j−1 is the search direction adopted at the (j−1)st iteration, with d₁≡−g₁.

In the context of proposing a conjugate gradient algorithm that adopts quasi-Newton types of updates and permits inexact line searches, Sherali and Ulular[10] develop yet another scheme for computing ψ_j. Their method, denoted in this paper by GD2, generates the deflected direction at the jth iteration as

$$\text{d}{}_{\mathrm{j}}\text{=−g}{}_{\mathrm{j}}\text{+}\text{q}{}_{\mathrm{j}}\text{′g}{}_{\mathrm{j}}\text{−(1/s}{}_{\mathrm{j}}\text{)p}{}_{\mathrm{j}}\text{′g}{}_{\mathrm{j}}\text{q}{}_{\mathrm{j}}\text{′d}{}_{\mathrm{j-1}}\text{d}{}_{\mathrm{j-1}}\text{,}$$

where

$$\text{p}{}_{\mathrm{j}}\text{=x}{}_{\mathrm{j}}\text{−x}{}_{\mathrm{j-1}}\text{,}$$

$$\text{q}{}_{\mathrm{j}}\text{=g}{}_{\mathrm{j}}\text{−g}{}_{\mathrm{j-1}}\text{,}$$

and where s_j is a scale parameter that, if suitably chosen, permits s_jd_j to be the Newton direction at the jth iteration, given that this direction is spanned by −g_j and d_j−1. From a computational viewpoint, the parameter s_j is prescribed as

$$\text{s}{}_{\mathrm{j}}\text{=λ}{}_{\mathrm{j-1}}\text{.}$$

Motivated by the computational success of BFGS quasi-Newton updates, Shanno proposed a related conjugate gradient strategy for which the direction at the jth (j=2, 3, …) iteration is given by

$$\text{d}{}_{\mathrm{j}}\text{=−}\text{I−}\text{p}{}_{\mathrm{j}}\text{q}{}_{\mathrm{j}}\text{′+q}{}_{\mathrm{j}}\text{p}{}_{\mathrm{j}}\text{′}\text{q}{}_{\mathrm{j}}\text{′p}{}_{\mathrm{j}}\text{g}{}_{\mathrm{j}}\text{,}$$

where p_j and q_j are as defined in , , respectively. We denote this gradient deflection method by GD3. Finally, a fourth gradient deflection method explored in this study, denoted by GD4, is a modification of GD2 suggested by Sherali and Ulular[10] that converts this strategy into a symmetric memoryless BFGS type of an update. The prescribed search direction under this modification is given by

$$\text{d}{}_{\mathrm{j}}\text{=−}\text{I−}\text{p}{}_{\mathrm{j}}\text{q}{}_{\mathrm{j}}\text{′+q}{}_{\mathrm{j}}\text{p}{}_{\mathrm{j}}\text{′}\text{q}{}_{\mathrm{j}}\text{′p}{}_{\mathrm{j}}\text{+}\text{1}\text{s}{}_{\mathrm{j}}\text{+}\text{q}{}_{\mathrm{j}}\text{′q}{}_{\mathrm{j}}\text{q}{}_{\mathrm{j}}\text{′p}{}_{\mathrm{j}}\text{p}{}_{\mathrm{j}}\text{p}{}_{\mathrm{j}}\text{′}\text{q}{}_{\mathrm{j}}\text{′p}{}_{\mathrm{j}}\text{g}{}_{\mathrm{j}}$$

where p_j, q_j, and s_j are as defined in , , , respectively. The four gradient deflection methods described above will be used in our empirical study. In addition, as suggested in the literature, restarting techniques employed in conjunction with gradient deflection methods can significantly enhance the performance of these methods. We next specify the particular restarting procedures employed in this study.

Beale[2] and Powell[8] have offered various restarting criteria that improve the performance of gradient deflection methods. In the present context of RSM, restarting at any iteration would imply following the path of steepest descent at that iteration, although as suggested by Powell[8] in the context of conjugate gradient methods, one could restart using the current deflected direction in order to preserve the accumulated second-order information. However, this would require an additional term in the deflection scheme. In this study, two restarting criteria, denoted by RSA and RSB, will be examined under the above four gradient deflection methods.

Under criterion RSA, for a k-variable problem, the optimization procedure is restarted at the jth iteration, by using d_j=−g_j, if any of the following three conditions is satisfied:

• if j=k, or

• if ‖g_j′g_j+1‖≥0.2‖g_j‖² holds, or

• if −1.2‖g_j‖²≤d_jproj′g_j≤−0.8(g_j′g_jproj) is violated,

where d_jproj and g_jproj respectively project d_j and −g_j onto the box (boundary) constraints by zeroing out the components corresponding to the active bounds that would be immediately violated if one were to start moving along the respective directions d_j and −g_j. The rationale for these conditions is provided in Section 4 of Powell[8], or on p. 336 in Bazaraa et al.[1].

Under criterion RSB, for a k-variable problem, the optimization procedure is restarted at the jth iteration if any of the following two conditions is satisfied:

• if j=k, or

• if d_jproj′g_j>−0.8(g_j′g_jproj) holds.

Notice that the conditions in RSB are a subset of the conditions in RSA, and that in particular, since restarting is triggered whenever d_jproj′g_j>−0.8(g_j′g_jproj), the adopted direction d_jproj is always a descent direction having a sufficiently negative directional derivative. These restarting criteria are empirically tested in Section 3. The next section embeds the foregoing deflection schemes within the framework of an enhanced RSM algorithm that, in addition, adopts second-order search directions whenever a significant curvature is evident.