A Two-phase Framework with a BézierSimplex-based Interpolation Method for
Computationally Expensive Multi-objective
Optimization
GECCO 2022 at Boston

Ryoji Tanabe (Yokohama National University),
Youhei Akimoto (University of Tsukuba),
Ken Kobayashi (Fujitsu Limited),
Hiroshi Umeki (Yokohama National University),
Shinichi Shirakawa (Yokohama National University),
Naoki Hamada (KLab Inc.)Introduction

Bézier simplex fitting

Two-Phase framework with the Bézier simplex (TPB)

Setup

Results

Conclusion

Four-phased HMO-CMA-ES [Loshchilov 16] performs well for expensive opt.
1st phase runs BOBYQA on K scalar optimization problems• BOBYQA [Powell 09]: SOTA mathematical derivative-free optimizer• It iteratively solves a trust region sub-problem using quadratic models
BOBYQA

BOBYQA
BOBYQA

BOBYQA
BOBYQA• 1st phase uses only the 10 × N fevals in total (N = Num. variables)• 2nd: SS-MO-CMA-ES → 3rd: MO-CMA-ES → 4th: CMA-ES• HMO-CMA-ES shows an excellent anytime performance ,Ilya Loshchilov, Tobias Glasmachers: Anytime Bi-Objective Optimization with a Hybrid Multi-Objective CMA-ES (HMO-CMA-ES). GECCO(Companion) 2016: 1169-1176
M. J. D. Powell. 2009. The BOBYQA algorithm for bound constrained optimization without derivatives. Technical Report DAMTP
2009/NA06. University of Cambridge

2 / 17

Introduction

Bézier simplex fitting

Two-Phase framework with the Bézier simplex (TPB)

Setup

Results

Conclusion

One drawback of the 1st phase in HMO-CMA-ES
It can achieve only K sparsely distributed solutions• Only a limited number of fevals are available• K needs to be as small as possible (K = 5 in ↙)Motivation• Can this issue be addressed by a solution interpolation approach?

3 / 17

Introduction

Bézier simplex fitting

Two-Phase framework with the Bézier simplex (TPB)

Setup

Results

Conclusion

Proposed: A Two-Phase framework with a Bézier simplex-based
interpolation method (TPB)
1st phase is similar to that in HMO-CMA-ES• It runs BOBYQA on K scalar problems, but its details are different• K = Num. objectives +1 (= 2 + 1 = 3 in this study)• The normalization procedure, a budget allocation strategy, the orderof scalar optimization, control parameters of BOBYQA, etc.

2nd phase interpolates the K(= 3) solutions by the Bézier simplex• It is theoretically well-founded and can fit the K solutions
buget1
1stbuget2
2nd

1st

2nd4 / 17

Introduction

Bézier simplex fitting

Two-Phase framework with the Bézier simplex (TPB)

Setup

Results

ConclusionBézier simplex: A generalized version of the Bézier curve to higher dims
The Bézier curve

The Bézier simplex(M = 2, N = 2, D = 3)

(M = 3, N = 3, D = 3)1

p(2,1)x2

p(0,3)

0.5

p(1,2)
p(3,0)

000.5

1x1
From [Kobayashi 19]• M : Num. objectives, N : Num. variables, D: Degree of a model• D determines the number of control points pd1 , ... ∈ RN
• Control points define a Bézier simplex model• It can describe the Pareto optimal solution set X ⋆ [Kobayashi 19]• When X ⋆ is homeomorphic to an (M − 1)-dim. simplex [Hamada 20]• The theoretically well-founded nice property for the interpolation ,Ken Kobayashi, Naoki Hamada, Akiyoshi Sannai, Akinori Tanaka, Kenichi Bannai, Masashi Sugiyama: Bézier Simplex Fitting: Describing
Pareto Fronts of Simplicial Problems with Small Samples in Multi-Objective Optimization. AAAI 2019: 2304-2313
Naoki Hamada, Kenta Hayano, Shunsuke Ichiki, Yutaro Kabata, Hiroshi Teramoto: Topology of Pareto Sets of Strongly Convex Problems.
SIAM J. Optim. 30(3): 2659-2686 (2020)

5 / 17

Introduction

Bézier simplex fitting

Two-Phase framework with the Bézier simplex (TPB)

Setup

Results

Conclusion

