Finding effective points by surrogate models with overcomplete bases

We develop algorithms to find the so-called effective points (EPs) x∈X⊂Rnx∈X⊂Rn such that the corresponding responses f(x)∈Rf(x)∈R belong to a specific region of interest (ROI). Examples of an ROI include extreme values, bounded intervals, and positivity. We are especially interested in the problem defined by the following characteristics: (i) the definition of f(x)f(x) is either complicated or implicit, (ii) the response surface f(X)f(X) does not fit simple patterns, and (iii) computational costs of function evaluations is high. To solve this problem, we iteratively approximate the true yet unknown response surface with simplified surrogate models and then use the surrogate models to predict the possible EPs. Unlike interpolation schemes, the surrogate models are formed by linear combinations of a set of overcomplete bases and they are not obliged to fit the known response value. A numerical example that involves finding positive Lyapunov exponents of a dynamical system shows that the algorithm is efficient and practical.