DDRSM - Fast and Scalable Method of Gradients Estimation

Dynamically Dimensioned Response Surface Method (DDRSM) is a new method to estimate gradients, which is equally efficient for low-dimensional and high-dimensional tasks. DDRSM is a key element in four eArtius optimization algorithms. It requires just 5-7 model evaluations to estimate gradients regardless of task dimension.

DDRSM: How it Works DDRSM (a) generates 5-7 sample points on each optimization step in the current sub-region, and (b) uses the points to recognize the most significant design variables for each objective function. Then (c) DDRSM builds local approximations for all objectives, and (d) estimates gradients analytically based on the approximations.

The estimated gradient has non-zero projections that correspond to the most significant variables, and zero projections for the low significance variables. Ignoring non-significant variables slightly reduces the accuracy, but allows estimating gradients by the price of 5-7 evaluations for tasks of practically any dimension.

DDRSM recognizes significant variables repeatedly on each optimization step every time gradients need to be estimated. This is important because the topology of objective functions and constraints can diverge in different parts of the design space throughout the optimization process.

The same design variable can be crucially important for one of the objective functions in the current sub-region, and not significant for other objective functions. Later, in a different sub-region, the local topology of an objective function can be changed, and DDRSM will create another list of significant design variables corresponded to the objective's topology in current sub-region. Thus, dynamic use of DDRSM on each optimization step makes it more adaptive to objective functions' topology changes, and allows for an increase in the accuracy of gradients estimation.

eArtius DDRSM vs. Traditional RSM The following table shows the most important aspects of Response Surface Methods (RSM), and compares traditional RSM with eArtius DDRSM.

Comparison of traditional response surface methods with DDRSM approach

RSM Aspects	Traditional RSM	eArtius DDRSM
Purpose	Optimize fast surrogate functions instead of computationally expensive simulation models	Quick gradients estimation for direct optimization of computationally expensive simulation models
Approximation type	Global approximation	Local approximation
Domain	Entire design space	A small sub region
Use of surrogate functions	Optimization in entire design space	Gradient estimation at a single point
Accuracy requirements	High	Low
The number of sample points to build approximations	Exponentially grows with increasing the task dimension	5-7 sample points regardless of task dimension
Time required to build an approximation	Minutes and hours	Milliseconds
Task dimension limitations	30-50 design variables	Up to 5,000 design variables
Sensitivity analysis	Required to reduce task dimension	Not required

As follows from the above table, the most common use of response surface methods is creating global approximations based on DOE sample points, and further optimization of such surrogate models. This approach requires maintaining a high level accuracy of the approximating surrogate function over the entire design space, which in turn requires a large number of sample points.

In contrast, DDRSM method builds local approximations in a small sub region around a given point, and uses them for gradients estimation at the point. This reduces requirements to the accuracy of approximating models because DDRSM does not have to maintain a high level accuracy over the entire design space.

The following benchmark problem ZDT1 is intended to demonstrate (a) high efficiency of the DDRSM approach to estimate gradients compared with the finite difference method, and (b) the ability of DDRSM to recognize significant design variables.

ZDT1 has 30 design variables, two objectives, and the Pareto frontier is convex. The global Pareto-optimal front corresponds to . The optimization task formulation used is as follows:

The following diagrams show Pareto optimal solution found by MGP optimization algorithm based on two different methods of gradient estimation: FDM and DDRSM. In both cases MGP algorithm started from the same initial point (see diagrams), and performed 17 steps along Pareto frontier until it hit the end of the Pareto frontier.

The finite difference method (FDM) spent 31 model evaluations to estimate gradients on each step: 31*17=527, and found 17 Pareto optimal points. Red points on the right diagram are evaluated to estimate gradient by FDM approach.
DDRSM method spent about two model evaluations on each step, and found 17 Pareto optimal points out of 38 model evaluations. DDRSM has generated a number of points randomly (see red markers on left and right diagrams.) The points have been used to build local approximations for estimating gradients.

Clearly, both methods FDM and DDRSM of gradient estimation allowed MGP to precisely determine the direction of improvement of the preferable objective F1 on each step, and the direction of simultaneous improvement for both objectives. As a result, MGP algorithm was able to step along the global Pareto frontier on each optimization step. All Pareto optimal points match the conditions , and this means that the optimal solutions are exact in both cases. However, DDRSM has spent 527/38=13.8 less model evaluations to find the same 17 Pareto optimal points.

Benefits of New DDRSM-based optimization technology developed at eArtius:

• Removes any task dimension limitations, and allows optimizing models with up to 5,000 design variables
• Eliminates necessity in use of DOE and global RSM
• Eliminates necessity in use of sensitivity analysis
• Can be applied for direct optimization of high-dimensional computationally expensive simulation models

All eArtius optimization algorithms are based on DDRSM, and available as plug-ins for eArtius Pareto Explorer, Noesis OPTIMUS, ESTECO modeFrontier, and Simulia iSight design optimization environments.