A quasi-Newton trust-region method for optimization under uncertainty using stochastic simplex approximate gradients

Abstract

The goal of field-development optimization is maximizing the expected value of an objective function, e.g., net present value for a producing oil field or amount of CO$_2$ stored in a subsurface formation, over an ensemble of models that describe the uncertainty range. A single evaluation of the objective function requires solving a system of partial differential equations, which can be computationally costly. Hence, it is most desirable for an optimization algorithm to reduce the number of objective-function evaluations while delivering high convergence rate. Here, we develop a quasi-Newton method that builds on approximate evaluations of objective-function gradients and takes more effective iterative steps using a trust-region approach compared to line search. We implement three gradient formulations: ensemble optimization (EnOpt) gradient, and two variants of the stochastic simplex approximate gradient (StoSAG), all computed using perturbations around the point of interest. We modify the formulations to enable exploiting the objective-function structure. Instead of returning a single value for the gradient, the reformulation breaks up the objective function into its sub-components and returns a set of sub-gradients. We then can utilize our prior problem-specific knowledge through passing a ‘weight’ matrix to act on the sub-gradients. Two quasi-Newton updating algorithms are implemented: Broyden-Fletcher-Goldfarb-Shanno and the symmetric rank 1. We first evaluate the variants of our method on test challenging functions (e.g., stochastic variants of Rosenbrock and Chebyquad). Then, we present an application to a well-control optimization problem for a realistic synthetic problem. Our results confirm that StoSAG gradients are significantly more effective than EnOpt gradients for accelerating convergence. An important challenge to stochastic gradients is determining a priori the adequate number of perturbations. We report that the optimal number of perturbations depends on both the number of decision variables and the size of uncertainty ensemble and provide practical guidelines for its selection. We show on the test functions that imposing our prior knowledge on the problem structure can improve the gradient quality and significantly accelerate convergence. In many instances, the quasi-Newton algorithms deliver superior performance compared to the steepest-descent algorithm, especially during the early iterations. Given the computational cost involved in typical applications, rapid and noteworthy improvements at early iterations is greatly desirable for accelerated project delivery. Furthermore, our method is robust, exploits parallel processing, and can be readily applied in a generic fashion for a variety of problems where the true gradient is difficult to compute or simply not available.

Appendix

Fig. 22

Comparison of gradient-based methods on the stochastic Rosenbrock function with $N=1000$

Fig. 23

Comparison of gradient-based methods on the stochastic Chebyquad function with $\sigma =10^{-1}$

Fig. 24

Comparison of gradient-based methods on the stochastic Chebyquad function with $\sigma =1$

Fig. 25

Progression of the analyzed methods from the initial point (black circle) to their final convergence points

Fig. 26

Chebyquad function with $\sigma =10^{-3}$. Progression of the analyzed methods from the initial point (black circle) to their final convergence points

Fig. 27

Chebyquad function with $\sigma =1$. Progression of the analyzed methods from the initial point (black circle) to their final convergence points

In this section, some supplementary plots are presented to support the ideas developed in the main body of the manuscript. First, we discuss the effect of increasing the dimension of the optimization-parameter vector. As can be seen in Figs. 21 and 22, when N is large, the stochastic gradients (StoSAG and EnOpt) are more efficient than the FD gradient. However, for small scale problems, the FD gradient is more efficient. The results for the stochastic Chebyquad function are plotted for a varying range of $\sigma$ are plotted in Figs. 23-24. When the variance is large, The performance of the EnOpt gradient is comparable to that of the StoSAG gradients. However, when the variance is small, the EnOpt gradient leads to poor results.

The progress of the iterations can be visualized for the 2-dimensional Rosenbrock problem in Fig. 25. In this plot, each arrow represents the step taken between iteration, while the color of the arrow designates the method, and is the same as in the previous figures. Unlike the SD, the Newton method exhibits quadratic convergence and takes much less iterations to converge. The Newton direction learns about the curvature of the surface of F resulting in smooth downhill navigation, as opposed to the zigzagging movement in case of SD. The BFGS exhibits behavior that is intermediate between the SD and Newton. In Figs. 26 and  27, the response surface of the Chebyquad function is plotted in contours for different uncertainty distributions. It is clear from the figures that the EnOpt gradient becomes less accurate as the variance increases.