Benchmarking the Hooke-Jeeves Method,
MTS-LS1, and BSrr on the Large-scale BBOB
Function Set
The BBOB-2022 workshop at Boston

Ryoji Tanabe
Yokohama National University
Yokohama, Japan

Introduction

Hooke-Jeeves

MTS-LS1

BSrr

Tips

Setting

Results

Conclusion

Separability in black-box numerical optimization
A D-dim. separable function f can be D 1-dim. functions
arg min f (x) = (arg min f (x1 , ..., ), ..., arg min f (. . . , xD ))x1xDx

 Separable functions are easier to solve than nonseparable ones
 If an optimizer can exploit the separability
 E.g., Coordinate-wise optimizers

IMHO, a separable real-world problem is very rare
 Some decision variables are likely to depend on each other The motivation to study optimizers for separable functions is weak Just in case , it is better for an algorithm portfolio to contain an
optimizer that can exploit the separability
 An efficient algorithm selection system is available [Tanabe 22] ,Ryoji Tanabe: Benchmarking Feature-based Algorithm Selection Systems for Black-box Numerical Optimization. IEEE Trans. Evol. Comput.
in press (2022)2 / 17

Introduction

Hooke-Jeeves

MTS-LS1

BSrrTips

SettingResults

Conclusion

Benchmarking three optimizers for separable functions on bbob-largescale
1. The Hooke-Jeeves method (HJ) [Hooke 61]
 One of the most classical black-box optimizers
2. Multiple trajectory search local search 1 (MTS-LS1) [Tseng 08]
 Designed for the CEC LSGO competition 2008
 Some winners of the CEC (LSGO) competitions used MTS-LS1
 Very similar to the Hooke-Jeeves method, but it has been overlooked

3. Brent-STEP in a round-robin manner (BSrr) [Baudis 15]
 State-of-the-art for the five separable bbob functions (f1 , . . . , f5 )
 BSrr is a member of a portfolio in recent algorithm selection systems

Robert Hooke, T. A. Jeeves: “Direct Search” Solution of Numerical and Statistical Problems. J. ACM 8(2): 212-229 (1961)
Lin-Yu Tseng, Chun Chen: Multiple trajectory search for Large Scale Global Optimization. IEEE Congress on Evolutionary Computation
2008: 3052-3059
Petr Baudis, Petr Posı́k: Global Line Search Algorithm Hybridized with Quadratic Interpolation and Its Extension to Separable Functions.
GECCO 2015: 257-264

3 / 17

Introduction

Hooke-Jeeves

MTS-LS1

BSrrTips

Setting

Results

Conclusion

The Hooke-Jeeves method: a pattern move (variable-wise operation)
 HJ iteratively improves a search point x ∈ RD by two moves:
1. a pattern move (variable-wise operation)
2. an exploratory move (vector-wise operation)

 In the pattern move, HJ generates a new point xnew by perturbing
only one variable xi ∈ x (from i = 1 to D)
lowlownew xnew
← xi + σ(xup← xi − σ(xupii − xi ) or xii − xi ) σ: step-size (the initial σ init = 0.4)
and xlow xupi : the upper and lower bounds for the i-th variable
iFirst, add a positive
perturbation to xi
0.3
2.7
1.8

If not improved, add a negative
perturbation to xi
5.3

Add 5

2.7-5.3

Add -5

1.8

2.7
1.8

 When all trials for all variables were unsuccessful, σ ← c × σ c: learning rate (typically, c = 0.5?)

4 / 17

Introduction

Hooke-Jeeves

MTS-LS1

BSrr

Tips

Setting

Results

Conclusion

The Hooke-Jeeves method: an exploratory move (vector-wise operation)
 If the pattern move was successful for at least one variable, HJ
performs a bonus operation
 HJ generates a new point xnew by taking the difference from theprevious one xprev to the current one x xnew ← x + (x − xprev )5 / 17

Introduction

Hooke-Jeeves

MTS-LS1

BSrr

Tips

SettingResultsConclusion

The overall procedure of the Hooke-Jeeves method
Initialize x, σ ← σ init ;2 while not happy do
3xprev ← x;

1456789101112131415
16
17/* The pattern move (variable-wise operation)for i ∈ {1, . . . , D} doxnew ← x;*/

