Grid Search in MATLAB
Andrii Parkhomenko
Universitat Autònoma de Barcelona and Barcelona GSE
Spring 2017
Andrii Parkhomenko (UAB & Barcelona GSE) Grid Search in MATLAB 0 / 14
Grid Search
Problem:
max f (x)
x∈Rn
Approach. Build a grid: a finite set of points in the domain of f :
G = {(x11 , ..., xn1 ), ..., (x1m1 , ..., xnmn )}
where mi is the number of gridpoints in the dimension i
Andrii Parkhomenko (UAB & Barcelona GSE) Grid Search in MATLAB 1 / 14
Grid Search
Example 1
Problem:
max f (x) = x1 − 0.2x12 + x2 − 0.3x22
x∈R2
Construct an equally-spaced grid:
G = {(x1 , x2 )|x1 ∈ {0, 1, ..., 5}, x2 ∈ {0, 1, ..., 5}}
Andrii Parkhomenko (UAB & Barcelona GSE) Grid Search in MATLAB 2 / 14
Grid Search
In MATLAB:
Andrii Parkhomenko (UAB & Barcelona GSE) Grid Search in MATLAB 3 / 14
Grid Search
Grid is too coarse:
Algorithm finds x = (3, 2)
True maximum: x = (2.5, 1.667)
Solutions:
Finer grid
Non-equally spaced grid
Andrii Parkhomenko (UAB & Barcelona GSE) Grid Search in MATLAB 4 / 14
Grid Search
Construct non-equally spaced grid:
G = {(h(x1 ), h(x2 ))|x1 ∈ {0, 1, ..., 5}, x2 ∈ {0, 1, ..., 5}}
where h(xi ) = ln(3xi + 1)
Andrii Parkhomenko (UAB & Barcelona GSE) Grid Search in MATLAB 5 / 14
Grid Search
In MATLAB:
Andrii Parkhomenko (UAB & Barcelona GSE) Grid Search in MATLAB 6 / 14
Grid Search
This is a better grid for our purposes:
Solution algorithm finds x = (2.565, 1.996)
True maximum: x = (2.5, 1.667)
Non-equally spaced grids are also useful when you don’t know the
neighborhood in which to look for maximizer x
Andrii Parkhomenko (UAB & Barcelona GSE) Grid Search in MATLAB 7 / 14
Grid Search
“Curse of Dimensionality”
Typically we search on x ∈ Rn
When n is even moderately large, grid search requires too many
iterations:
I if n = 5, mi = 100 for i = 1, ..., 5, then we have to perform
1005 = 10, 000, 000, 000 iterations!
Solutions
Adaptive (refined) grid search
Don’t use grid search (see notes from previous class)
Andrii Parkhomenko (UAB & Barcelona GSE) Grid Search in MATLAB 8 / 14
Adaptive Grid Search
Idea:
Start with a coarse grid
Refine as you approach to the solution
Andrii Parkhomenko (UAB & Barcelona GSE) Grid Search in MATLAB 9 / 14
Adaptive Grid Search
Example 2
Problem:
max f (x) = x1 − 0.2x12 + x2 − 0.3x22
x∈R2+
1 Start with:
G 0 = {(x1 , x2 )|x1 ∈ {0, 1, ..., 5}, x2 ∈ {0, 1, ..., 5}}
2 Obtain interim solution: x = (3, 2)
3 Refine the grid around the interim solution by halving the length of
the search interval:
G 1 = (x1 , x2 )|x1 ∈ {1.75, 2.25, 2.75, 3.25, 3.75, 4.25},
x2 ∈ {0.75, 1.25, 1.75, 2.25, 2.75, 3.25}
4 Repeat steps 2-3 until convergence
Andrii Parkhomenko (UAB & Barcelona GSE) Grid Search in MATLAB 10 / 14
Adaptive Grid Search
In MATLAB:
Andrii Parkhomenko (UAB & Barcelona GSE) Grid Search in MATLAB 11 / 14
Adaptive Grid Search
After 4 refinements:
Solution algorithm finds x = (2.531, 1.656)
True maximum: x = (2.5, 1.667)
This level of precision requires about 37,000 iterations with simple grid
search, but only 144 with adaptive grid search!
Andrii Parkhomenko (UAB & Barcelona GSE) Grid Search in MATLAB 12 / 14
Adaptive Grid Search
Adaptive grid search faces the same problems as most other numerical
optimization methods when
objective function is not concave, discontinuous or non-differentiable
local optima exist
(see notes from previous class)
Andrii Parkhomenko (UAB & Barcelona GSE) Grid Search in MATLAB 13 / 14
Adaptive Grid Search
Further reading
Carroll, Christopher D. “The Method of Endogenous Gridpoints for
Solving Dynamic Stochastic Optimization Problems” (2006) Economics
Letters 91(3), 312-320
Fella, Giulio. “A Generalized Endogenous Grid Method for Non-Smooth
and Non-Concave Problems” (2014) Review of Economic Dynamics 17,
329-344
Andrii Parkhomenko (UAB & Barcelona GSE) Grid Search in MATLAB 14 / 14