Example: Bézier simplex with M = 2 (N. obj), N = 2 (N. var), and D = 2A Bézier simplex model b ∶ t ↦ b(t)b(t) = t21 p(2,0) + 2t1 t2 p(1,1) + t22 p(0,2)• Input t ∈ RM : a parameter vector, and ∑M
m=1 tm = 1, tm ≥ 0• Output b(t) ∈ RN : a mapping of t. It can be a solution x ∈ RN
• Model parameters pd1 , ... ∈ RN : Control points• p(2,0) = (0.1, 0.7)

1p(1,1)• p(1,1) = (0.8, 0.8)p(2,0)
b(t2)

x2

b(t1)

0.5

• p(0,2) = (0.9, 0.2)b(t3)• t1 = (1, 0)b(t4)p(0,2)b(t5)000.5x11↦ b(t1 ) = (0.1, 0.7)

• t2 = (0.75, 0.25) ↦ b(t2 ) ≈ (0.41, 0.71)• t3 = (0.5, 0.5)

↦ b(t3 ) ≈ (0.65, 0.63)• t4 = (0.25, 0.75) ↦ b(t4 ) ≈ (0.81, 0.46)• t5 = (0, 1)↦ b(t5 ) = (0.9, 0.2)
6 / 17

Introduction

Bézier simplex fitting

Two-Phase framework with the Bézier simplex (TPB)

Setup

Results

ConclusionBézier simplex fitting to approximate a solution set X [Kobayashi 19]• Let X = {xk ∈ RN }K
k=1 be a solution set of size K• Let T = {tk ∈ ∆M −1 ⊆ RM }K
k=1 be a parameter vec. set of size K• tk corresponds to xk• We want a Bézier simplex model b that approximates X• How do we set control points, e.g., p(2,0) , p(1,1) , and p(0,2) ?

• The Bézier simplex fitting method adjusts the control points (pd )by minimizing the ordinary least squares loss function:
Kminimize∑ ∥xk − b(tk )∥2k=1• The loss function is a convex quadratic function with respect to pd• Its minimizer can be found by solving a normal equation
The PyTorch implementation is available athttps://github.com/rafcc/pytorch-bsf
Ken Kobayashi, Naoki Hamada, Akiyoshi Sannai, Akinori Tanaka, Kenichi Bannai, Masashi Sugiyama: Bézier Simplex Fitting: Describing
Pareto Fronts of Simplicial Problems with Small Samples in Multi-Objective Optimization. AAAI 2019: 2304-2313

7 / 17

Introduction

Bézier simplex fitting

Two-Phase framework with the Bézier simplex (TPB)

Setup

ResultsConclusion

1st phase applies BOBYQA to K scalar optimization problems {gwk }K
k=1• We set K = 2 + 1 = 3, w1 = (0, 1), w2 = (0.5, 0.5), w1 = (1, 0)• K should be K ≥ M + 1 to handle the nonlinear PS set• We use the weighted sum function as in HMO-CMA-ES• TPB can use any g, e.g., the weighted Tchebycheff function• We set a budget ratio r1st = 0.9• e.g., budget1st = 0.9 × 40 = 36 fevals when budget= 40 fevals• Each run of BOBYQA can use budget1st /K = 36/3 = 12 fevals

Results on f1 (Sphere/Sphere) with N = 2 in bbob-biobj
Objective space
120 w1-130
f2x2

Solution space
2w310w2-1-2
w1-3-4 -3 -2 -1 0
x1

-140

w2
w3-150390 400 410 420 430
f1
8 / 17

Introduction

Bézier simplex fitting

Two-Phase framework with the Bézier simplex (TPB)

Setup

Results

Conclusion

2nd phase interpolates the K sol. by a Bézier simplex model-based method
2.1 The fitting phase• The 1st phase obtained X = {x1 , x2 , x3 } using W = {w1 , w2 , w3 }fit• TPB treats wk as tfit
= {t1 , t2 , t3 }k , and T• TPB fits a Bézier simplex model b to X with T fit = W
2.2 The solution generation phase• budget2nd = budget - budget1st = 40 − 36 = 4 in this example
int int int• 4 solutions are generated by giving tint
1 , t2 , t3 , t4 to b

• We equally generate parameters on ∆M −1 , removing (0, 1) and (1, 0)

Results on f1 (D-Sphere) with N = 2 in bbob-biobj
120

w1-130tint
1f2

