TL;DR
This paper introduces a new optimization algorithm, p-sep lmm-CMA, that significantly speeds up the search for optimal solutions in partially separable functions. By building specialized "meta-models" for each sub-component of these functions, the algorithm achieves substantial performance gains over standard methods, particularly for complex, high-dimensional problems.
What Problem Does This Paper Address?
Optimizing complex, real-world problems often involves expensive objective functions, where each evaluation can take minutes or even hours (e.g., fluid flow simulations in oil and gas fields). To tackle this, researchers often use "meta-models" or surrogate functions to approximate the objective function, reducing the number of costly evaluations. The Covariance Matrix Adaptation Evolution Strategy (CMA-ES) is a powerful, derivative-free optimization algorithm. However, standard CMA-ES can be slow on certain problem structures. This paper focuses on a specific class of functions called "partially separable functions," which can be decomposed into sums of simpler sub-functions. The challenge is to effectively exploit this structure within CMA-ES to accelerate optimization without sacrificing too much generality.
Methods
The core innovation is the p-sep lmm-CMA algorithm, which builds upon the local meta-model CMA-ES (lmm-CMA). Here's how it works:
- Partially Separable Functions: The paper defines these as functions that can be expressed as a sum of "element functions," each depending on a subset of the original variables. For example, a function of 10 variables might be a sum of two functions, one depending on variables 1-5 and another on variables 6-10.
- Meta-Models for Sub-Functions: Instead of building a single meta-model for the entire complex function, p-sep lmm-CMA constructs individual meta-models for each element function. This is the key novelty.
- Local Quadratic Models: Each element function's meta-model is a locally quadratic approximation, built using a technique called locally weighted regression. This involves selecting nearby data points from the optimization history and fitting a quadratic surface to them.
- Leveraging Element Function Values: Crucially, the authors assume that when evaluating the overall function, one can also obtain the values of its individual element functions. This is a realistic assumption in many practical scenarios (e.g., calculating the profit from each individual well in a field).
- Integration with CMA-ES: The meta-models are used within the CMA-ES framework to approximate the ranking of candidate solutions. This allows CMA-ES to update its search distribution (mean, covariance matrix, and step-size) without needing to evaluate the expensive true objective function for every candidate.
Datasets
The paper evaluates its proposed method on several standard test functions, specifically chosen for their partially separable nature:
- Rosenbrock function (fRosen)
- Rosenbrock function with a twist (f100Rosen)
- Rosenbrock function with a large number of variables (f10000Rosen)
- Block-rotated ellipsoid function (fBlockElli-2D, fBlock Elli)
These functions are modeled using different numbers of element functions (N) and different numbers of variables per element function (nм), as detailed in Table 2. No new benchmark datasets were introduced.
Key Insights and Ideas
- Structure is Key: Exploiting the inherent structure of a problem (like partial separability) is a powerful way to accelerate optimization, even if it means breaking some of the theoretical invariances of the original algorithm.
- Divide and Conquer for Meta-Models: Building separate, specialized meta-models for each sub-component of a partially separable function is more effective than a single, global meta-model. This allows the algorithm to better capture the local behavior of each part.
- Access to Sub-function Values is Crucial: The assumption that element function values are available significantly enhances the effectiveness of the proposed approach.
- Dimensionality Reduction for Meta-Modeling: For a problem of dimension n, building N meta-models of dimension nм (where nм < n) effectively reduces the complexity of meta-model construction. This is a major reason for the observed speedups in high-dimensional problems.
- Population Size Matters: Increasing the population size can further improve performance, though there's a point of diminishing returns.
Key Results
- Significant Speedups: p-sep lmm-CMA achieved speedups ranging from 4.5 to 15 times compared to standard CMA-ES on the tested functions.
- Theoretical Maximum Achieved: For certain configurations of the Rosenbrock function (e.g., n=40 for fRosen, n=20 for f100Rosen), the algorithm reached a speedup close to the theoretical maximum allowed by the approach (λ/nм).
- Impact of Dimension: The speedup generally increases with the dimension of the problem, especially when the number of element variables (nм) is kept small.
- Population Size Optimization: Increasing the population size by a factor of 4 (γ=4) led to a 1.5 to 2 times reduction in the number of evaluations needed to reach a target value on the Rosenbrock function.
Limitations and Future Work
- Computational Cost: While the number of objective function evaluations is reduced, the internal computational cost of building meta-models increases. This is dominated by finding nearest neighbors and solving quadratic models.
- Bandwidth Selection: The paper investigates the optimal bandwidth for meta-models, finding that a factor of 2 times the minimum required points (β=2) is often a good choice, but not universally optimal.
- Future Work: The authors suggest further investigation into the optimal population size, especially its dependence on problem dimension and sub-problem dimensions. They also note that while their adaptive encoding approach is believed to be more numerically robust, it was not tested in this work.
Summary updated