lowxnew← xi + σ(xupii − xi );newif f (x) < f (x) then x ← xnew ;elsexnew ← x;
lowxnew← xi − σ(xupii − xi );if f (xnew ) < f (x) then x ← xnew ;/* The exploratory move (vector-wise operation)
if f (x) < f (xprev ) thenxnew ← x + (x − xprev );if f (xnew ) < f (x) then x ← xnew ;else σ ← c × σ ;*/6 / 17

IntroductionHooke-Jeeves

MTS-LS1

BSrr

Tips

Setting

Results

Conclusion

Two main differences between MTS-LS1 and the Hooke-Jeeves method
1. MTS-LS1 does not adopt the exploratory move (vector-wise operat.)
2. MTS-LS1 reinitializes the step-size σ when σ is too small

7 / 17

Introduction

Hooke-Jeeves

MTS-LS1

BSrr

Tips

Setting

Results

Conclusion

The Hooke-Jeeves method vs. MTS-LS1
The Hooke-Jeeves method
Initialize x, σ ← σ init ;2 while not happy do
3xprev ← x;
4for i ∈ {1, . . . , D} do
5xnew ← x;
low6xnew← xi + σ(xup);ii − xi
7
if f (xnew ) < f (x) thenx ← xnew ;8else
9xnew ← x;
10xnew← xiilow
11− σ(xup);i − xinew12
if f (x) < f (x) then13x ← xnew
1

1415
16

17

if f (x) < f (xprev ) thenxnew ← x + (x − xprev );if f (xnew ) < f (x) thenx ← xnew ;else σ ← c × σ ;MTS-LS1
Initialize x, σ ← σ init ;2 while not happy do
3xprev ← x;
4for i ∈ {1, . . . , D} do
5xnew ← x;
low
6xnew
← xi − σ(xup);ii − xi
7
if f (xnew ) < f (x) thenx ← xnew ;8else
9xnew ← x;
10xnew← xi
i111121314151617

low+0.5σ (xup);i − xinew
if f (x) < f (x) thenx ← xnew

if f (x) = f (xprev ) thenσ ← c × σ;
low−15if σ(xupthen
1 − x1 ) < 10σ ← σ init

8 / 17

Introduction

Hooke-Jeeves

MTS-LS1

BSrr

Tips

Setting

ResultsConclusion

The Brent-STEP method for 1-dimensional optimization
The Brent method (e.g., fminbnd in Matlab)
 It simultaneously performs the bisection and the secant methods
 Pros : It performs very well on unimodal functions
 Cons : It performs poorly on multimodal functions

Select The Easiest Point (STEP) [Langerman 94]
 It sequentially selects an interval with the smallest difficulty Pros : It performs well on multimodal functions
 Cons : It generally converges slow

The Brent-STEP method aims to take their pros
 First, it runs the Brent method If the search fails (i.e., on multimodal functions), it then runs STEP
Richard Peirce Brent. Algorithms for Minimization without Derivatives. Englewood Cliffs, 1973
Stefan Langerman, Gregory Seront, Hugues Bersini: S.T.E.P.: The Easiest Way to Optimize a Function. International Conference on
Evolutionary Computation 1994: 519-524

9 / 17

Introduction

Hooke-Jeeves

MTS-LS1

BSrr

Tips

Setting

Results

Conclusion

BSrr: An extension of the Brent-STEP method to D-dimensional opt.
 BSrr applies Brent-STEP to each variable in a round-robin manner
 It is competitive with more sophisticated ones [Posı́k 15]

Initialize x;
2 while not happy do
3for i ∈ {1, . . . , D} do
4xnew ← x;
5xnew
← Apply a single iteration of brent step to xi ;i
6
if f (xnew ) < f (x) then7x ← xnew ;8
Update internal parameters of D brent step;
1

Petr Posı́k, Petr Baudis: Dimension Selection in Axis-Parallel Brent-STEP Method for Black-Box Optimization of Separable Continuous
Functions. GECCO (Companion) 2015: 1151-1158

10 / 17

Introduction

Hooke-Jeeves

MTS-LS1

BSrrTipsSetting

Results

Conclusion

The three optimizers are sensitive to the order of variables
Results of MTS-LS1 on Schwefel 1.2108

 Similar to LeadingOnes,
the first i variables aredependent

SP1

107
106
105

lexicalrandom104
103

i2
 f (x) = ∑Di=1 (∑j=1 xj )2040 60 80 100
Dimensions

 lexical: x1 , x2 , x3 , x4 , ...
 random: x9 , x1 , x8 , x3 , ...
 Max. fevals = 105 × D
 N. runs = 31

 MTS-LS1 perturbs variables in a lexical order (from x1 to xD )
 It can unintentionally exploit the order of variables

 Their operators are not permutation-invariant [Lehre 12] This issue can be very very easily addressed by randomly shuffling the order of perturbations