Objective space

2w31tint
40w2 tint
3int
-1
t2
int
-2
w 1 t1-3-4 -3 -2 -1 0x1

x2

Solution spacetint
2w2 tint
3tint
-150
4 w3
390 400 410 420 430
f1-140• tint
1 = (0.2, 0.8)
• tint2 = (0.4, 0.6)
• tint3 = (0.6, 0.4)
• tint4 = (0.8, 0.2)
9 / 17

Introduction

Bézier simplex fitting

Two-Phase framework with the Bézier simplex (TPB)

Setup

Results

Conclusion

Advantages and disadvantages of TPB
Advantages ,1. TPB can use any SOTA single-objective black-box optimizer
2. TPB can exploit the structure of the PS set
3. TPB is faster than model-based optimizers, e.g., ParEGO [Knowles 06]

Disadvantages /1. The poor anytime performance as in most two-phase approaches• They can obtain only a poor-quality solution set when they stop
before reaching the maximum budget [Dubois-Lacoste 11]• But, this is true for most model-based optimizers (due to the LHS)

2. It performs poorly when the PS topology cannot be a simplex• The 15/55 unimodal bbob-biobj problems would be OK• The 40/55 multimodal bbob-biobj problems would be NG
Joshua D. Knowles: ParEGO: a hybrid algorithm with on-line landscape approximation for expensive multiobjective optimization problems.
IEEE Trans. Evol. Comput. 10(1): 50-66 (2006)
Jérémie Dubois-Lacoste, Manuel López-Ibáñez, Thomas Stützle: Improving the anytime behavior of two-phase local search. Ann. Math.
Artif. Intell. 61(2): 125-154 (2011)10 / 17

Introduction

Bézier simplex fitting

Two-Phase framework with the Bézier simplex (TPB)

Setup

ResultsConclusion

Experimental setup• All experiments were conducted using COCO [Hansen 21]• The 55 bbob-biobj problems [Brockhoff 22] with N ∈ {2, 3, 5, 10, 20}• ICOCO : The uncrowded HV based on the unbounded external arch.
• When none of objective points dominates the reference point z,
ICOCO is based on the smallest distance to the ROI defined by z

• We compare TPB with HMO-CMA-ES [Loshchilov 16] and ...
• ParEGO [Knowles 06], MOTPE [Ozaki 20], K-RVEA [Chugh 18],
KTA2 [Song 21], and EDN-ARMOEA [Guo 22]• Maximum fevals: 20 × N , 30 × N , and 40 × N• Parameter setting for TPB:
• The number of weight vectors K in the 1st phase: 3• The budget ratio in the 1st phase r1st : 0.9• The degree of a Bézier simplex D: 2
Nikolaus Hansen, Anne Auger, Raymond Ros, Olaf Mersmann, Tea Tušar, Dimo Brockhoff: COCO: a platform for comparing continuous
optimizers in a black-box setting. Optim. Methods Softw. 36(1): 114-144 (2021)
Dimo Brockhoff, Anne Auger, Nikolaus Hansen, Tea Tušar: Using Well-Understood Single-Objective Functions in Multiobjective Black-BoxOptimization Test Suites. Evol. Comput. 30(2): 165-193 (2022)

11 / 17

Introduction

Bézier simplex fitting

Two-Phase framework with the Bézier simplex (TPB)

Setup

Results

Conclusion

Results on the 55 bbob-biobj problems with N = 2 (max. fevals = 40)
HMO-CMA-ES shows the best anytime performance• ParEGO is the best optimizer at 20 × N fevals

Fraction of function,target pairs• TPB is the second-worst optimizer
1.0 bbob-biobj f1-f55, 2-D

31 targets RLs/dim: 0.5..50
from refalgs/best2016-bbob-biobj.tar.gz10 instances

0.8

best 2016
HMO-CMA
ParEGO

0.6

KRVEA
KTA2

0.4

MOTPE
0.20.0EDN
v2.4.1.1, hv-hash=ff0e71e8cd978373

0TPB

