Approximation model management for optimization
J. Dennis, Virginia J. Torczon · 6th Symposium on Multidisciplinary Analysis and Optimization · 1996
A standard engineering practice is the use of approximation models in place of expensive simulations to drive an optimal design process based on nonlinear programming algorithms. The use of approximation techniques is intended to reduce the number of detailed, costly analyses required during optimization while maintaining the salient features of the design problem. The question we address is how to manage the interplay between the optimization and the fidelity of the approximation models to ensure that the process converges to a solution of the original design problem. Using well-established notions from the literature on trust-region methods and a powerful global convergence theory for pattern search methods, we can ensure that the optimization process converges to a solution of the original design problem. Introduction The desire is to find x* to minimize f ( x , y ( x ) ) , where x represents the control variables, y(x) represents the state variables, and / is the design objective. We assume that the control variables x are subject to some constraints. In addition, we assume: • y(x] is never available, but computational procedures are available to compute or estimate some •Professor, Member AIAA. t Assistant Professor. Copyright ©1996 by the American Institute of Aeronautics and Astronautics, Inc. All rights reserved. • models M(x) « M f ( x ) can be built with increasing accuracy at additional computational cost. The task is to minimize f ( x , M * ( x ) ) by approximately optimizing appropriately chosen f(x, Model Management Suppose we want to solve the following general minimization problem: min(f>(z), subject to z £ B, where B denotes the feasible region for the optimization problem. Then given a putative solution Zf, « z* we can follow the general strategy: • If convergence, then exit; otherwise, continue. • Build a global model G of on B. • Build a local model m of G at Zk. • From m obtain a z£' that improves G. » If z£+' improves , then Zk+i = z%+ otherwise, either backtrack on the amount of optimization applied to G to obtain a more conservative choice of z£t, or refine the global model G and repeat the process. This simple strategy leads the the following framework for using approximation models in optimization. 1044 Proposed Optimization Framework Using Approximation Models Given M, M*, XQ « x*, J/Q = M*(XQ): For k = 0 , 1 , , 1. If convergence, then exit; otherwise, continue. 2. Apply an optimization algorithm to the approximate problem to find an xk+ for which f(x/:+!yk+) satisfies an appropriate decrease condition for f(x,M°'(x)) from xk. (This could mean something like do a complete optimization for the problem defined by f(x, M*(x)y or take some (fixed) number of optimization iteration on the problem defined by f ( x , M(x)). Compute predk = f(xk , y*k) f(xk+,y%+). This is the amount of reduction that the approximate problem defined by f(x,M(x)) predicts if the trial solution xk+ is applied to the true problem f ( x , M * ( x ) ) . 3. Compute j / j j , = M*(xk^.) using either a detailed analysis or adaptive heuristics. Computer aredk f(xk, yk)-f(xk+, y%+). This is the amount of reduction realized by the trial step xk+ when applied to the actual problem Allow the same optimization on the approximate problem at the next iteration. 4. If aredk < 0, then (improvement was predicted but not achieved) Set xk+i xk and y*k+l = yk. (Reject the step.) Get a more faithful model M anchored at xk. (Refine the model.) Allow less optimization on the approximate problem at the next iteration. Else, if 0 < jjJ^fjL < iQ-, then (much more improvement was predicted than achieved) Set Kt+i = z*+ and yk+i = yk+. (Accept the step.) Update the current M to interpolate to yk+i. Allow less optimization on the approximate problem at the next iteration. Else, if 10~ < -2 - < 0.5, then (the prediction pretty — * was satisfactory) Set xk+1 xk+ and y*k+l y*k+. (Accept the step.) Update the current M to interpolate to Else, 0.5 < (the prediction was excellent, or more decrease was obtained than predicted) = y*k+. Set xk+1 = xk+ and (Accept the step.) Update the current M to interpolate to yk+\. Consider using a less accurate approximation model. Allow more optimization on the approximate problem at the next iteration. 5. Return to Step 1. To finish the specification for the general algorithm we must determine: • how to find a trial step xk+, • what constitutes an appropriate decrease condition for f ( x , M(x)) from xk, • how to update the amount of optimization to be done on the approximate problem in Step 2, and • how to incorporate adaptive heuristics to estimate y*k+. We use well-established notions from the literature on trust-region methods and a powerful global convergence theory for pattern search methods to manage this interplay between optimization and the fidelity of the approximation models. A careful use of these techniques ensures that the process converges under the mild condition that at any given point at which a full simulation has been run, the approximation model agrees with the objective function of the optimization problem. Computational testing is underway and will be the subject of future reports. Acknowledgments This work was supported by the Air Force Office of Scientific Research under grant F49620-95-1-0210.