Per Kristian Lehre, Carsten Witt: Black-Box Search by Unbiased Variation. Algorithmica 64(4): 623-642 (2012)11 / 17

Introduction

Hooke-Jeeves

MTS-LS1

BSrrTips

Setting

Results

Conclusion

Experimental setup The 24 bbob-largescale functions [Varelas 20]
 Dimension D ∈ {20, 40, 80, 160, 320, 640}
 The results of L-BFGS were taken from [Varelas 19] as a base line The Hooke-Jeeves method and MTS-LS1
 We implemented them in C (https://github.com/ryojitanabe/largebbob2022)
 The maximum number of function evaluations: 104 × D
 The initial step size σ init = 0.4 (is this best for HJ?) The learning rate c = 0.5 and 0.9
 “HJ-5” and “MTS-LS1-5” are HJ and MTS-LS1 with c = 0.5
 “HJ-9” and “MTS-LS1-9” are HJ and MTS-LS1 with c = 0.9

 BSrr We used the Python implementation of BSrr (https://github.com/pasky/step) Default setting The maximum number of function evaluations: 103 × D
Konstantinos Varelas, Ouassim Ait ElHara, Dimo Brockhoff, Nikolaus Hansen, Duc Manh Nguyen, Tea Tušar, Anne Auger: Benchmarking
large-scale continuous optimizers: The bbob-largescale testbed, a COCO software guide and beyond. Appl. Soft Comput. 97: 106737(2020)
Konstantinos Varelas: Benchmarking large scale variants of CMA-ES and L-BFGS-B on the bbob-largescale testbed. GECCO (Companion)
2019: 1937-1945

12 / 17

Introduction

Hooke-Jeeves

MTS-LS1BSrr

Tips

Setting

Results

Conclusion

Aggregated results on the separable function group (f1 , . . . , f5 ) and themoderate conditioning function group (f6 , . . . , f9 ) for D = 320
BSrr, HJ-9, and MTSLS1-9 outperform L-BFGS on f1 , . . . , f5
 BSrr performs the best on f1 , . . . , f5 for all D HJ-5 and MTSLS1-5 (with the learning rate c = 0.5) do not work c = 0.5 is recommended for CEC functions, but unsuitable for BBOB?

1.0 bbob-largescale f1-f5, 320-D

BSrr0.8MTSLS1-90.6

HJ-90.4

MTSLS1-50.2

HJ-5

51 targets: 100..1e-08
15 instances

0.0v2.60246log10(# f-evals / dimension)

LBFGS

Fraction of function,target pairs

Fraction of function,target pairs

 They are outperformed by L-BFGS on f6 , . . . , f9
1.0 bbob-largescale f6-f9, 320-D

LBFGS

0.8

HJ-9

0.6

HJ-5

0.4

MTSLS1-9

0.2

MTSLS1-5

51 targets: 100..1e-08
15 instances

0.0v2.60BSrr

246log10(# f-evals / dimension)

13 / 17Introduction

Hooke-Jeeves

MTS-LS1

BSrr

Tips

SettingResults

Conclusion

Performance deterioration of BSrr on f2 and f4 for D ≥ 320
BSrr could not reach x∗ on f2 and f4 for D ≥ 320
 But, BSrr still performs better than the other optimizers
 The small max. fevals (103 × D) may be the reason
BSrr

0.8

MTSLS1-90.6

HJ-90.4

MTSLS1-5

51 targets: 100..1e-08
15 instances

HJ-5

0.2
0.0

v2.6

02
4
6
log10(# f-evals / dimension)

LBFGS

4 Skew Rastrigin-Bueche separ

Fraction of function,target pairs

Fraction of function,target pairs

4 Skew Rastrigin-Bueche separ

1.0 bbob-largescale f4, 160-D

1.0 bbob-largescale f4, 320-D

BSrr

0.8

MTSLS1-9

0.6

HJ-9

0.4

MTSLS1-5

51 targets: 100..1e-08
15 instances

HJ-5

0.2
0.0

v2.6

0

LBFGS

246
log10(# f-evals / dimension)

14 / 17

Introduction

Hooke-Jeeves

MTS-LS1

BSrr

Tips

Setting

Results

Conclusion

Poor performance of MTS-LS1 on f4
MTS-LS1 works well for f3 , but does not work for f4
 MTS-LS1 uses (almost) the symmetric operation
 MTS- LS1 can perform poorly on a function with a asymmetriclandscape structure, e.g., f4
BSrr

0.8

MTSLS1-90.6

HJ-90.4

MTSLS1-50.2

HJ-5

51 targets: 100..1e-08
15 instances

0.0v2.60246
log10(# f-evals / dimension)

LBFGS

4 Skew Rastrigin-Bueche separ

Fraction of function,target pairs

Fraction of function,target pairs

3 Rastrigin separable

1.0 bbob-largescale f3, 320-D

1.0 bbob-largescale f4, 320-D

BSrr

0.8

MTSLS1-90.6

HJ-90.4

MTSLS1-50.2

HJ-5

51 targets: 100..1e-08
15 instances

0.0

v2.60

LBFGS

246log10(# f-evals / dimension)

15 / 17

Introduction

Hooke-Jeeves

MTS-LS1

BSrrTips

SettingResults

Conclusion

Comparison of HJ and MTS-LS1 on f2 and f3 for D = 320
HJ can outperform MTS-LS1 on unimodal functions, e.g., f2
 HJ adopts the the exploratory move (vector-wise operat.)

MTS-LS1 can outperform HJ on multimodal functions, e.g., f3
 MTS-LS1 adopts the reinitialization strategy for the step-size σ HJ can be improved by a restart strategy or the reinitialization for σ
HJ-50.8

MTSLS1-50.6

HJ-90.4

MTSLS1-90.2

BSrr

51 targets: 100..1e-08
15 instances

0.0v2.60246log10(# f-evals / dimension)

LBFGS

3 Rastrigin separable

Fraction of function,target pairs

Fraction of function,target pairs

2 Ellipsoid separable

1.0 bbob-largescale f2, 320-D

1.0 bbob-largescale f3, 320-D

BSrr

0.8

MTSLS1-90.6

HJ-90.4

MTSLS1-50.2

HJ-5

51 targets: 100..1e-08
15 instances

0.0

v2.60LBFGS246log10(# f-evals / dimension)

16 / 17

Introduction

Hooke-Jeeves

MTS-LS1BSrr

Tips

Setting

Results

Conclusion

Conclusion
Benchmarking HJ, MTS-LS1, and BSrr on bbob-largescale BSrr generally performs the best on f1 , ..., f5
 BSrr can complement L-BFGS and CMA-ES variants , Its performance deterioration was observed on f2 and f4

 MTS-LS1 cannot handle the asymmetricity in f4
 Due to the symmetric operation
 The same is true for HJ

 HJ performs better than MTS-LS1 on unimodal functions But, HJ is outperformed by MTS-LS1 on multimodal functions
 A restart strategy or the reinitialization for σ is needed

Future work Benchmarking the winners of the CEC LSGO competitions
 E.g., MOS, SHADE-ILS, and CC-RDG3
 Especially, variable-decomposition-based approaches

17 / 17

Computation time of the three optimizers (10−5 seconds)
The C code is much faster than the Python code

Optimizers

Languages

20-D

40-D

80-D

160-D

320-D

640-D

HJMTS-LS1
BSrrCCPython

Na
4.1
13

4.2
2.0
20

5.9
5.8
33

11116221211204142270

 CPU time to run the three optimizers on the 24 bbob-largescale
functions for 2D function evaluations
 Computation environment
 Ubuntu 18.04
 Intel(R) 52-Core Xeon Platinum 8270 (26-Core×2) 2.7GHz
 Compile options -O2

 f21 for D = 640 may be particularly time-consuming
 f21 : the Gallagher’s Gaussian 101-me Peaks function

Unexpected results on f19 for any D pointed out by a reviewer (Thanks!)
The initialization method significantly influences the results
 The initial point in HJ-5, HJ-9, MTSLS1-5, and MTSLS1-9
 The center of the search space (0, ..., 0) The initial point in L-BFGS and BSrr
 randomly generated in the search space The solution at (0, ..., 0) may have a good objective value Known issue? (https://github.com/numbbo/coco/issues/1851)
Fraction of function,target pairs

19 Griewank-Rosenbrock F8F2

1.0 bbob-largescale f19, 20-D

HJ-5

0.8

MTSLS1-5

0.6

HJ-9

0.4

MTSLS1-9

0.2

BSrr

51 targets: 100..1e-08
15 instances

0.0v2.60246log10(# f-evals / dimension)LBFGS