2log10(# f-evals / dimension)
12 / 17

Introduction

Bézier simplex fitting

Two-Phase framework with the Bézier simplex (TPB)

Setup

Results

Conclusion

Results on the 55 bbob-biobj problems with N = 5 (max. fevals = 100)

Fraction of function,target pairs

TPB performs better than the five model-based optimizers• HMO-CMA-ES performs the best
1.0 bbob-biobj f1-f55, 5-D

31 targets RLs/dim: 0.5..50
from refalgs/best2016-bbob-biobj.tar.gz
10 instances

0.8

best 2016
HMO-CMA
TPB

0.6

KRVEA
ParEGO

0.4

MOTPE
0.2
0.0

EDN
v2.4.1.1, hv-hash=ff0e71e8cd978373

0

KTA2

2
log10(# f-evals / dimension)

13 / 17

Introduction

Bézier simplex fitting

Two-Phase framework with the Bézier simplex (TPB)

Setup

Results

Conclusion

Results on the 55 bbob-biobj problems with N = 10 (max. fevals = 200)
TPB performs better than HMO-CMA-ES at 20 × N fevals• TPB outperforms the model-based optimizers at anytime

Fraction of function,target pairs• Because KTA2 was too time-consuming, it was removed
1.0 bbob-biobj f1-f55, 10-D

best 2016

0.8

HMO-CMA

31 targets RLs/dim: 0.5..50
from refalgs/best2016-bbob-biobj.tar.gz
10 instances

TPB
0.6

ParEGO
0.4

KRVEA

0.2
0.0

MOTPE
v2.4.1.1, hv-hash=ff0e71e8cd978373

0EDN

2
log10(# f-evals / dimension)
14 / 17

Introduction

Bézier simplex fitting

Two-Phase framework with the Bézier simplex (TPB)

Setup

Results

Conclusion

Results on the 55 bbob-biobj problems with N = 20 (max. fevals = 400)

Fraction of function,target pairs

TPB performs better than HMO-CMA-ES at 20 × N fevals• Because ParEGO and EDN were time-consuming, they were removed
1.0 bbob-biobj f1-f55, 20-D

31 targets RLs/dim: 0.5..50
from refalgs/best2016-bbob-biobj.tar.gz
10 instances

0.8

best 2016

HMO-CMA

0.6

TPB
0.4

KRVEA
0.2
0.0

v2.4.1.1, hv-hash=ff0e71e8cd978373

0MOTPE

2log10(# f-evals / dimension)

15 / 17

Introduction

Bézier simplex fitting

Two-Phase framework with the Bézier simplex (TPB)

Setup

Results

Conclusion

Results on f1 , f28 , f46 , f53 with N = 10 (max. fevals = 200)
We did not expect the results on f53 with no simplex structure• The Bézier simplex can represent only a standard simplex
best 2016

0.8

HMO-CMA

31 targets RLs/dim: 0.5..50
from refalgs/best2016-bbob-biobj.tar.gz
10 instances

TPB

0.6

ParEGO
0.4

KRVEA

0.2
0.0

MOTPE
v2.4.1.1, hv-hash=ff0e71e8cd978373

0EDN

28 Rosenbrock/Rosenbrock

Fraction of function,target pairs

Fraction of function,target pairs

1 Sphere/Sphere

1.0 bbob-biobj f1, 10-D2

1.0 bbob-biobj f28, 10-D

best 2016

0.8

HMO-CMA

31 targets RLs/dim: 0.5..50
from refalgs/best2016-bbob-biobj.tar.gz
10 instances

TPB

0.6

ParEGO
0.4

KRVEA

0.2
0.0

MOTPE
v2.4.1.1, hv-hash=ff0e71e8cd978373

0log10(# f-evals / dimension)
best 2016

0.8

HMO-CMA
ParEGO

0.6

MOTPE
0.4

KRVEA

0.2
0.0

EDNv2.4.1.1, hv-hash=ff0e71e8cd978373

02
log10(# f-evals / dimension)

TPB53 Schwefel/Schwefel

Fraction of function,target pairs

Fraction of function,target pairs

46 Rastrigin/Rastrigin

1.0 bbob-biobj f46, 10-D

31 targets RLs/dim: 0.5..50
from refalgs/best2016-bbob-biobj.tar.gz
10 instances

EDN2log10(# f-evals / dimension)

1.0 bbob-biobj f53, 10-D

best 2016

0.8

HMO-CMA

31 targets RLs/dim: 0.5..50
from refalgs/best2016-bbob-biobj.tar.gz
10 instances

TPB0.6

ParEGO
0.4KRVEA

0.20.0MOTPE
v2.4.1.1, hv-hash=ff0e71e8cd978373

0EDN2log10(# f-evals / dimension)

16 / 17

Introduction

Bézier simplex fitting

Two-Phase framework with the Bézier simplex (TPB)

Setup

Results

Conclusion

Conclusion
Proposed: A Two-Phase framework with a Bézier simplex-based
interpolation method (TPB)• The 1st phase runs BOBYQA on K scalar optimization problems• The 2nd phase interpolates the K solutions by the Bézier simplex• It can describe the PS set under under certain conditions• The performance of TPB was investigates on bbob-biobj• TPB performs better than HMO-CMA-ES for N ≥ 10 at max. fevals• TPB performs better than the five model-based optimizers for N ≥ 5• TPB is computatoinally cheaper than the five optimizers

TPB can give a new perspective for expensive MO optimization• A non-Bayesian optimization approach• The use of the Bézier simplex for MO optimization
Future work
• An extension of TPB to optimization with more than 2 objectives• An extension of TPB to initialize the population in EMO
17 / 17

Average computation time of the optimizers over the 15 instances of f1• TPB is the fastest for N ≥ 5• Meta-model-based optimizers are generally time-consuming

Average time

• Especially for a larger N103102
10110010−1 23 5 10 20
Dimension

TPBMOTPEKRVEAKTA2EDN
ParEGOComparison of 7 optimizers on bbob-biobj for N. var N = 10 [Brockhoff 21]
HMO-CMA-ES performs the best for 102 × N (= 1 000) fevals• HMO-CMA-ES performs well for computationally expensive opt.

Dimo Brockhoff, Baptiste Plaquevent-Jourdain, Anne Auger, Nikolaus Hansen: DMS and MultiGLODS: black-box optimization benchmarking of two direct search methods on the bbob-biobj test suite. GECCO Companion 2021: 1251-1258

Definition of the Bézier simplex (M : Num. obj, N : Num. var, D: Degree)
The standard (M − 1)-simplex
⎫⎧
M⎪
⎪
⎪
⎪
∆M −1 = ⎨t = (t1 , . . . , tM ) ∈ RM ∣ ∑ tm = 1, tm ≥ 0⎬
⎪⎪
⎪
⎪
m=1⎭
⎩

• E.g., t = (0.2, 0.8) and t = (1, 0) for M = 2
A set of non-negative integers⎧⎫M⎪⎪⎪⎪
NMd = (d1 , . . . , dM ) ∈ NM ∣ ∑ dm = D⎬D ∶= ⎨⎪⎪⎪
⎪
m=1
⎩
⎭

• E.g., N22 = {d = (d1 , d2 ) ∈ N2 ∣d1 + d2 = 2} = {(2, 0), (1, 1), (0, 2)}
A Bézier simplex, b ∶ ∆M −1 → RN , b ∶ t ↦ b(t)Db(t) = ∑ ( )td pd
Md∈ND d• pd ∈ RN is a control point , e.g., p(2,0) = (4.1, −3.2), p(1,1) = (2.6, 0)
2D!
• (Dd ) ∶= d1 !...dM ! is a multinomial coefficient, e.g., ((2,0))• td ∶= td11 . . . tdMM is a monomial for each t and d, e.g., t(2,0) = (t21 , t02 )Example: Bézier simplex with M = 2 (N. obj), N = 2 (N. var), and D = 2
Db(t) = ∑ ( )td pd ,dd∈NMD
22
2=()t21 t02 p(2,0) + ()t11 t12 p(1,1) + ()t01 t22 p(0,2)(2, 0)(1, 1)(0, 2)= t21 p(2,0) + 2t1 t2 p(1,1) + t22 p(0,2)• p(2,0) = (0.1, 0.7)1

• p(1,1) = (0.8, 0.8)p(1,1)p(2,0)
b(t2)

x2

b(t1)

0.5

• p(0,2) = (0.9, 0.2)
b(t3)
b(t4)

p(0,2)
b(t5)

000.5

x11

• t1 = (1, 0), b(t1 ) = (0.1, 0.7)
• t2 = (0.75, 0.25), b(t2 ) ≈ (0.41, 0.71)• t3 = (0.5, 0.5), b(t3 ) ≈ (0.65, 0.63)• t4 = (0.25, 0.75), b(t4 ) ≈ (0.81, 0.46)• t5 = (0, 1), b(t5 ) = (0.9, 0.2)