Solver: Stochastic Trust-Region Response-Surface Method (STRONG)¶
Description:¶
The solver estimates the shape of the underlying response distribution, through function evaluations taken within a neighborhood of the incumbent solution. STRONG has two stages in each iteration where a sub trust region is defined: stage I optimizes a first-order polynomial, and stage II optimizes a second-order polynomial. If stage II fails to generate a good solution, an inner loop is initiated where value, gradient, and Hessian of the center point are further calculated.
Modifications & Implementation:¶
Process within a stage: We first find the Cauchy Point and the new solution in order to create a polynomial. Then, the solver either shrinks trust region size, or moves the center point while the trust region size stays constant, or moves the center point while the trust region enlarges.
Helper functions: There are 3 helper functions in addition to the main algorithm.
cauchy_point finds the Cauchy Point by using the gradient and Hessian matrix to find the steepest descent direction.
check_cons checks the feasibility of the Cauchy point and updates the point accordingly.
finite_diff uses finite difference to estimate gradients and BFGS to estimate the Hessian matrix.
Scope:¶
objective_type: single
constraint_type: box
variable_type: continuous
Solver Factors:¶
crn_across_solns: Use CRN across solutions?
Default: True
n0: Initial sample size
Default: 10
n_r: Number of replications taken at each solution
Default: 10
sensitivity: shrinking scale for VarBds
Default: 10**(-7)
delta_threshold: maximum value of the radius
Default: 1.2
delta_T: initial size of trust region
Default: 2
eta_0: the constant of accepting
Default: 0.01
eta_1: the constant of more confident accepting
Default: 0.3
gamma_1: the constant of shrinking the trust regionthe new solution
Default: 0.9
gamma_2: the constant of expanding the trust region
Default: 1.11
lambda: multiplicative factor for n_r within finite difference
Default: 2
lambda_2: magnifying factor for n_r in stage I and stage II
Default: 1.01
References:¶
This solver is adapted from the article Kuo-Hao Chang, L. Jeff Hong, Hong Wan, (2013). Stochastic Trust-Region Response-Surface Method (STRONG) - A New Response-Surface Framework for Simulation Optimization. INFORMS Journal on Computing, 25(2):230-243. (https://doi.org/10.1287/ijoc.1120.0498)