Boundary Decomposition for Nadir Objective Vector Estimation
Authors: Ruihao Zheng
Zhenkun Wang
Venue: NeurIPS 2024 poster (2024)
Keywords: multi-objective optimization
nadir objective vector estimation
black-box optimization
evolutionary computation
Primary area: optimization
TL;DR: We propose a general and rigorous method for nadir objective vector estimation.

Abstract: The nadir objective vector plays a key role in solving multi-objective optimization problems (MOPs), where it is often used to normalize the objective space and guide the search. The current methods for estimating the nadir objective vector perform effectively only on specific MOPs. This paper reveals the limitations of these methods: exact methods can only work on discrete MOPs, while heuristic methods cannot deal with the MOP with a complicated feasible objective region. To fill this gap, we propose a general and rigorous method, namely boundary decomposition for nadir objective vector estimation (BDNE). BDNE scalarizes the MOP into a set of boundary subproblems. By utilizing bilevel optimization, boundary subproblems are optimized and adjusted alternately, thereby refining their optimal solutions to align with the nadir objective vector. We prove that the bilevel optimization identifies the nadir objective vector under mild conditions. We compare BDNE with existing methods on various black-box MOPs. The results conform to the theoretical analysis and show the significant potential of BDNE for real-world application.

Boundary Decomposition for Nadir Objective Vector Estimation
Ruíhao Zheng Zhenkun Wang"
School of System Design and Intelligent Manufacturing,
Southern University of Science and Technology 121326860mail. sustech. wws.sse
enu vangzhenkunn9O@gaai..co
Abstract
The nadir objective vector plays key role in solving multi-objective optimization problems (MOPs), where it is often used to normalize the objective space and guide the search. The current methods for estimating the nadir objective vector perform effectively only specific MOPs. This paper reveals the limitations of these methods: exact methods can only work on discrete MOPs, while heuristic methods cannot deal with the MOP with complicated feasible objective region. To fill this gap, we propose a general and rigorous method, namely boundary decomposition for nadir objective vector estimation (BDNE). BDNE scalarizes the MOP into a set of boundary subproblems. By utilizing bilevel optimization, optimized and adjusted alternately. thereby refining their optimal solutions to align with the nadir objective vector. We prove that the bilevel optimization identifies the nadir objective vector under mild conditions. We compare BDNE with existing methods on various black-box MOPs. The results conform to the theoretical analysis and show the significant potential of BDNE for real-world application.
boundary subproblems
Introduction
The multi-objective optimization problem (MOP) can be written as min. f(x) = (f.. s.t. x E S2
(1)
where x -I1,,... In) T is the decision vector (also called solution), and Ω R" denotes the feasible region. f: T + T." is composed of m objective functions, and f(x) is the objective vector corresponding to x.
Definition 1. Given two vectors V E Thm is said to dominate v (denoted as u < v), if and only uf S 04 for every E (1,..., m) and uj < U3 for at least one j E (1...., m}.
Definition 2. A decision vector x" and the corresponding objective vector f(x* are Pareto-optimal,
if there no X E such that f(x) dominates f(x") according to Definition
Definition 3. A decision vector x" E Ω and the corresponding objective vector f(x*) are weakly Pareto-optimal, if there does not exist another decision vector x E S2 such that f((x) < f((x") for all i m.
Definition 4. The set of all Pareto-optimal solutions called the Pareto set (denoted as PS), and the set of all pareto-optimat objective vectors is called the Pareto front (denoted as PF). Definition 5. The relative complement of the PF in the set of all weakly Pareto-optimal objective vectors called the weakly Pareto-optimal boundary (denoted W PB).
"Coneesooning author
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Definition 6. The ideal objective vector z zide is composed of the lower bounds of the PF, i.e., zit minxxrs PS fx(x) for i I....,m. m. The nadir objective vector znnd consists of the upper bounds of the PF, i... znad maxxEPs fi(x) for 1,...,711. M..
Definition 7. For the i-th objective function fi with i {1....,m] an objective vector 2 called the critical point of f. if it is Pareto aneetooptimal and has the worst ft value, i.c. 2 E {f(x))x arg xars }. The nadir objective vector is often determined by obtaining the critical point on each objective, since znad (0) for each m..
The nadir objective vector is fundamental concept of multi-objective optimization and has been widely applied to real-world problems [1 2 Specifically, numerous optimization methods operations involve the nadir objective vector. Firstly, the nadir objective vector is often used to guide the search in various tasks, including both continuous MOPs [ and discrete MOPs [6] 7 An inaccurate estimation of the nadir objective vector degrades the performance of exact algorithms (8], evolutionary algorithms [9]. and multi-objective learning [10]. Secondly, the nadir objective vector which can facilitate the application For example, accurate nadir objective vector is the
offers a comprehensive view of the PF for decision-maken
of preference-basee based algorithms [ 12 2 assumption of many interactive algorithms. A poor approximation may cause biased decisions. In addition, the nadir objective vector and the ideal objective vector widely used to normalize the objective space [3] Normalization with an inappropriately estimated nadir objective vector can cause performance deterioration of the optimization algorithm [14 15).
The ideal objective vector can acquired by minimizing each objective separately. Unfortunately, obtaining the nadir objective vector is much more complicated [T6 17]. Existing exact methods are developed for discrete MOPs, posing significant challenges for their extension to other MOPs. The remaining methods are heuristic, showing satisfactory performance
simple MOPs. For example, PF, and its nadir objective vector can be easily estimated using several heuristic methods [9]. However, when the MOP possesses complicated feasible objective region (e.g., an irregular PF and the W PB), all heuristic methods fail to approximate the nadir objective vector accurately.
DTLZI has an qquilateraltriangle-shseee
In this paper; we first demonstrate the shortcomings of existing methods in detail. After that, we propose a general method with theoretical guarantees called boundary decomposition for nadir objective vector estimation (BDNE). We implement BDNE for black-box MOPs and use 28 black- box problems to validate its performance. The results indicate that BDNE remarkably outperforms the existing methods. The major contributions of BDNE are summarized as follows:
Scalarization method for boundary decomposition. We define the boundary subproblem that converts an objective vector into a scalar via boundary weight vectors. We prove that the critical point of each objective can be found by optimizing partieular boundary subproblem under mild conditions (i.e., the critical point satisfies proper Pareto optimality). We also prove that the optimal solution any boundary subproblem is Pareto-optimal, thereby facilitating the search of the particular boundary subproblems.
Bilevel optimization based on boundary decomposition. We formulate a bilevel optimization problem for each objective, aiming to identify the particular boundary subproblem by com- paring the optimal solutions of boundary subproblems. The upper-level optimization seeks each objective's 's boundary weight vector that maximizes the objective function value; the lower-level optimization searches for the optimal solutions of given boundary subproblems. Besides, the trade-off of decision- makers can be involved in finding a satisfactory nadir objective vector.
2 Related Works
Existing nadir objective vector estimation methods can be divided into two categories: 1) exact methods and 2) heuristic methods.
Exact methods are all designed for discrete MOPs and cannot applied to other problems. For example, the methods in [88 19 assume that the objective function values are integers, limiting their applicability to continuous problems. Moreover, some exact methods are exclusively designed for multi-objective integer linear programming [20]. bilevel optimization problems are
Exact Method.

---

formulated in [21 and guarantee that their optimal solutions construct the nadir objective vector. The bilevel optimization is implemented solely for the discrete search space where an exhaustive search is available. However, the exact solver is often unavailable for many problems such as non-linear continuous ones, leading to uncertain optimality gaps. As a result, the pay-off table, which this method relies heavily on, may be tough to obtain. In addition, its lower-level optimization, including two stages, may exhibit significant unreliability and high computational costs. Another significant limitation of exact methods is their inability to solve beyond small-scale problems within reasonable runtimes, thus posing substantial challenges to their real-world applicability.
Heuristic Method. Heuristic methods readily apply to diverse MOPs yet lack theoretical guarantees. Generally, the heuristic method estimates the nadir objective vector as follows
gnad max [x( for i = 11.1,.... m. XES
where S is an iteratively improved solution set. S can be specified as the population of the multi- objective evolutionary algorithm (MOEA) [22] (denoted as SF1). When the population is the PS, Eq. 2 becomes the definition of the nadir objective vector. That is, SF1 can achieve the nadir objective vector under the ideal situation where the population is the PS. However, this is almost impossible because retaining inferior solutions, such as weakly Pareto-optimal or dominance-resisann ones, in the population is often inevitable (33 In case the population contains these inferior solutions, the SF1-based algorithm may be severely misled and fail to estimate the nadir objective vector, as shown in Figure 26 and Figure 2 (see Section 4. Several methods are proposed to mitigate the
impact of inferior solutions by selecting a subset from the population (24 25 26] Additionally, S 28
the extreme points are determined by finding the objective vector with minimum values on each objective function. This method is also known as the pay-off table method, which can overestimate underestimate the nadir objective vector [30 20). Some methods identify the objective vectors that are closest to axis vectors as extreme points. The distance between the objective vector and the axis vector can be measured by the Minkowski distance (e.g. L2 [3 and Loc [2]), the perpendicular distance [33], and the cosine similarity 19] In (34,, each objective is associated with single-objectio
can be obtained by identifying extreme points in the population. In 27
29
optimization subproblem
to determine m extreme points. In Appendix [A] we use an example to illustrate the deficiencies of heuristic methods in estimating the nadir objective vector. We can observe from Figure annd Table 4
that all methods incorrectly estimate the critical points as well as the nadir objective vector.
3 Methodology
To address the limited applicability of exact methods and the unreliability of heuristic methods, we propose a method with general applicability to any MOP and theoretical guarantees in this section. Specifically, our method does not necessitate the objective function value to be integer opposed to [8 19] and involves simpler optimization tasks compared to [21]. Our method also enables finding the nadir objective vector, unlike heuristic methods. Furthermore, a user-defined trade-off. In the following, we begin by introducing boundary decomposition and establishing its theoretical foundations. After that, we develop bilevel optimization method based on boundary decomposition to achieve alignment with the nadir objective vector. This method is then implemented for the black-box MOP, and its effectiveness is evaluated in the subsequent section.
method supports using
3.1 Boundary Subproblem
We define a boundary subproblem for the i-th objective as
( (1-0))(0)
m Es(() -3;
23 })}}
bd (x 2², ax) = max 1575m
+ a
(3)
m
where w' is called the boundary weight vector of the i-th objective, z" is a reference point, and 0 < a < 1. w satisfies three conditions: 1) w! = 0: 2) Vjj E (1....,m) .m) wy 2 0: 3) F j e (1..... m}. w > 0. The definition of the boundary subproblem is inspired by the modified weighted Tehebycheff metric (35] The contour surface of the boundary subproblem illustrated in Figure] [ Additionally, several examples are presented to demonstrate the optimal objective vector of the boundary subproblem. In the following, we provide the theoretical foundations. Claims are followed by corresponding explanations. All proofs are presented in Appendix F
3

---

P
235
02
055
05
95
(a) w (0.5, 0.5, 0)T
(h) w (0.5, 0.5, 0)T
(c) w
(0.7, 0.3, 0)
(d) w2 =0.77 0.3,0)
Figure 1: The contour surfaces of boundary subproblems.
Definition 8 (From (3].. Let 2 be the image of an objective vector z, where
2 = (1 - 0:
for i= I,..., m (0 (0<a<l).
(4)
j=1
Given a value of a and two objective vectors and v, u is said cone-dominate v (denoted as 2 v) if and only if û v.
Definition 9. Given value of a, objective vector is cone-optimal if no objective vector can cone-dominate
Theorem The optimal objective vector to the boundary subproblem with w' (denoted as z²) must be Pareto-optimal if and only ij {1,...,ma mm] \ {i} such that 2j S 2j.
Theorem 2. Let 2/ S 2 for every j {1, m} {i). (()) uniquely solves the boundary subproblem with
0.
j i
B
j # i,
(1)
and only (8) cone-optimal.
Corollary 1. To ensure the validity of Theorem 2 without further information, it is necessary satisfy the condition 2 S 2/0 for every j E {l....,m) {i}.
Firstly, we reveal the connection between the boundary subproblem and the nadir objective vector. The boundary subproblem involves two steps: transforming the given objective vector and scalarizing the transformed objective vector with the boundary weight vector. The transformation implies cone domination, which defines strict partial order (see Appendix F. for details) and belongs to the family of generalized Pareto domination 377. We assume that the critical points are cone-optimal and set of objective vectors is obtained by optimizing infinitely sampling boundary subproblems. According to Theorems [ and 2 this set a subset the PF and the critical points are included Finally, the nadir objective vector can be identified by Eq. (2) where S is specified as the obtained set.
Definition 10 (From (38)). A decision vector x" and the corresponding objective vector f(x*) are properly Pareto-optimal if they are Pareto-optimal and if there exists a finite number M > 0 such that, for each i and any Ω we have
fi(x') -xx)--i(x) Si(x) [,(x) - (xx))1fxx*))
< M,
(6)
where j satisfies f,(x") < fx(x).
Theorem 3. An objective vector is cone-optimal, if and only if the objective vector is Pareto-optimal and the value of a satisfies
m
a 5
(m-1)M m
Corollary 2. cone-optimal objective vector is also properly Pareto-optimal.

---

The following question arises: under what conditions can solution be considered cone-optimal?
Let u = (0, 1, T and = (0.2. 0.5, 0.5)T be a critical point and Pareto-optimal objective vector, respectively. If a 0.5, then v < (since i = (1, 2)T and v (0.8. 1.1, I.1)T); If a 0.1, (0.2, 1.2, 1.2)T and V (0.32, 0.62, 0.62)T). The critical point
then u e v and v A u (since is cone-dominated if an excessive a value is used. We should know how to set an appropriate to preserve the specific Pareto-optimal objective vectors. We find that cone domination is related to proper Pareto optimality. The idea of proper Pareto optimality is to divide the PS into proper and improper ones. The definition of proper Pareto optimality is shown in Definition TO That is, solution can be considered properly Pareto-optimal when at least one pair of objectives satisfies: a finite decrement in one objective requires a reasonable increment in the other objective. We also can infer that different proper Pareto-optimal solutions may necessitate distinct minimum values of M. Then we derive that a is bounded by M as shown in Theorem 3 Corollary i is established accordingly. We can let be a sufficiently small value such that the critical points cone-optimal.
m,] \ {i}. If an objective vector z' does not cone-dominate z and 2 2 24. then z" has a lower function value than z' with respect to some boundary subproblem of the i-th objective.
Theorem 4. Let z be an objective vector satisfying 2] 23 for every
Corollary 3. Let zf consist of the optimal values of m BLOPs and {z z - ) be the promising region. Any Pareto-optimal objective vector outside the promising region fails to address the trade-off of decision-makers. namely, M > p.
The remaining issue is that M is not known in advance, making it difficult to set a according to M. We introduce a user-defined parameter μ (p > 0) and let & (m-1))u+m H represents the upper bound of the trade-off between the k-th and (-th objectives, where k = arg maxi (x*))ff((r (x) and / = arg maxisjsm [x(x - fx(x). In other words, μ is the amount of increment in the value of one objective function that the pacciion-mmaker is willing to tolerate in exchange for one-unit decrement in another objective function. If the preference of decision-maker about ç is available, we have the guarantee shown in Corollary derived from Theorems 3 and 4 Corollary can guarantee to obtain a satisfactory nadir objective vector. When the preference is not provided, J can take a sufficiently large value. On the one hand, if finite trade-off M exists for the critical point, then can take an appropriate value from [M, 0o) to obtain the nadir objective vector. On the other hand, M + oo results in a + O, which means the corresponding objective vector is not properly Parcto-optimal. In practical terms, Pareto-optimal solution with a very large value of M does not essentially differ from an inferior solution for decision-makens If the critical points are improper. using a generally agreeable value of is reasonable.
m
Theorem 5. The optimal objective vector to the boundary subproblem with wi (denoted as z²) must be cone-optimal (or properly Pareto-optimal), if 3j {1,...,m,, m, \ {i} such that zj. < zz.
Theorem 6. Let 2] < 22 for every j E {f,....,) m) \ {d). If an objective vector z" is optimal for the boundary subproblem with w', z² must be an optimal objective vector to the boundary subproblem with
0
j = i
wj
B
(8)
3 x i.
Moreover, we can make minor modifications to Theorem D resulting in Theorem 5 Theorem 6 can be deduced using Theorem [ Theorem @ reveals the relationship between the boundary subproblem's 's optimal solution and the boundary weight vector, which is useful for designing the algorithm in Section 33
3.2 Nadir Objective Vector Estimation via Bilevel Optimization
Practically, we cannot have infinite boundary subproblems. In this subsection, an optimization problem is defined to obtain the nadir objective vector. Its two goals are: 1) converging to Pareto- optimal objective vectors and 2) identifying critical points from Pareto- case, both goals can be achieved through a single optimization procedure. Specifically, the critical points can be obtained by optimizing boundary subproblems using (1, 0)T and (0, 1)T as the weight vectors. This is because solving the boundary subproblem with equivalent to solving that with 3w" where B > 0 is constant. Unfortunatcly, the critical points cannot be obtained by
ones. In the 2-objective
5

---

fixed boundary subproblem when the MOP involves three or more objectives. That is, both goals cannot be achieved simultaneously. This motivates the formulation bilevel optimization problem (BLOP) for each objective to achieve the two goals: the lower-level optimization problem (I..OP corresponds to the first goal while the upper-level optimization problem (ULOP) is for the second goal. The BLOP is formulated below, based on the boundary subproblem.
Firstly, M affected by different value ranges of objective functions, which might lead to algorithm
performance deterioration 39. The objective space should be normalized properly. We let 2j = 0 for
j = 1,..,, in Eq. 3 and introduce two reference points x"1 and 2²2 (zj² > 25 for j = 1, 1.....,.00 m)
for normalization. Then, the boundary subproblem with normalization can be written as
wo (a-
m
bdn (x/ ('", x=1 :2
2 a) = max 15/5m
Σ
(9)
where (x) (fx(x) 2/ (z6² - 2/ for k = 1,... m. In this formulation, z²1 should be
set according to Theorem | and Corollary For example, it is reasonable to set 2²1 to zide since
zide < (x) for j = I,.... m such that (1 (x) + a/2 Σx [x( 2 0. Furthermore, z² should be set according [40 Secondly, several boundary subproblems might have the same optimal solution. On the one hand, solving the boundary subproblem with w is equivalent to solving that
with 3w' where 3 is a constant. We can let Ži= wj 1. On the other hand, Theorem 6
indicates that the optimal objective vectors some boundary subproblems may not align with the corresponding boundary weight vectors. For example, this scenario is common on discrete MOPs. We can penalize the flat landscape of the ULOP according the distance between the boundary weight vector and its optimal objective vector. Let x" be the optimal solution of the boundary subproblem
with w In this paper, we calculate the distance as dl w², x*) where
m
-Aj (w) Ug/ 1==1 uk)
0,
j = i
Uj
j *
(10)
(1 (0-o)s{(83 (x) + a m E fx(x)'
Let e be a sufficiently small constant, E {l...., m {i). and / = (l..... m) \ (i, l. Finally, the BLOP with respect to the i-th objective for i = 1,..,, m has the ULOP formulated
max. f. (w') = f((x') -edl (w", x)),
s.t.
w = 0, wi =1 - Σ w/
Σ JEI
w S 1,
(11)
JEI
0 5 w < for every j E I,
where x" is the optimal decision vector to the LLOP of the following form
min. f(x) = ghdn (x w x²2 2²,,a))
(12)
s.t. x E
The search is performed on the original decision space in the LLOP, while the search space of the ULOP can be viewed as R= (i.e., (m - diddinnnsa Euclidean space). For the i-th objective, the ULOP uses a boundary weight vector w' as a solution and requires maximizing the i-th penalized objective function value of the Pareto- ootimmll solution obtained by the LLOP. In other words, a feasible solution of the ULOP requires an optimal solution of the LLOP. We propose an algorithm framework called BDNE for estimating the nadir objective vector on the MOP with more than two objectives. Specifically, BDNE aims to solve these m BLOPs. The steps of BDNE are given in Algorithm[[ where μ is the user-defined upper bound of the trade-off (see Section for details). Three following issues should be specified: determine the reference points z"1 and z²², choose suitable single-objective optimizers, and set the stopping criteria.
3.3 Algorihm for Black-Box Multi-Objective Optimization Problems
To evaluate the viability of BDNE, we implement it for black-box MOPs. We adopt evolutionary algorithms the solvers in BDNE, Each ULOP uses CMA-ES 41 to search the eligible boundary

---

Algorithm BDNE
Input: An MOP, stopping criteria of m BLOPs, μ
Output: gnad
1: Initialization: a f [m- 1m determine zn2 and 2²²; configure solvers.
m
2: while stopping criteria of m ULOPs are not all satisfied do
3: Generate boundary weight vectors by the solvers of unstopped ULOPs.
4: Minimize LLOPs with the generated boundary weight vectors by the corresponding solvers.
5: Update parameters: z"1 and z²² (optional); parameters the solvers of unstopped ULOPs.
6: end while
weight vector(s). We utilize CMA-ES to optimize the ULOP for two reasons. First, CMA-ES is a state-of-the-art algorithm for single-objective black-box optimization. Second, optimal solutions to the LLOPs are not always available; instead, approximate solutions are often obtained. Consequently, the function values of the approximate solutions may exhibit noise. CMA-ES is suitable for this task as it demonstrates strong robustness in optimizing noisy functions AT. In each iteration, m ULOPs generate the pending LLOPs simultaneously. Then all LLOPs are solved collaboratively by the MOEA instead of optimizing each LLOP separately, This is because the superiority of MOEAs is demonstrated empirically and theoretically in solving multi-objective black-box optimization
problems 42 43
Table 1: Notation used in Section 3.3
Symbol
Description
Tu(m)
Maximum number iterations for cach CMA-ES procedure (the MOEA solving LLOPs).
N
Z number of generated LLOPss in each iteration of ULOPs.
P
P N; population of the MOEA for solving N LLOPs.
A
A = N; clite archive preserved the current best solutions for N LLOPs.
w/
The j-th boundary weight vector of the i-th objective.
Stopping Criteria and Reference Points. The maximal number of iterations is employed as the stopping criterion for the ULOP well as the LLOP. We Ta and Ti to denote the maximum number of iterations for the ULOP and the LLOP respectively. z=1 is set to the current best objective function values. r² is constructed by the current best objective function values of m ULOPs. Initially, EC-NSGA-II (22) runs for 77 iterations. The minimum and maximum objective function values of its final population determine the settings of z=" and z²² Then zd1 is updated once a new solution is generated. z² is only renewed when the parameters of CMA- update. During the optimization process, z"1 and z²2 iteratively approximate z idde and and respectively.
Upper-Level Optimization. m ULOPs represents m CMA-ES procedures. Let ( = N 1. The population size of each CMA-ES procedure is That is, (N - m.) boundary weight vectors are used to align with the eligible ones and evenly assigned to m objectives. Let (w 1, 1,...,,) .} denote the set of adjustable boundary weight vectors for the i-th objective. Initially, most of them sampled from the initial distribution of the CMA-ES procedure. The sampled points may need to be repaired to satisfy the constraints in the ULOP. For each objective, one boundary weight vector initialized to the vector with (m 1) elements being -ا (e.g., (0, 2 "). The remaining m ones, which different unit vectors, are fixed throughout the optimization of BLOPs. The LLOPs with these m boundary weight vectors can motivate the search of z ide Besides, they enhance population diversity when the adjustable boundary subproblems become similar. When LLOPs are stopped, the parameters of each CMA-ES procedure are updated first according to the & boundary weight vectors. Let x A be the best solution so far for the subproblem with wij, and then the fitness of w is defined as (Ji (x++)= eed (w*J, x².)) )) Note that some boundary weight vectors, such as repaired ones, might not be directly generated from the current distribution of the CMA-ES procedure. These injected solutions should obey the injection rule 45 Subsequently, the boundary weight vectors of the i-th objective are updated follows:
Step W {wid,) j = 1......)
...
} and then delete [
the worst boundary weight vector in W.
Step 2 Transform the best one in W according to Eq. 10
7

---

Step 3 Create [/ new ones via the i-th CMA-ES procedure and integrate them into W.
The updated 2 may substantially alter the normalized space in Eq. ( potentially changing the optimal solution to the L.OP. As Theorem repoertss,,,s.... Step can effectively preserve the best solution for the LLOP, irrespective of changes in the normalized space. Particularly, in the last iteration of the whs are all changed to the boundary weight vector with
ULOP (i.e., the -h iteration), w the best fitness for i = 1, .... m. More computational resources are allocated to the i-th objective's s current best LLOP in the final iteration. helps to obtain a better approximation for these m LLOPs.
Lower-Level Optimization. N LLOPs are optimized by an MOEA with population size N. An evolutionary algorithm executes solution reproduction and environmental selection iteratively. The reproduction procedure of the proposed MOEA includes two steps:
Step Use binary tournament selection based on π to obtain the mating pool from Step 2 Apply reproduction operators to create an offspring set of size N (denoted O).
t a utility vector including utility values solutions in P. solution with a lower utility value is more likely to enter the mating pool. The selection procedure is performed as follows:
Step 1
Calculate = (ri..... .II......PPPo)) ")PLo))) for PUO.
Step Select the smallest N elements of r and their corresponding solutions for the new л and the new generation of P, respectively.
Step 3 Identify the best solutions for the N subproblems from P U for the new generation of A.
Given decision vector x² PPOO, we let R be the ascending rank of gl (x*| z²1, z²² a) within (x w z=1 x²2 a)) x E PUO). rı is formulated as r& = (i) (R..) where 1= -(ii,)) 1 m, 1 c). x* with smaller F3 implies higher quality.
4 Experimental Studies
4.1 Experimental Setup
Instances. We proposed 4 scalable test problems denoted TN1-TN4. The feasible objective regions TNI and TN2 are shown in Figure 2a and Figure 2c The PF TNI a (m 1) 1)-dimensional simplex. TN2 has concave PF constructed by two
-)ddimensio simplices. TN3 and TN4 are the modified versions of TN1 and TN2 respectively. Their objective functions have different value ranges. Details of TN1-TN4 are available in Appendix(BB Moreover, we select problems with different shapes of feasible objective regions, including 6 existing test problems [46 47
48
49
(DTLLZ3, mDTL.733 MaF2, DTL.75, IMOP4, and IMOP6) and 4 real-world problems 50 51 52
(MP-DMP, MI-DMMP, RE3-4-7, and RE5-3-1), We consider test problems with 3, 5, and 8 objectives, which accordingly have 8, 12, and 16 variables. The PFs of RE3-4-7 and RE5-3-1 unknown and represented by their current best solution sets.
Comparison Algorithms BDNE is compared with 2 rep- resentative heuristic algorithms for black box MOPs: ECR- NSGA-II [54] (based on SF1) and DNPE (34 (based on EP6). ECR-NSGA-II is parameter-free parammeer--rrrrerrrreeee ing the corresponding reference (i.e., X 100). For BDNE, we set / 100 and 7 = 200. Then Tu = 14 according to the setting of 72 and F Fmmaz- The general algorithm settings are summarized in Table [2] where F'Ema means maximum number of function evaluations. Each algorithm executed 30 times on each instance, Additionally, the computer resources and algorithm runtimes can be found in Appendix C
Table General algorithm settings.
N
F'Emar
Operator
DNPE is configured accord-
60
180,000
SBX+PM
100
300,000
S3
160
480,000
Performance Metric. The estimated nadir objective vector is extracted by Eq. where S is the final population. Let gnnd be the estimated nadir objective vector. The error metric value is computed
by E E ((aped sgadd) (2ppadd 2 2ide) The result table records the mean metric value
"The source code is available at hethttp:: : http://hhhbb.eee//////eeeeenn///

---

Table 3: Comparisons of error metric values among ECR-NSGA-II, DNPE, and BDNE.
Problem
m
ECR-NSGA-II
A
DNPE
A
BDNE
3
132)
-2.23
1.203=11.500a7222 (2)
-0,203
3.14e 164605--10
TN1
5
(.)
-5.28
1.1
-0.171
0.000273 1 0.00074 (1)
8
12.7
-12.7
0.168 ()-
-0.146
0.0221 00.333 (1)
3
1.46
-1.46
0.223+154-mn(2)
-0.223
0.000172
TN2
5
4.77 191 (3)-
-4.77
4.3334486-10f2
-0.325
0.00803 .0.0233
8
12:2+
-12.2
0.333 30660102 2)-
-0.315
0.0185 -0.0004 (1)
3
1.3))
-2.15
0.263 14.02-
-0.263
2.39c- + 16
TN3
5
4.7 (m))
-4.69
0.263 850-0R (2)-
-0.262
0.000669 1.000m
8
12.7
-12.7
0.263 12200
-0.243
0.0195
3
-1.35
4.000044 (2)
-0.337
4.92c-054
00 (1)
TN4
5
(.
-5.34
0.337 1.96000
-0.335
0.00208 0.00022
8
12.3 (3)
-12.3
0.337 + 1.420005
-0.31
0.0268 +0.031
3
1.00268+002271
-0.00268
4.29e- 10
-2.48e-10
181e-1122200 10
DTLZ2
(.026940omm10)
-0.0269
6.04e- 10 (2)-
-4.36e-10
1.68e-10: 100 1
8
0.233 4o (3)-
-0.233
5.91e 40 (2)-
-2.04e10
3.87e- 10 10
0.171 (3)-
-0.164
0.0209
14. (2)-
-0.0143
0.00658...00000 1)
mDTLZ2
5
0.581 10
-0.576
0.0112
1 06 (2)-
-0.00648
0.0047 20.0045
8
0.826 (3)-
-0.823
0.00859 1.25 (2)-
-0.005
0.00358 50.0009
MaF2
3
0.0243
-0,0154
2.00888_29-.111
-2.le-06
0.00888 (1)
DTLZ5
3
0.005 (3)-
-0.005
5.81e-10 10(2)-
-5.11e100
666e 13
IMOP4
3
7.69c-05 4..00023
-7.69c-05
0.748 0.0322))
-0.748
4.16 17 1.09
IMOP6
3
0.0139 (3)115(3)
-0.0139
0.00125 2.1102=2210.0022
-0.00125
3.2c- 15 15.49
3
0.369 10 (3)-
-0.361
0.23 (2)-
-0.222
0.00777 05 (1)
MP-DMP
5
0.357 a00n (2)-
-0.344
0.16-021) (3)-
-0.754
0.0127 4.88c
3
80.8 +o0ess (3)-
-80.7
0.00699 22 (1)+
0.00917
0.0162+9.56e.0ff
ML-DMP
5
(3)
-85.1
0.5012576-06()
-0.521
0.0397=0.072
RE3-4-7
3
0. (0000
-0.0538
0.545+26tenn() (3)-
-0.466
0.0787 O.0 (1)
CRE5-3-1
5
24.8 24.8261903)
-24.6
0.191 17 17
8.58c-08
0.1911999-002
Total +/=/- Average rank
0/1/27
2/0/26
2.8929(3)
2.0357(2)
1.0714(1)
The approximate PF may be the reason for the large error on CRE5-3-1 since the results of DNPE and BDNE are similar.
and the standard deviation across all runs for each instance. The performance rank on each instance inside parentheses. "+", "=" or "_" denotes that the performance of the corresponding algorithm is statistically better than, similar to, or worse than that of BDNE based on Wilcoxon's 's rank sum test at 0.05 significant level. "A" " indicates the gap between the mean metric value of the corresponding algorithm and that of BDNE. The best mean metric values are also emphasized.
4.2 Results
Table Bshows the statistical results on 28 instances. Across most instances, BDNE outperforms the other algorithms and has mean metric values below 5%. In Figure 2 we can see that BDNE accurately approximates at least one critical point for each objective, consistent with our theoretical analysis. DNPE ranks second. DNPE has competitive results on MaF2, DTLZ5, DTLZ2, mDTLZ2, IMOP6, 3-objective ML-DMP, and CRE5-3-1. We can infer that the extreme points determined by DNPE are very close to the critical points of these MOPs. Nevertheless, the performance of DNPE deteriorates on other instances. Besides, comparing the results between TNI and TN3, value ranges of objective functions significantly impact DNPE but hardly affect BDNE. ECR-NSGA-II achieves the worst overall performance. Moreover, it has large standard deviations on many instances, which indicates its highly unstable performance. This is because ECR-NSGA suffers from dominance-resistam

---

A
Py
ECRANGAA-I
PB
Cálicai
h
5
f
f
(a) TN1
(b) TNI
(c) TNI
(d) TN1
6
RCE-NSCA-1
DNPR
BONE
pial
0
0
8
f
(c) TN2
(f) TN2
(g) TN2
(h) TN2
Figure 2: Plots of the final solution sets with median error metric values.
solutions. For example, ECR-NSGA- retains solutions close to the WPB in Figure 2bland Figure Each of these solutions has at least one inferior objective function value.
In general, the two algorithms have huge performance gaps compared with BDNE. The effectiveness and superiority of BDNE are demonstrated. More experiments are presented in Appendix
Conclusion, Limitation, and Future Work
Conclusion. In this paper, we have revealed the deficiency of existing methods in estimating the nadir objective vector. Specifically, exact methods suffer from limited applicability and high computational costs, while the irregular PF and the W PB can cause significant challenges for heuristic methods. We have proposed a new scalarization method, which can define specific boundary subproblems find the nadir objective vector under mild conditions. We have formulated mn BLOPs using boundary subproblems and designed a corresponding algorithm framework called BDNE. We have also conducted experimental studies validate the effectiveness of BDNE. In experiments, BDNE adopts evolutionary algorithms and effectively approximates the nadir objective vectors of various black-box MOPs.
Limitation and Future Work. The estimated nadir objective vector can be obtained beforehand or improved with the optimization process. In the paper, we present BDNE independent algorithm (i.e., estimate the nadir objective vector beforehand). BDNE into the iteration of algorithm to enhance its overall performance (see Appendix [E.4 some pilot studies). Furthermore, BDNE has been implemented in a general manner. We plan to refine BDNE for specific applications, including multi-objective discrete optimization problems. Potential societal impacts can be found in Appendix D
the future, we will investigate how to integrate
Acknowledgments and Disclosure of Funding
This work supported by the National Natural Science Foundation of China (Grant No. 62106096 and Grant No. 624761188 18), the Natural Science Foundation of Guangdong Province (Grant No. 2024A 151501 1759), the National Natural Science Foundation of Shenzhen (Grant No.JCY1200005301133013333 130103033
References
[1] Asiri Umenga Weerasuriya, Xuelin Zhang, Jiayao Wang, Bin Lu, Kam Tim Tse, and Chun-Ho Liu. Performance evaluation of population-based metaheuristic algorithms and decision mocisinn-making
10

---

for multi-objective optimization of building design. Building and Environment, 198: 107855, 2021.
[2] Mena, M Godoy, C Catalán, P Viveros, and Enrico Zio. Multi-objective two-stage stochastic unit commitment model for wind-integrated power systems: A compromise programming approach. International Journal of Electrical Power & Energy Systems, 152:109214, 14, 2023.
[3] Mostafa Ekhtiari, Mostafa Zandich, and Erfan Babace Tirkolace. Optimizing the dam site selection problem considering sustainability indicators and uncertainty: An integrated decision- making approach. Journal of Cleaner Production, 428:1392400 2023.
[4] Xinye Cai, Zhiwei Mei, and Zhun Fan. decomposition--ass many-objective evolutionary algorithm with two types of adjustments for direction vectors. IEEE Transactions Cyhernetics, 48(8):2335-234) 2348, 2018.
[5] Yingbo Xie, Shengxiang Yang. Ding Wang. Junfei Qiao, and Baocai Yin. Dynamic transfer ref- erence point-oriented MOEA/D involving local abjective-space knowledge. IEEE Transactions on Evolutionary Computation, 26(3):542-554, 2022.
[6] Jiahai Wang. Taiyao Weng, and Qingfu Zhang. A two-stage multiobjectiive evolutionary algorithm for multiobjective multidepot vehicle routing problem with time windows. IEEE Transactions on Cybernetics, 49(7):2467-2472 2019.
[7] Ilgin Dogan, Banu Lokman, and Murat Köksalan. Representing the nondominated set in multi- objective mixed-integer programs. European Journal of Operational Research, 296(3):804-818, 2022.
[8] Mariana Mesquita- Cunha, José Rui Figueira, and Ana Paula Barbosa-Póvon New e-constraint methods for multi-objective integer linear programming: A Pareto front representation approach. European Journal of Operational Research, 306(1):286-)))) 307,,30700100 2023.
[9] Yanan Sun, Bing Xue, Mengjie Zhang, and Gary G Yen. A new two-stage evolutionary algorithm for many-objective optimization. IEEE Transactions on Evolutionary Computation, 23(5):748-761, 2019.
[10] Xiaoyuan Zhang. Xi Lin, Bo Xue, Yifan Chen, and Qingfu Zhang. Hypervolume maximization: A geometric view of Pareto set learning, Advances in Neural Information Processing Systems (NeurIPS), 36, 2023.
[11) Jurgen Branke, Jürgen Branke, Kalyanmoy Deb, Kaisa Miettinen, and Roman Slowiński. Multiobjective optimization: Interactive and evolutionary approaches, volume 5252. Springer, 2008
[12] Handing Wang, Markus Olhofer, and Yaochu Jin. mini-review on preference modeling and articulation in multi-objective optimization: current status and challenges. Complex & Intelligent Systems, 3:233-245, 2017.
[13] Kaisa Miettinen. Nonlinear multiobjective optimization. Springer, 1998.
[14] Oleg Grodzevich and Oleksandr Romanko. Normalization and other topics in multi multi-objective optimization. In Proceedings of the Fields- Industrial Problems Workshop, pages 89-101, 2006.
[15] Linjun He, Hisao Ishibuchi, Anupam Trivedi, Handing Wang, Yang Nan, and Dipti Srinivasan. A survey of normalization methods in multiobjective evolutionary algorithms. IEEE Transactions on Evolutionary Computation,
1048, 2021.
[16] Kalyanmoy Deb and Kaisa Miettinen. A review of nadir point estimation procedures using evolutionary approaches: tale of dimensionality reduction. In Proceedings of the Multiple Criterion Decision Making Conference (MCDM). 2009.
[17] Julian Blank, Kalyanmoy Deb, and Proteek Chandan Roy. Investigating the normalization pro- cedure of NSGA-III. In International Conference on Evolutionary Multi-Criterne Optimization (EMO), pages 229-240. Springer, 2019.

---

[18] Murat Köksalan and Banu Lokman. Finding nadir points in multi- integer programs. Journal of Global Optimization, 62:55-77, 2015.
[19] Özgür Özpeynirei. On nadir points of multiobjecctiv integer programming problems. Journal of Global Oplimization, 69:699-712, 2017.
[20] Natashia Boland, Hadi Charkhgard, and Martin Savelsbergh. A new method for optimizing a linear function over the efficient set of a multiobjective integer program. European Journal of Operational Research, 260())904-919, 2017.
[21] Gokhan Kirlik and Serpil Sayın. Computing the nadir point for multiobjective discrete opti- mization problems. Journal of Global Optimization, 62:79 99, 2015.
[22] Kalyanmoy Deb, Kaisa Miettinen, and Shamik Chaudhuri. Toward an estimation of nadir objective vector using hybrid of evolutionary and local search approaches. IEEE Transactions on Evolutionary Computation, 14(6):821-8)) 1418821111,,220 2010.
[23] Kokolo Ikeda, Hajime Kita, and Shigenobu Kobayashi. Failure of pareto-based moeas: Does non-dominated really mean near to optimal? In IEEE Congress on Evolutionary Computation (CEC), volume 2, pages 957-962. IEEE, 2001.
[24] Xinye Cai, Zhiwei Mei, Zhun Fan, and Qingfu Zhang, A constrained decomposition approach with grids for evolutionary multiobjective optimization. IEEE Transactions on Evolutionary Computation, 22(4)5564-577, 2018.
[25] Mengzhen Wang, Fangzhen Ge, Debao Chen, and Huaiyu Liu. A many-tbee evolutionary algorithm with adaptive convergence calculation. Applied Intelligence, 53264):17200-11221 2023.
[26] Rammohan Mallipeddi, Kedar Nath Das, et al. A twin-archive guided decomposition based cetti//mannnoojjectiii evolutionary algorithm. Swarm and Evolutionary Computation, 71:101082, 2022.
[27] Ryoji Tanabe, Hisao Ishibuchi, and Akira Oyama. Benchmarking multi-and many-objective evolutionary algorithms under two optimization scenarios. IEEE Access, 5: 5:19997-19619, 2017.
[28] Hemant Kumar Singh, Kalyan Shankar Bhattacharjee, and Tapabrata Ray. Distance-based subset selection for benchmarking in evolutionary multi/many-objecaee optimization. IEEE Transactions on Evolutionary Computation, 23(5):904-912, 2019.
[29] Zhenkun Wang, Hui-Ling Zhen, Jingda Deng, Qingfu Zhang, Xijun Li, Mingxuan Yuan, and Jia Zeng. Multiobjective pptimization-aided decision making system for large-scale manufacturing planning. IEEE Transactions on Cyhernetics, (2(8)833268333) 2022.
decision-making
[30] Matthias Ehrgott and Dagmar Pondel. Computation of ideal and nadir values and implications for their in MCDM methods. European Journal of Operational Research, 151(1):1191139 2003.
[31] Yiping Liu, Dunwei Gong, Jing Sun, and Yaochu Jin. A many-objective evolutionary algorithm using a one-by-one selection strategy. IEEE Transactions on Cybernetics, 47(9):2689-2702. 2017.
[32] Kalyanmoy Deb and Himanshu Jain, An evolutionary many-objective optimization algorithm using reference-pont corecce---ontttttt based nondominated sorting approach, part I: Solving problems with box constraints. IEEE Transactions on Evolutionary Computation, 18(4):577-601, 2014.
[33] Zhengping Liang, Kaifeng Hu, Xiaoliang Ma, and Zexuan Zhu. A many-objective evolution- ary algorithm based a two-round selection strategy. IEEE Transactions Cybernetics, 5 51(3):1417-1429, 2021.
[34] Yanan Sun, Gary G Yen, and Zhang Yi. IGD indicator-based evolutionary algorithm for many-objective optimization problems. IEEE Transactions on Evolutionary Computation, 23(2):173-187,22 2019.
12

---

[35] Ignacy Kaliszewski. A modified weighted Tchebycheff metric for multiple objective program ming. Computers & Operations Research, 14(4):315-323 1987.
[36] Cristian Ramirez-Atencia, Sanaz Mostaghim, and David Camacho, A knee point based evo- lutionary multi-objective optimization for mission planning problems. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO), pages 1216-1223, 2017.
[37] Chenwen Zhu, Lihong Xu, and Erik Goodman. Generalization of Pareto-optimality for many-objective evolutionary optimization. IEEE Transactions on Evolutionary Computation, 20(2):299-315, 2016.
[38] Arthur M Geoffrion. Proper efficiency and the theory of vector maximization. Journal of Mathematical Analysis and Applications, (1(3)668-630 1968.
[39] Hisao Ishibuchi, Lie Meng Pang, and Ke Shang. Effects of dominance modification on hypervolume- based and IGD-based performance evaluation results of NSGA-IL. In Proceedings of the Genetic and Evolutionary Compulation Conference (GECCO), pages 679-687, 2023.
[40] Linjun He, Hisao Ishibuchi, and Dipti Srinivasan. Metric for evaluating normalization methods in multiobjective optimization. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO), pages 403-411, 2021.
[41] Nikolaus Hansen. The CMA evolution strategy: A tutorial. arXiv preprint 2016.
[42] Qingfu Zhang and Hui Li. MOEA/D: A multiobjective evolutionary algorithm based on decomposition. IEEE Transactions on Evolutionary Computation, 11(6):712-731, 2007.
[43] Duc-Cuong Dang, Andre Opris, and Dirk Sudholt. Crossover can guarantee exponential speed-ups in evolutionary multi-objective optimisation. Artificial Intelligence, page 104098, 2024.
[44] Nikolaus Hansen. Injecting external solutions into CMA-ES. arXiv preprint arXiv: 2011.
[45] Saúl Zapotecas- Zapttecus-Martine,, Bilel Derbel, Arnaud Liefooghe, Dimo Brockhoff, Hernán E Aguirre, and Kiyoshi Tanaka. Injecting CMA-ES into MOEA/D. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO), pages 783-790, 2015.
[46] Kalyanmoy Deb, Lothar Thiele, Marco Laumanns, and Eckart Zitzler. Scalable test problems for evolutionary multiobjective optimization. In Evolutionary multiobjective optimization: Theoretical advances and applications, pages 105-145. Springer, 2005.
[47] Ran Cheng, Miqing Li, Ye Tian, Xingyi Zhang, Shengxiang Yang, Yaochu Jin, and Xin Yao. benchmark test suite for evolutionary many-objective optimization. Complex & Intelligent Systems, 3:67-81, 2017.
[48] Zhenkun Wang, Yew-Soon Ong, and Hisao Ishibuchi. On scalable multiobjective test problems with hardly dominated boundaries. IEEE Transactions Evolutionary Computation, 23(2)2217~ 231, 2019.
[49] Ye Tian, Ran Cheng, Xingyi Zhang, Miqing Li, and Yaochu Jin. Diversity assessment of multi- objective evolutionary algorithms: Performance metric and benchmark problems [research frontier]. IEEE Computational Intelligence Magazine, 14(3):61-74, 2019.
[50] Mario Köppen and Kaori Yoshida. Substitute distance assignments in NSGA-II for handling obje-obeective optimization problems. In International Conference on Evolutionary Multi- Criterion Optimization (EMO), pages 727-741. Springer, 2007.
[51] Miqing Li, Crina Grosan, Shengxiang Yang, Xiaohui Liu, and Xin Yao. Multiline distance min- imization: A visualized majy-obeective test problem suite. IEEE Transactions Evolutionary Computation, 22(1):61-7,, 2018
[52] Ryoji Tanabe and Hisao Ishibuchi. An easy-to-use real-world multi-objective optimization problem suite. Applied Soft Computing, 89:106078, 2020.
13

---

[53] Robin C Purshouse and Peter J Fleming. On the evolutionary optimization of many conflicting objectives. IEEE Transactions on Evolutionary Computation, 11(6):770-784, 2007.
[54] Handing Wang, Shan He, and Xin Yao. Nadir point estimation for many-objective optimization problems based on emphasized critical regions. Soft Computing, 2109):2283-2295, 2017.
[55] Yieun Hua, Qiqi Liu, Kuangrong Hao, and Yaochu Jin. A survey of evolutionary algorithms for multi-objective optimization problems with irregular pareto fronts. IEEE/CAA Journal of Automatica Sinica, 8(2):303-31) 318, 2021.
[56] Simon Huband, Philip Hingston, Luigi Barone, and Lyndon While. review of multiobjec- tive test problems and scalable test problem toolkit. IEEE Transactions on Evolutionary Computation, 10(5):47-5566, 2006.
[57] Öngür Özpeynirei and Murat Köksalan. An exact algorithm for finding extreme supported non- dominated points of multiobjective mixed integer programs. Management Science, 56(12):2302- 2315, 2010.
[58] Qite Yang, Zhenkun Wang, and Hisao Ishibuchi. is hard to distinguish between dominance resistant solutions and extremely convex Pareto optimal solutions. In International Conference on Evolutionary Multi-Criterion Optimization (EMO), pages 3-14. Springer, 2021.
[59] Ye Tian, Ran Cheng, Xingyi Zhang, and Yaochu Jin. PlatEMO: A MATLAB platform for evo- lutionary multi-objective optimization [educational forum]. IEEE Computational Intelligence Magazine, 12(4):73-87, 2017.
[60] Ruihao Zheng and Zhenkun Wang. A generalized scalarization method for evolutionary multi- objective optimization. Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), volume 37, pages 12518-12525 2023.
[61] Eckart Zitzler and Lothar Thiele. Multiobjective evolutionary algorithms: A comparative case study and the strength Pareto approach. IEEE Transactions on Evolutionary Computation, 3(4::257-271 1999.
14

---

This is an appendix for "Boundary Decomposition for Nadir Objective Vector Estimation". Specifi- cally, we provide:
Detailed analyses of heuristic methods (Appendix A
Mathematical models of the proposed benchmark problems, i.e., TN1-TN4 (Appendix B
The computational environment, algorithm runtimes, and the complexity analysis of BDNE (Appendix C
The potential societal impact of this work (Appendix D):
More experimental results and analyses including ablation studies, the impact of μr, and the comparison with other heuristic methods (Appendix
Properties of the cone domination and proofs of theorems and corollaries (Appendix) F
A Deficiencies of Heuristic Methods
Existing heuristic methods for the nadir objective vector estimation can be divided into two cate- gories [15] straightforward methods and extreme--oint--asee methods. We an example PF to illustrate the drawbacks of heuristic methods in estimating the nadir objective vector. As shown in Figure 3 the PF consists of two triangles and is concave. We uniformly sample 225 points along the PF in order to include sufficient critical points. We use these sampled points each method's population and test its performance in estimating the nadir objective vector.
The experimental results are summarized Table 4 and plotted in Figure 4 We can observe from Table that all methods incorrectly estimate the nadir objective vector. Specifically, Figure show that methods except for SF4 acquire the critical points fi and fz but miss that of f3- As shown in Figure 3 the critical point of fa distant from every axis and thereby difficult obtain by these methods.
PF
PF
(0.9, 0.7, 1.57
10.1.1
f
(1.0, o
/1
fr
(1,1,07
(a) Detailed information
(b) Another perspective
Figure Illustrations of an example PF. The critical points of f1 are convex combinations of (1, O, 1)T and (1, 1,TT, The critical points of f2 convex combinations of (0, 1)T and (1, O)T, The critical point of fa is (0.9, 0.7, L.5)T. The nadir objective vector is 1,,1,
15

---

Table 4: Estimated nadir objective vectors of existing heuristic methods. The nadir objective vector (1, 1, 1.5)T. "SFx" denotes the straightforward method; "EPx" denotes the extreme-pone caaee--oontbbaaa based method. Parameters settings: the minimum number of selected points is set to 10 for SF3 and SF4; À in EP6 is set 100.
Method
Result
SF2 24
1.14)T
SF3 25
(1,
SF4
26
(0.88, 0.96, 1.2)T
EP1
29
(1,
EP2
23
(1,
EP3
L2)
[1
(1, (1,1,
L
32
(.39)
EP4
33
(1,1, 1.18T
EP5
EP6
(1, 1,,88
1.5
Onikal
Onikal
puest
1.5
Uiselecal pozzf..
Selected
155
Uracleted poizal. Selozed
0.5
0.5
0.5
8-
0.5
0.5
0.5
0.5
0.5
0.5
ft
(a) Sampled points
(b) SF2
(c) SF3
Unadectal paint
Retresre polzzs
Ectrann point
13
Serected poirt
Extrams point
point f
G
DOOS
0.5
0.5
0.5
0.5
fi
f0
fi
f:
fi
(d) SF4
(e) EPI or EP2
(I) EP3 (L2)
Extiessa: pein of
Earmmn pair of ft Eainm piu. &o
Ectrmn point of
Extesss:: jain of Extawnar
Ecirms point of Extroar
1.5
1.5
Earnus pour
1.5
0.5
0.5
0.5
0.5
0.5
0.5
0.5
0.5
0.5
J
f9
fi
f1
(g) EP3 (Loz) or EP5
(h) EP4
(i) EP6
Figure 4: Illustrations of selected points obtained by existing heuristic methods.
16

---

B Test Problem with Adjustable Critical Points
B.1 Test Problem Generator
The existing test problems [55] can not have various critical points. Many test problems share similar (or even identical) nadir objective vector configurations. For example, most problems of DTLZ [46] and WFG (56) are constructed from the unit simplex (i.e., equilateral triangle). The critical points of the unit simplex its vertices. We design problem generators that have controllable critical points.
Each objective function of the proposed test problem generators takes the following form f((x) = (x),(x))(1 + (x(x))),
(13)
where 8; is constant such that different objectives have different ranges of values; [0, 1| C IR, and X, = (#1...., Imm and Xı5 (Im+1,...,, F are subvectors of x. I: (x(x(1) 0 is called the distance function, which specifies
9:(x11) = 10
Σ (xy 0.3)², JEJ.
(14)
J + 2m + 1, ......
m
hx(x)) is termed as the position function, which determines the shape of the PF.
B.1.1 Generator
The PF is simplex. Firstly, we define y(1)) [0, dimensional vector (y1...., -um) as follows
[0, 10 as a base. returns an m-
34
y1
for 1,..., m.
(15)
m
Σ
3z
1=1
(y(x)))x E [0, 1)" is an (m 1)-dimensional unit simplex. Then the position function value vector is calculated by
h(x;) = Vy(xi),
(16)
where V [v2 v determines vertices of the PF. When (I,..., 1)T, v a vertex PF. Any v² should be non non-dominated. V is the particular parameter to be specified. The critical points depend on the settings of V.
B.1.2 Generator
The PF is two adjacent simplices, We modify the base of Generator to
1 1A S 0.5,
2x m
5z
i=
1,..., m 1 xm > 0.5,
2(1 - )m )
Σ
V/
jml
A Fm 0.5,
(17)
2z m
2(1 x.)
i = mm 0.5.
2(1 Rm))
Letting
> 1, = 3,
(18)
" <,,1433,
and
f1. }#1
4/ 10 0, j=i,
(19)
17

---

the position function value vector is
[V((x)) (V'y(x1), Im > 0.5,
Im 0.5,
h(x1)
(20)
where
[v] u. v V' = [v]
m v²),
(21)
u,
The PF of this generator consists of two simplices. Assume that s = (1....,1)1 1)T. The vertices of two simplices are the column vectors of and V respectively. The difference between and V the last column. That is to say, two simplices share many common edges and they are adjacent. is the particular parameter to be specified. The unique critical point of fa is u. The critical points of other objectives are the same the inverted unit simplex whose objective vectors any edge are critical points.
6
F
f
(a) Detailed illustration
(b) Other perspectives
Figure 5: The feasible objective region of 3-objective TNI.
(0.0.01..1.))
11:0
(.7
Oy
F
f.
(a) Detailed illustration
(b) Other perspectives
Figure 6: The feasible objective region of 3-objective TN2.
B.2 Proposed Test Problems
We use the proposed test problem generators to obtain scalable MOPs denoted as TNI-TN4, We first specify matrix and vectors:
0, if i
1.2,
=f==2Aj=1
(Vi)g=
(22)
0.8, (i==1vi=3) 3) Aj =,
1, otherwise;
s (1, (l...., 1)T:
if m 3, 22 100, 10000)T; otherwise, s² (1, 100, 10000, 1,
1)T:
if m 3, u' 0.7,,0.7, 1:5):; otherwise, u' 0.7, 1.5,
0.9)T
18

---

Then the test problems are summarized in Table 5 We can find that V1 is obtained by modifying such matrix: an m X m square matrix with zeros on the main diagonal and ones elsewhere. This matrix implies that the PF is inverted unit simplex whose objective vectors on any edge are critical points (e.g., mDTLLZI [48). The modified vertices are the first and the second ones and the modification performs across fi to f3- Consequently, the critical points of f1, f2. and fa are some vertices only. For example, we show the feasible objective region of the 3-objective TNI in Figure 5 Vertices (0, 1.2, T) and (1, 0)T are the only critical points. TN2 is the specification of the studied case in Section 2 More specifically, as illustrated in Figure 6 we can find that the critical point of is unsupported (i.e., there exists convex combinations of objective vectors that dominate the critical point [57). making the PF exhibit a concave shape. Besides, the critical point of fa is distant from all axes and not optimal for any objective. TN3 and TN4 are extended from TNI and TN2 respectively. They have huge magnitude differences between some objective functions.
Table 5: Parameter settings of TN1-TN4.
Problem
Generator
Parameters
Nadir objective vector
TN1 TN3
s s V = V/
1,, 1)T
s u
1,, 1, 1)T
TN3
== 5², V = V1
(1, 120, 10000. 1)T
TN4
2
s u
(1, 100, 15000,
1)T
Figure and Figure also indicate these problems process the WPB. The WPB has evident dominance resistance 23]. That is, the objective vectors of the W PB are usually non non-dominated in the population, especially in many objective cases. The reason that each of them can only improve k (1 < k < m 1) objectives to obtaín an objective vector dominating it. Thus, they are difficult to distinguish from the population. The WPB causes the population to suffer poor convergence and diversity such that the nadir objective vector is hard to estimate. As found in [48). the objective vectors with = on the W PB exhibit severe dominance resistance, even when presenting in 3-objective cases. Unfortunately, how to cope with the W PB is still an open question (58).
19

---

C Runtime
In experiments, our codes rely on the MATLAB-based platform called PlatMMO 159 which is freely available for research purposes (see https: https://githubb Com/BIIK///LLLLEOO Experiments are executed on a computer equipped with two 3.00-GHz Intel Xeon Gold 6248R CPUs (48 cores in total), an NVIDIA T400 GPU, and I 128GB of RAM. We report the runtime for each algorithm on each instance in T DNPE exhibits the shortest runtime, followed by ECR-NSGA-IL BDNE has longer runtime than these two representative algorithms.
We want emphasize the runtime for BDNE strongly depends the implementation (e.g, the chosen solvers). We adopt an effective selection procedure stated in (60), which can facilitate the application of BDNE to various problems. The main loop of BDNE implementation has a time complexity of O (N² (N)( where N is the population size. The specific analysis is provided as follows. The reproduction procedure has a time complexity of O(N). The calculation of governs the complexity of the selection procedure, which has O (N² log])) The adjustment of boundary weight vectors with O (N log ))) is executed periodically. Therefore, The selection procedure governs the overall complexity, and the main loop has the complexity O (N2 log(N)) We can significantly reduce the complexity by using a simple selection procedure or choosing an alternative solver, which deserves further investigation.
Table Comparisons of runtimes among ECR-NSGA-II, DNPE, and BDNE.
Problem
m
ECR-NSGA-II A
DNPE
A
BDNE
3
10.610ms(2)+
11
7.17
14,5
21.610.01
TN1
5
15:610))2(()+
23.4
11.1 +1s
27.9
39 (33)33(33
8
31.2 (2)+
45.5
21.1 21.1 10s76(1)
55.6
76.7 10.90
3
2,2 (2)+
12
7.26403x21)+
14.2
21.5 (3)))
TN2
(2)+
23.4
11.54ama(1)+
28.4
39.9 (0.5+2)))33)
8
32, (2)+
45.9
21.7100:(1)+
56.3
77.9 (333633)
3
(2)
14.2
6.3140251
19.7
(32
TN3
5
17. (2))
26.2
10
33.2
43.9+1m(33
8
35.1
49.7
20.3
64.4
84.7+17733
3
(2)+
13.2
7.02+omt
17.2
24.2+0.0:(3)
TN4
5
18.6
25.5
11.540
32.7
44.1
8
35.9 (2)+
35
21.2
49.7
70.9
3
7.29 (2)
12.8
4.05
16.1
20. (347(())
DTLZ2
5
10.8 40.100 (2)+
25.8
5.43
31.2
36.7+as5:00
8
16.9 (2)x+
53.4
8.62+oa(1)+
61.7
13)
2.8
13.2
6,2610250(1)+
23
mDTLZZ
5
17.9 (2)+
25.2
11 11 (1)+
32.1
(3)
8
(2)+
49.6
21.1407121)+
63.4
14.5+1.1(3)
MaP2
3
12.6
4.3510.s:)1)4
17.5
21.8 21.8 (3)
DTL.75
3
7.75 (2)+
13.6
4.21
17.1
21.31
IMOP4
3
7.73 (2)+
13.5
4.18
17.1
21.3 1103))
IMOP6
3
7.88 (0355))
13.8
4.22
17.4
21.7
3
4.:3+
14.2
4.314o2z:
21.5 (3)))
MP-DMP
5
10.7 40200 (2)+
25.9
5.01 (02ss
31.6
(3)7+
3
7.3 10 (2)+
14.7
4.54102571)+
2221.9533)
ML-DMP
5
12.2 (24)
28.3
7.75
32.8
40.5+32a(3)
RE3-4-7
3
11. (2.4+
13.6
7.28
17.7
254214(3)
CRE5-3-1
5
17.241s9(2)+
30.7
14.7
33.2
47.9
Total +///-
28/0/0
28/0/0
Average rank
2(2)
1(1)
3(3)
20

---

D Potential societal impact
Many real-world problems, such as logistics dispatch, printed-cireuit board assembly, efficient chemical reaction, and Internet of Things service, require simultaneous optimization of multiple conflicting objectives. The nadir objective vector mainly has two strengths in multi-objective optimization: 1) it can normalize the objective space together with the ideal objective vector and 2) it provides a range for decision-maken or algorithms to more easily explore different trade-offs. Our proposed BDNE is good for better nadir objective vector estimation in terms of theoretical guarantee and wide applicability. BDNE can be applied various problems by employing appropriate solvers. Furthermore, the parameter μe, which indicates the tolerance of also be an important component in developing a more user- -er--fiindlly multi-criteria decision system.
makers for trade-off's, could
On the downside, relying solely on the nadir objective vector for decision- decision-making can be risky. Decision-makers should use additional information for more informed and comprehensive decision. Moreover, the leakage of the nadir objective vector might inadvertently expose problem information and user preferences. This particularly troublesome in certain applications where the confidentiality of such information is paramount, indicating need for caution to avoid these situations. In addition, there is no guarantee that the evolutionary algorithm version can approximate the nadir objective vector within a desired timeframe. This might delay decision-making processes or lead to decisions based on incomplete or inadequate information.
21

---

E More Experiments
We conduct more comprchensive empirical study in this section. We omit comparisons with existing exact methods, as they are implemented exclusively on the discrete MOP (where the exact solver is available) and nearly impossible apply other types of MOPs. Nevertheless, will propose the implementation of BDNE for the discrete MOP. Audiences can follow our work at https://gi thub. wwt./ooeeeeeeeeeee comm/Errcchheng124//DDM
E.1 Ablation Studies
We investigate 3 schemes in BDNE, "CFF" denotes the coping strategy for flat fitness (see Section (.2) "TBW" denotes the transformation of the best boundary weight vector (see Step 2 of the upper-level optimization in Section B.3). "BSU" denotes the boundary subproblems using unit vectors as their weight vectors (see the upper-level optimization in Section 3.3).
Table 7 presents the experimental results. Removing CFF or TBW merely does not evidently affect the performance of BDNE. However, the performance deteriorates when both schemes are absent. Particularly, BDNE without CFF and TBW is less effective MOPs with complicated feasible regions, ie., TN2 and TN4. BDNE outperforms BDNE without BSU across most instances, indicating that boundary subproblems using unit vectors important. Overall, the effectiveness of the two strategies is validated.
Table 7: Comparisons of error metric values among variants of BDNE.
Problem
372
w/o CFF
w/o TBW
w/o CFF & TBW
w/o BSU
BDNE
2.5e. 16 10[)
8 16
2.55e. 16
0.0001 (5))
3. 16.50s66
TNI
5.56-05 (U)
0.00277-000664))
0.0132+aamu(5)-
0.00073++00041
0,0208 (3)
0.0192
0.014]=0
0.0398100xx00
0.023120031(4)
1800016-0mmmm (1]=
0000494400mm0033
0.000122 0.00548_0mmm555==
TN2
0.0
0.00624
0.0103
0.0077660m:222)+
0.00803 (3)
0.0351 (5)
0.0308
0.0259 (22)))
0.0287+
20185-o92ed
3,28c-16 15
2,370-16
2.970-66
0.00217 (5)-
2.39c-16
TN3
(2)
0.000568 2nceen
0.000735 (4)=
0.0108_ammx(5)-
0.0192_00um( (3)=
0.0175 (2)=
0.0168 00)
0.0381 0.0381
0.0195 0.0195_o0xa(4)
0.0001 0000044 (2)=
0.00077 =4:00
0.00796-om22(55
4.22-05
TN4
0.00288 (2)=
0.03724
0.00696amm1103)
0.00288+0maa2
0.0253 (3]
20
0.0237_neas<2)=
00268gamm: (4)
10:7e-10
2.49e-10+2.6..00
1.Ne-11=994ee122
2 12
131e:00=222.nn(()
DTTL2
1.49c-10 1.9e-11 =3))=
1.03e
10:11...:00000
1.26e 10
0.000572-ummsd5)
1.68e- 16 10(4)
5,38c- 10+ 10))
4.39c-104399e
000667+225455
0.000282
3.87--10 -.30-
0000s5 (1+
0.00641
0.0062--0z0m1122 (2)=
0.00983 (5)-
0.0658
mDTLZ2
0.00461 0o00mss (2
+.00479++00057((4)
0.00488-000ssll
0.0182+a0z2(55)
0.004++004073))
0.00281 100000
0.00578_0oxxw(4==
0.02822am2s
0,00358
100358_10000002
Mal-2
0.00888 1 (4)=
00008872556-x1111
0.00885_1mmnn33)
0.008 (5)
0.00888 15xoxx
DTLZS
2.78c-15
2.380-33475%-11(4
4.6
4:430-13118--105-
1.43c-13
IMOP4
(166--17+33-111
1.96e-17+74een122
1.12:17-=29%
0.000167-60001155)
4.16e-17+1.h
(n(3)
IMOP6
13
1.09e
(3)
2.16e:07_111..x(4)
15
3.2e 15
0.00778_-mm-- (2)=
0.0077--
0.00781onenr(4)=
(50
(1)
MP-DMP
(401281000002(4)====
0.0127 0.0027
0.017720m0nss(0===
(,0)
0.01274488--
0.016247480003)
00162_000000(5)=====
0.0162=1445.00
0.016248:0.o5(4)
ML-DMP
0,0452--00ss(()m
0.0358 +am())
0.0577+o.us(4)-
0.0822+ai1155m
0.0397
RE3-4-7
0.0090 (40))
0.0775
0.0815
0.0787
CRES-3-1
0.191 (2)
0.191 11 (4))
0.191 (1)=
0.191 (5)
0.191 19
Total t///
2/25/1
1/26/1
2/19/7
2/13/13
Average rank
2.5714(2)
2,607((3)
2.8571(4)
4.4286((5)
2.5357(1)
E.2 Impact of p and Tu
We investigate the impact of parameters in BDNE. Recall that fæ is the user-defined upper bound of the trade-off, and r. denotes the maximum number of iterations involved in the upper-level optimization.
The Pareto-optimal objective vector, situated on the boundary of a convex PF, usually has a substantially higher value of M (see Definition I0) than that in the central region. We test BDNE with
22

---

different settings of on mDTLZ2, since this problem has a convex PF and thus effectively discloses the impact of μ.. We consider 6 values for μ.: 20, 40, 60, 80, and 100. We find that the estimated nadir objective vector is dominated by the exact one on every instance. We introduce another metric, representing the distance between the estimated nadir objective vector and the ideal objective vector.
This metric is defined as E" Di=1 i=ll (( 22 (= =²de))² Figure further illustrate this observation, plotting the means of E and E'. Consistently, the obtained nadir objective vector deviates from the exact nadir objective vector and moves closer to the ideal objective vector, as the value of f decreases. A smaller implies that decision-makers have stricter requirement for preferred solutions, resulting in a smaller set of preferred solutions. Accordingly, the promising region becomes more refined and the estimated nadir objective vector is getting farther away from the exact one.
10
2.5
Mean of E (log)
Mean of Es (log)
10-1
2
1.5
10:2
50
100
20
40
60
80
100
j
(a) E versus
(b) E" versus μ
Figure 7: Results of different settings on mDTLZ2.
Different MOPs have different difficulties in estimating the nadir objective vector. To clearly show the effects of Tu. we employ TN4, which possesses a complicated feasible objective region. Figure plots the results. The value for Tu begins The runtime getting shorter as the value of Tu decreases, which is straightforward. Besides, the relationship between the runtime and Tu is linear. The curve of E versus Tu exhibits declining trend with intermittent fluctuations. Generally, the error is getting smaller (or the accuracy is getting higher) the value of Tu increases. The fluctuations occur because the lower-level optimization algorithm is stochastic (i.e., it does not guarantee the attainment of Pareto- Pareto-optimal solution within a finite number of iterations).
increases by and ends 18, while 77 remains 200.
Mean E (log)
Mean of runtime
60
2
40
30
20
10
10
10
15
Tu
Tu
E T
(b) Runtime versus To
Figure 8: Results of different settings on TN4.
23

---

E.3 Comparison with Other Heuristic Methods
In previous sections, we employ theoretical analysis, illustrative examples, and experimental com- parisons with two representative baseline methods demonstrate the advantage of BDNE over the existing heuristic ones. To more comprehensively validate the effectiveness of BDNE, we present the experimental results comparing method with the remaining heuristic methods in Table g The majority of heuristic methods cannot surpass our method on any instance, while our method significantly outperforms them most instances. Table shows the detailed results of the methods having better performance than BDNE on some instances. Although EP1 achieves lower errors on 9 instances, the gaps are relatively small (A < 0.03). In contrast, BDNE has remarkably better performance than EP1 on many instances. For example, A < -0.3 on TN4 and TN4; A < 1.5 on 5- and 8-objective DTLZ2: A < -22 on 5-objective ML-DMP. For EP4, the better result only appears on 3-objective ML-DMP, and the gap is very small (A < 10 10"4). EP4 shows poor results on the rest of the instances. We can conclude that our method still outperforms other heuristic methods.
Table 8: Overall comparisons of error metric values between other heuristic methods and BDNE.
SF2
SF3
SF4
EPI
EP2
EP3
EP4
EPS
BDNE
Total +/=/- 0/0/28
0/0/28
0/0/28
9/3/16
0/0/28
0/2/26
1/2/25
0/1/27
Average rank 6. 6.6 6.4286(7) 4.4286(3) 2.7143(2) 7. 7.9286(9) 4.6429(5)
4.4643(4) 6.75(8) 1.4643(1)
Table 9: Comparisons of error metric values among EPI, EP4, and BDNE.
Problem
m
EP1
A
BDNE
1.71e- 1.71e-1543.80-1221
-1.39e-15
0.373
-0.373
3.14c +6ooee
TN1
133201712204-1666
0.000273
0.263
-0.263
0.000273 20.0044 (2)
4.44e-174205e1o(0)
0.0221
0.227
-0.205
0.0221 10.033 (2)
004)
-0.333
0.437+t244
-0.437
70000122=0.000s5
TN2
(33
-0.325
0,454 (6)-
-0,446
0.00803 20.0335
0.336 (2)-
-0.318
0.36 0.36
-0.341
0.0185
16 (2))
-4c-16
0.274
-0.274
2.39c-16 16
TN3
5.28c- 1741.76--16
0.000669
0.221 (4):
-0.22
0.000669 _00mmm (2)
4.44e 17 100-10
0.0195
(o175)))
-0,238
0.0195 10195 (2)
o(4)-
-0.333
0.4094aia(6)
-0.409
4.92c-05 5.59
TN4
033
-0.331
0.467 (6))
-0.465
0.00208 0.00 (1)
0.333 4-336-6639--100 (2()
-0.306
0.382+0om744 (4)-
-0.356
0.0268 o.03) (1)
4.55e-12410c
166-111 12
(1)++ (1)+
1.77e-10
1.33e-0621.16--00
-2.33-006
1.81e-10 100-10022300000000
DTLZ2
1.67 L..7+..1800 (7)-
-1.67
o.02247 (3)=
-0.00127
1.68e- 10
10. a..8 (7)-
-2.38
1.0147
-0.0242
3,87e- 107e-10 +5
0.000623 (1)+
0.00596
0.0405
-0.0339
0.00658 0000005
mDTLZ2
0.00155-0.00000 0.000o 1)+
0.00314
0.044 (4)-
-0.0393
0.0047 2000067777
0.00279 (1)
0.000798
+.0387
-0.0352
0.00358
= 0000099
MaF2
0.643
-0.635
0.0147=amus(2)
-0.00577
0.00888
DTLZS
1.23e-10-271e-100
-3.23e-10
0.58210556
-0,582
1.43e-13
IMOP4
8.74c-12 -8.74c-12
0.949 (6)-
-0.949
4.16e-17 1 (1)
IMOP6
5.77c-07 -5.77e-07
0.13 (5)
-0.13
3.2c- 15
3
0.00776=84-00 (1)=
1.13e-05
0.219
-0,211
0.00777
MP-DMP
0.0167 10021(2)
-0.00405
0.849 (6)-
-0.836
0.0127 4.8%
1.21 1.))
-1.19
0.0161
43288-0 (1)+
3.9c-05
0.0162 8.566
ML-DMP
12)941(7)
-12.8
0.547 200867 (2)-
-0.507
0.0397
RE3-4-7
-0.0692
0.616+aour:6)-
-0.537
0.0787
CRE5-3-1
19 (1)
0.000722
1.25 (5)
-1.06
0.191 (2.
Total +///-
9/3/16 2.7143(2)
1/2/25
Average rank
4.4643(4)
1.4643(1)
24

---

E.4 Pilot Studies on Integrating BDNE in Algorithm Iteration
We present BDNE as an independent algorithm this paper. This subsection provides initial investigations about integrating BDNE into the iteration of an algorithm. We select the MOEA to conduct experimental studies and propose two simple implementations. First, we replace the nadir objective vector estimation method of an MOEA with ours and denote the variant as "VI". We define the promising region as the dominating region of the estimated nadir objective vector. Then V1 is further improved by focusing the search within the promising region. Specifically, in the environment selection of each iteration, the objective vector outside the promising region is considered to have a worse fitness value than the one inside. The improved version of V1 is termed "V2". We consider two famous MOEAs: MOEA/D [2] and NSGA-III 32]. The population size of the BDNE is set to 12, whereas the population size of the MOEA is set to 91. The number of function evaluations is consistent with the original settings, i.e., 180,000. The MOEA and its improved versions use the same function evaluation budget. VI or V2 consumes 12 additional function evaluations for nadir objective vector estimation in each iteration, and as result, it uses about 230 fewer iterations than the original MOEA.
The statistical results of the hypervolume metric 6 are reported in Table TO The results of Wilcoxon's 's rank sum test are shown by two symbols in ft, in the cell. The first and second symbols are the comparison results with VI and V2, respectively. We begin by analyzing the comparative results of the MOEA and VI. Both MOEA/D-VI and NSGA-III-VI significantly outperform their original versions, respectively. Besides, MOEA/D-VI exhibits clearly smaller standard deviations compared with its original versions (e.g., 0.0106 versus 0.00289), indicating more stable performance. Analogously, NSGA-III-VI yields stable performance. These results also emphasize that inaccurate nadir objective vector estimation can have a significant impact on algorithm performance. According to the remaining results, V2 of the MOEA has a better performance than VI, indicating the promising region determined by BDNE useful for guiding the search. Furthermore, we find that V2, on average, retains more solutions within the promising region compared with V1. For MOEA/D, 73 versus 83 on TN1, 46 versus 53 on TN2, 70 versus 84 on TN3, and 48 versus 53 on TN4. For NSGA-III, 30 versus 89 on TN1, 25 versus 67 on TN2, 32 versus 88 on TN3, and 25 versus 66 on TN4. This explains the performance improvement and demonstrates the effectiveness of the scheme.
In conclusion, our method shows great potential improve the performance of algorithm.
Table 10: Comparisons of hypervolume metric values between the MOEA and its improved variants.
Problem
MORA/D
VI
V2
NSGA-III
VI
V2
TNI
0.387 (nm
0.398 inoonss (2)-
0.404 1u
0.333 0.333 (3)mw(3)-
0.377 (2))
0.406 nocoon
TN2
0.213
0.227 a0occ
0.226
D. (0060))))))-
0.207 =00000 (2),
4.00 D+)
TN3
0.397 0.397 +.384+anuas))-
(2)-
0.34-ezz1(3-
0.3 0.378-couss
0.405 000000 (I)e)
TN4
0.209 0.20)_0a2)3)-
0.0222))))
0.148 (3))
0.209
0 229 (ie
0004
3/1/1
W113
4/00D
Total +/s/-
0/04
1/03
A
0/04
0/04
Average rank
3(3)
1.75(2)
1,25(1)
3(3)
2(2)
1(1)
E.5
Results on All Problems in the Used Test Suites
In previous experiments, we select the problems with different kinds of feasible objective regions from several test suites to comprehensively compare the algorithms and avoid showing similar results. Specifically, we employ 4 new and 6 existing test problems (28 instances in total), including instances with many objectives (e.g., 5 and 8 objectives cases), weakly Parcto-optimal boundaries (e.g., TN1- TN4 and mDTLZ3), linear PF' (e.g., TNI and TN3), convex PF's (e.g.. mDTLZ3), concave PFs (e.g., TN2, TN4, and DTLZ3), irregular PF's (c.g., TN3, TN4, DTLZS, IMOP4, and IMOP6).
Table IT summarizes the complete results on all the test problems by showing "Total +/=/-" DTLZZ MP-DMP, and ML-DMP are absent in this experiment, as the MaF test suite already covers them. Besides, IMOPI-IMOP? are non-scalable 2-objective MOPs, which are also omitted. We can find that our method outperforms the two representative algorithms on most instances. Ta2 records the detailed results indicating either of the two algorithms statistically outperforms BDNE, and the positive gaps in the table are marked. Most of the positive gaps are lower than 0.02, while the absolute
25

---

values of negative gaps can be very large. Besides, BDNE always ranks second on these instances, exhibiting competitive performance. short, BDNE still shows its superiority on the three test suites.
Table 11:
Overall comparisons of error metric values among ECR-NSGA-II, DNPE, and BDNE on MaF, mDTLZ, and IMOP test suites.
Problem
# instances
EC-NSGA-II
DNPE
BDNE
MaFI-MaF7
21
1/0/20
5/2/14
MaF8- MaF9
6
0/0/6
1/0/5
MaF10-Maris 10-0
12
5/0/7
0/1/11
ADTT1ZI-mDDTL. .24
12
0/0/12
1/2/9
IMOP4-MMOPS
0/0/5
0/1/4
Average rank
2.5893(3)
2.125(2)
1.2857(1)
Table 12: Comparisons of eтror metric values among ECR-NSGA-II, DNPE, and BDNE on the three test suites' instances where either of the two algorithms outperform BDNE.
Problem
ECR-NSGA-II
A
DNPE
A
BDNE
MaFi
8
(3))
-0.2
2.8 16 1)+
0.000149
0.00015
1000050 (2)
MaF2
8
0.275
-0.0805
1.69c-06 (1
0.195
0.195 1 (2)
MaF4
0.00569 #0.010s 1)+
0.000713
0.0127 #0.00022
-0.00627
0.0064 0.00055s
MaF4
1.133403600 (3)-
-0.129
0.00255
0.00012 11)
0.000828
0.00337 4.0000661 (2)
MaF4
-0.364
0.000355 100000 100005550000014(0
0.00126
0.00161
MaF7
0. 0.166102sx71 (3)-
-0,0043
0.0269 120
0.135
0. 0.
MaFI0
0.00669 0s (I)+
0.00674
0.14 (3)-
-0.127
0.0134
MaF10
0.0148 a.. 1)+
0.0154
0.352 1.38e (3)-
-0.322
0.0302 +00033
MaF10
0.0298 0.0298-6628-40 23 ()+
0.0156
0. (3)-
-0.648
0.0454
MaF11
5
0.0165 00 (1)+
0.0103
400277
-0.82
0.0268
MaF11
0.0256 (1+
0.051
10002
-1.56
0.0766100145
mDTL.ZI
71
16)653)-
-711
(100000) 10060o0550000000
9.36e-05
0.0363
0.0364100197(
ML-DMMP
100000 (3)-
-80.7
0.00917
0.0162.1..6e05((
26

---

F Proofs
E1 Properties of Cone Domination Property (Reflexivity). Vu, u A u.
Proof. Since ü; ú, for i 1,..., m, we have A Property 2 (Anti-symmetry). !f u < v, then A
Proof. Since u < V, we have < Thus, v e according to Definition g Property 3 (Transitivity). Ift - and xa v, then t v.
Proof. Since t <20 u and u < v, we have < and ú x v. According to the transitivity of Pareto domination, < V. Therefore, < v.
The three properties imply that cone domination defines a strict partial order.
F.2 Proof of Theorem
Proof. Without loss of generality, we let 2j 0 for I,..., m.
(Sufficiency) Let 2j 2 2 = 0 for at least one j E (1,...,m) m
m} \ (i}- We consider an objective vector
z satisfying z z. We have 2 2x > >
k= 2 and then
m2
(1
m Σ
26 > (1 2)2 +
for every j E (l.....m}.
(23)
m
Consequently,
1 2j = w/}
2 =0 0,
if w 0,
(24)
w/ 3j w) žj. if wf 0.
Since 3j {1...., m] \ {i) such that 27 2 0.
deduce {w)
max 15msm
{w) 13 max 15/5m
27 2 0.
(25)
The dominated objective vector can not be optimal for the boundary subproblem. Therefore, the optimal solution of the boundary subproblem must be Pareto-optimal.
(Necessity) Let z be Pareto-optimal. We suppose that 25 2j for each j {1,..., m) \ {t).
We consider zj- = z + Ej for j = I,..., m where E, 2 0 is a sufficiently small value such that 23 āj
< 2 Then the following equation holds
max (W)) }3} = max (w) },} O. 15
(26)
15
which indicates that z dominated by z" can also be optimal for the boundary subproblem. But this is contradiction.
E3 Proof of Theorem 2
Proof. Without loss of generality, we let 2/ 0 for j 1,..., m. Since z(00 2 2/ for every
j E (l....,m) m] {i), we have
{ W 2000]
wi 2/0" (1+1) 20
max 15i$m
(27)
(Sufficiency) Let z (t) be cone-optimal. We assume that z, rather than z (8) is the optimal objective vector this boundary subproblem. That is,
max 15
{wi 2/} < max
w 20--200 5019
(28)
15
27

---

Since 2 A² x00 and w =(00= O. Eq. (28) implies that =(" & and =/0r" > 2, for all jE \ {i}. Theorem ! signifies is Pareto-optimal, and thus the corresponding objective
(2) function value larger than that of the critical point (i.e., 24 2 21). Based on 2!0) 2 and (0) Zi. have
TN
m
(29)
1=1
f=1
There exists an index 1 A such that 2
<
21. Therefore,
(8)
α
(1)
21
21
24
(30)
m
which means
max IS)sm { (w)
2/} > wi 2(1) = max 15.5m
ww)
2(09
(31)
This conclusion conflicts with the assumption. 20 is optimal for this boundary subproblem. Since can be arbitrary, (0) is also the unique optimal objective vector.
(Necessity) Let (0) uniquely solve the boundary subproblem with
0,
j
w3
B
(32)
j j i.
(1)
2j
We assume that z cone-dominates (0) Then
w) žj w -)
0,
if w = 0,
(33)
w 2j S w =11 if w/ > 0.
Consequently,
max 15j5m
{ w
200 2011 15s5m
max
(34)
indicating that (0) is not uniquely optimal for the boundary subproblem. But this is contradiction.
F44 Proof of Corollary
Proof. Since the index / in Inequality 30 not arbitrary, of should be larger than 2/ for j 1,..,m. m.
F55 Proof of Theorem
We first prove that cone-optimal objective vector is Pareto-optimal. Letting z be cone- optimal objective vector and z E [f(x)|x E R?), we have
Proof.
3k, - a) zn) + m
Σ
2
Zj
< 0.
(35)
Since
1
min (2) - 2q) <
(zj - 27)
(36)
15
j=1
then 3k, 2 < O.
28

---

We now prove that a S (m-1)M++ holds for a cone-optimal objective vector. Given a Pareto-optimal objective vector xt and an objective vector z E {f(x)|x E Q2, to make sure that z" is Pareto-optimal for each Z, the following inequality should hold
min 2j 1515m
2j
-(1 a)
min (23 ssism
2z) + a
2j
(37)
<0.
Since 2j 23 < O, we have
< (m
max 15/5m
(3] 2z)
(38)
j=1
The Definition 10 is equivalent to a properly Pareto-optimal decision vector x* E Q satisfying that
max fx(x*) fz(x) 15/5m
max fz(x) - (x*) S M 1535m
(39)
where x Ω and maxisism
(x) - (x*) > 0. According to Inequalities
38 and 33).
we have
< m 1)a
(m 1)aM
Σ
max sm
(zj - 23) 5
max 15mmm
(3) 23)) (40)
j=1
j=1
Then
(1 a) min
(2) 22) m
2
2j
15i5m
j=1
(41)
(m
1)aM
< (1 ()) max (2j 27)
max 1535m
(z) - 2j)
1555m
m
0.
Since max maxigism(2 (2) 27) > 0, then
1 + (m- 1)aM 50
(42)
1
5
(m 1)M m
E.6 Proof of Corollary 2
If cone-optimal objective vector is not properly Pareto-optimal, a S 0 should hold according to Theorem 3 Therefore, cone-optimal objective vector has finite value of M, indicating it is properly Pareto-optimal. However, a > 0 as shown in Definition g The formal proof is as follows.
Proof. Let z be cone-optimal objective vector. We assume that z" is not properly Pareto-optimal.
Then there exists an objective vector z such that
max 2j
2j
I m
- 00.
(43)
max 2j 2j I575m
Since z" is a Pareto-optimal objective vector, have
m
Σ (2) 23)
(44)
> max (3j - - (m 1) 1535m
(zj 25}
max 15)5m
>0.
29

---

The inequality can be rewritten
o.) min
(zj - zz)
[2) 2n)
isJsm
a
(z) -2z)
171
15m5
max
(45)
a(m 1)
(z) 2j)
max 15J5m
m
>0.
This conclusion conflicts with the optimality z"
Moreover, leveraging Theorem 3 and Corollary 2 we illustrate the relationships among Pareto optimality, proper Pareto optimality, and cone optimality Figure
Pareto optimality
Proper Pareto optimality
Cone optimality
Figure 9: Relationships among Pareto optimality, proper Pareto optimality, and cone optimality.
F.7 Proof of Theorem
The proof is analogous to the sufficiency proof of Theorem 2
Proof. Without loss of generality, we let 27 = 0 for j = 1...., m. According to Theorem 6 we can
let w) 8/2] for every j E {l,...,,. m) \ {i}. Then we have
max {w) 27 B 2 0, 15s5m
(46)
where B is constant.
Suppose that z' yields a lower function value than zt for the boundary subproblem with w That is,
max 15
{ {w) z/} < B,
(47)
and 2" A x' according Theorem every j (1...., m) \ {i). Based on 2 8 and 2 2/, can deduce that
Since n' 4 zz Eq. (47) implies that द < < and 2ÿ 2/ for
m
(48)
j
There exists an index l of such that z
z Therefore,
(49)
which means
8 1
max
ww)
w
// >
(50)
This conclusion conflicts with the assumption.
30

---

F.8 Proof of Corollary 3
Proof. According Theorem B the Pareto- Pareto-optimal objective vector deviating from the user-defined trade-off is cone-dominated by some objective vector. And Theorem !| reports the cone-optimal objective vector that maximizes given objective optimal for at least one boundary subproblem.
F.9 Proof of Theorem
The proof is modified from the sufficiency proof of Theorem
Proof. Without loss of generality, we let 2j = for j = I,.... m. We consider an objective vector satisfying z' < Then we have
(1 - (1-a)zz + a
2k 2 (1
0)2
a
m k=1
m
(51)
for every
j E (1....,m
Consequently,
w/} 2, w) =0 if w/ 0,
(52)
wn 2j 2 w z): if wg O.
Since Aj E {1...., m] \ (i) such that 2 > 0. we can deduce
Ww) 2 max 15ms
max
[w) -2 0.
(53)
15s5m
not be optimal for the boundary subproblem. Therefore, the optimal solution the boundary subproblem must be cone-optimal. According to Corollary Pareto-optimal.
2
the optimal solution is also properly
E.10 Proof of Theorem
6
Proof. Let for = = l,..., m. Suppose that z, rather than z 2" optimal for the subproblem
with w Letting w32 = B for j E {l....,.0 ..... } {i} where 3 >> a constant, we have
w 2j = w 2, = 0, if w = 0, B wj 2, 2 0.
(54)
if w > 0.
Since z" is properly Pareto-optimal according to Theorem we have w > 0,J * We can deduce that 2] > žn for j E (1,...,m,) m) (i). For the subproblem with w we obtain
max 15.5m
{ (w) 2
max (w) } Sm
(55)
which implies z, rather than z", is the optimal objective vector to the boundary subproblem with w This is contradiction.
31

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: This paper proposes a general and rigorous method for nadir objective vector estimation, as demonstrated in the abstract and introduction. paper are summarized the end of the introduction.
The main contributions of this
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
The limitations are summarized in the conclusion (Section
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-specfiiatiinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
32

---

Answer: [Yes]
Justification: The theoretical results are shown in Section 3.1 All proofs are presented in Appendix [F]
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: The implementation details of BDNE are shown in Section 3.3
The experi-
mental setup is detailed in Section 4.1
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
33

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
Our code is available httttp////ggtabo...ooo///ttthhhp
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so No is an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ praips.cc/publicguuu.ee CoodeSumeeieeeeee ssi iessonPolll mollicyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
The full details of experimental settings are available in Section 4.1
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: See Section 4 In this paper, each algorithm is executed 30 times for every instance. The results tables include both the mean and the standard deviation. Wilcoxon's rank sum test is used to confirm the statistical results.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
34

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative rates).
show in tables or
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: See Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't It make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification: We do not propose any dataset and potential societal impacts can be found in Appendix [
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
See Appendix D
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
35

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: See Appendix
Guidelines:
The answer NA means that the paper does use existing assets. The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in package should be provided. For popular datasets, paperswithcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
36

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moodl as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This paper does involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
37


Reviews:
[{"review_id": "szd8VN7LD1", "reviewer": "Reviewer_3RPX", "summary": "This work proposes bilevel optimization problems to align their optimal values with the nadir point.  Some schemes are suggested to address potential flat fitness in upper-level optimization. An algorithm based on evolutionary computation is then proposed for black-box cases.", "questions": "1. Is there evidence of really complicated feasible objective spaces from industrial applications?\n2. The algorithm for the lower-level optimization problem appears to be quite complicated.  Can we consider changing it to a different one?\n3. Can evolutionary algorithms be used in the optimization problems proposed by Gokhan et al. (2015)?\n4. How are the benchmarks chosen in the experiment?\n5. What is the performance if coping strategies for flat fitness are eliminated?\n6. I also wonder about the effects of removing the subproblems with unit vectors.\n7. I recommend providing a more detailed analysis of the deficiencies of the heuristic methods.", "limitations": "This work mentions one limitation: the lack of fine-tuning to a specific problem.  I agree that this is an interesting and important topic for future research.", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This work demonstrates both theoretically and experimentally that the nadir point can be obtained or approximated via newly proposed optimization problems.\n2. Compared to existing optimization problems for finding the nadir point, the proposed problem is more concise and applicable to a broader range of scenarios.\n3. Several schemes are used to cope with the issue of flat fitness in the upper-level problem.", "weaknesses": "1. The algorithm proposed in this paper is an approximation algorithm rather than an exact one.\n2. The algorithm is general. Its performance may be unsatisfactory for some specific problems.\n3. The lower-level optimization problem consists of a series of single-objective subproblems, limiting the applicability of some multi-objective optimization algorithms.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your time and effort in reviewing our work. We are glad to know that you find our method is concise, has broad applicability, and demonstrates its effectiveness theoretically and experimentally.\n\nwe address your concerns as follows.\n\n## W1/W2. BDNE is a general approximate algorithm.\nBDNE can **accurately** determine the nadir objective vector, as long as an exact solver is available. BDNE can achieve **satisfactory** performance for a specific task, as long as a suitable solver is utilized. This paper proposes a general framework applicable to various scenarios, such as multi-objective integer linear programming with available exact solvers, and multi-objective learning utilizing gradient information.\n\nTo demonstrate that BDNE can be a promising exact algorithm, we apply BDNE to the discrete problem and choose an exact solver. We test BDNE on the multi-objective assignment problem (MOAP) and the multi-objective knapsack problem (MOKP). 3 instances are randomly generated for each problem. The following table shows the mean and standard deviation of error metric values. Our method is **accurate**, while the heuristic method misses the nadir objective vector. The superiority is also demonstrated, as shown in Common Concern 2.\n\n|Problem|$m$|$n$|ECR-NSGA-II|DNPE|BDNE|\n|:-------:|:---:|:------------:|:------------:|:--------------:|:----:|\n|MOAP|3|20$\\times$20|0.261±0.103|0.392±0.0828|0|\n||||0.202±0.064|0.419±0.055|0|\n||||0.197±0.0945|0.582±0.0767|0|\n||4|10$\\times$10|0.147±0.0602|0.498±0.0405|0|\n||||0.252±0.0917|1.16±4.52e-16|0|\n||||0.142±0.0659|0.536±2.26e-16|0|\n|MOKP|3|200|0.218±0.0861|3.84±0.0284|0|\n||||0.229±0.0804|4.62±0.0315|0|\n||||0.208±0.084|5.48±0.0346|0|\n||4|50|0.244±0.0957|3.43±0.0586|0|\n||||0.27±0.0743|4.25±0.0587|0|\n||||0.262±0.107|5.08±0.0709|0|\n\n## W3. Applicability of other multi-objective optimization algorithms for lower-level optimization.\nWe would like to clarify that the LLOPs constitute a set of single-objective optimization problems (SOPs) **rather than** an MOP. Therefore, not all multi-objective optimization algorithms are suitable for the lower-level optimization. Nevertheless, these SOPs can be solved sequentially or in parallel. We employ a decomposition-based multi-objective optimization algorithm to collaboratively address these SOPs, thereby enhancing optimization efficiency.\n\n## Q1. Evidence of really complicated feasible objective region.\nReal-world problems usually have many constraints that can result in irregular feasible objective regions. A comprehensive review of these industrial cases is provided in [1,2].\n\n## Q2. Can the complicated lower-level optimization algorithm be changed?\nYes. We can change the selection strategy in this algorithm to reduce the complexity. This is because this algorithm employs an efficient selection strategy as described in [3], which governs the overall complexity. Moreover, the optimizer of LLOPs can be changed to any suitable one according to the task's properties. For example, use other decomposition-based evolutionary algorithm frameworks [4]. Local search (or gradient information, if available) can be employed to facilitate the convergence [5,6]. All single-objective optimizers such as GUROBI and BARON can also be applied to solve the LLOP, as the LLOP is a single-objective optimization problem.\n\n## Q3. Can the method proposed in (Gokhan et al. 2015) adopt the evolutionary algorithm as the solver?\nThis method relies heavily on an exact solver. This method is **time-consuming** and **unreliable** when the evolutionary algorithm is adopted. Specifically, its lower-level optimization problem, including two sequential single-objective optimization problems, exhibits high computational costs. Furthermore, uncertain optimality gaps arise when the evolutionary algorithm is adopted. As a result, the first single-objective optimization problem misleads the subsequent one, thereby presenting significant unreliability in the lower-level optimization process. The pay-off table, which is a key step, also cannot be accurately obtained.\n\nIn contrast, our method does not require the payoff table, and the lower-level optimization problem is an independent single-objective optimization problem.\n\n## Q4. Criteria used to select benchmarks.\nPlease refer to Common Concern 3.\n\n## Q5 \\& Q6. Ablation studies.\nThe experimental results are presented in Table 1 of the one-page PDF. BDNE-V1 denotes BDNE without the coping strategy for flat fitness. BDNE-V2 denotes BDNE removing boundary subproblems with unit vectors. The effectiveness of the two strategies is validated.\n\n## Q7. More detailed analysis of deficiencies of the heuristic methods.\nWe aim to point out that heuristic methods do not guarantee obtaining exact objective vectors. We construct an example $PF$ and then find all heuristic methods can not identify its nadir objective vector. We believe this example is clear and intuitive. Additional analysis is not necessary to support the above claim.\n\n\n## References\n[1] Tanabe et al. An easy-to-use real-world multi-objective optimization problem suite. Applied Soft Computing, 2020.\n\n[2] Kumar et al. A benchmark-suite of real-world constrained multi-objective optimization problems and some baseline results. Swarm and Evolutionary Computation, 2021.\n\n[3] Zheng et al. A generalized scalarization method for evolutionary multi-objective optimization. AAAI, 2023.\n\n[4] Ke Li. A survey of decomposition-based evolutionary multi-objective optimization: Part I-past and future. arXiv preprint, 2024.\n\n[5] Lara et al. HCS: A new local search strategy for memetic multiobjective evolutionary algorithms. TEVC, 2010.\n\n[6] Lapucci et al. A memetic procedure for global multi-objective optimization. MPC, 2023.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ZOhODIKXM4", "reviewer": "Reviewer_NNkD", "summary": "This paper looks at the problem of finding the nadir objective vector in multi-objective optimization problems, which is important for both optimization and decision-making. This work first analyzes the drawbacks of existing techniques, and then proposes a new method for nadir objective vector estimation using bilevel optimization and a multi-objective evolutionary approach. Experimental results show that the proposed method can achieve good performance in several test examples.", "questions": "Refer to the above comments.", "limitations": "The discussion in the conclusion section is comprehensive enough.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "This paper is very well written. As far as I can tell, the problem discussed in the paper is important for multi-objective optimization. \n\nThe analysis of existing methods is convincing. Particularly, the paper gives a clear example of poor estimation of the vector by existing heuristic techniques. The proposed method has theoretical guarantees and can be applied to a wide range of problems. The effectiveness of this method is also verified experimentally.", "weaknesses": "I do not find any obvious weakness, but I have the following questions:\n\n1. Two different evolutionary algorithms are used to solve the upper- and lower-level problems respectively. Why is CMA-ES used for the optimization of upper-level problems but not for lower-level problems?\n\n2. How should one select a value for the parameter mu in BDNE?\n\n3. Suppose I select a relatively small value of mu and obtain a point consisting of the optimal values of bilevel optimization problems. Does this mean that in the area where the objective vectors do not dominate the point, there are no Pareto optimal objective vectors with a minimum M value less than mu?\n\n3. I notice that the error on CRE5-3-1 is large (about 20%). Please explain this.\n\n4. Why are algorithms only tested on continuous problems?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your time and effort in reviewing our work. We are glad to know that you find this work is important and well-written, the analysis of existing methods is convincing, and our method has wide applicability.\n\nwe address your concerns as follows.\n\n## Q1. Why is CMA-ES used for the optimization of upper-level problems but not for lower-level problems?\nWe utilize CMA-ES as the optimizer for ULOP for two reasons. First, CMA-ES is a state-of-the-art algorithm for single-objective black-box optimization. Second, optimal solutions to the LLOPs are not always available; instead, approximate solutions are often obtained. Consequently, the function values of the approximate solutions may exhibit noise. CMA-ES is suitable for this task as it demonstrates strong robustness in optimizing noisy functions [1].\n\nCMA-ES can be used to solve the LLOP since the LLOP is a single-objective optimization problem. We utilize an MOEA to cooperatively solve the LLOPs. This is because the superiority of MOEAs is demonstrated empirically and theoretically in solving multi-objective black-box optimization problems [2,3].\n\n## Q2. Criteria of setting $\\mu$.\n$\\mu>0$ is a user-defined parameter, indicating a bounded trade-off preferred by decision-makers. Once $\\mu$ is determined, $\\alpha$ in Eq. (3) can be calculated (see Lines 155-162). If the preferences of decision-makers are not available, $\\mu$ can be set to a reasonably large value. In the experimental studies, we demonstrate that BDNE with $\\mu=100$ can have an overall good performance. \n\n## Q3. A small value of $\\mu$: Suppose I select a relatively small value of $\\mu$ and obtain a point consisting of the optimal values of bilevel optimization problems. Does this mean that in the area where the objective vectors do not dominate the point, there are no Pareto optimal objective vectors with a minimum $M$ value less than $\\mu$?\nYes. That is, the Pareto-optimal solution does not address the user-defined trade-off $\\mu$ if it does not dominate the point constructed by the optimal values of BLOPs. The optimal solution of the $i$-th BLOP has the largest value of the $i$-th objective function among all the solutions addressing the trade-off. The conclusion can be deduced by Theorems 2 and 3. A satisfactory pseudo-nadir objective vector can be obtained if the decision-makers prefer a relatively small value of $\\mu$. This preference-compatible property enables our method to have greater application potential. We will add the new claims and their proofs to the revised version.\n\n## Q4. Large error on CRE5-3-1.\nThank you for the careful review. The $PF$ of CRE5-3-1 is unknown and represented by the non-dominated objective vector set provided in [4]. The approximate $PF$ may be the reason for the large error since the results of DNPE and BDNE are similar.\n\n## Q5. Why are algorithms only tested on continuous problems?\nWe test BDNE on the discrete problem and choose an exact solver. Compared with exact methods, BDNE still has a superior performance in terms of runtime (please refer to Common Concern 2).\n\n## References\n[1] Nikolaus Hansen. The CMA evolution strategy: A tutorial. arXiv preprint, 2016.\n\n[2] Zhang et al. MOEA/D: A multiobjective evolutionary algorithm based on decomposition. TEVC, 2007.\n\n[3] Dang et al. Crossover can guarantee exponential speed-ups in evolutionary multi-objective optimisation. AIJ, 2024.\n\n[4] Tanabe et al. An easy-to-use real-world multi-objective optimization problem suite. Applied Soft Computing, 2020.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "r72aQyimzJ", "reviewer": "Reviewer_wp71", "summary": "The authors model the task of computing the nadir objective vector as several bilevel optimization problems.  A corresponding algorithm named BDNE is designed to estimate the nadir objective vector for black-box multi-objective optimization problems.  BDNE scalarizes a multiobjective optimization problem into a set of boundary subproblems.  By utilizing bilevel optimization on the boundary subproblems, the nadir objective vector is identified.  To demonstrate the performance, the new approach is applied to some benchmark problems and real-world problems.", "questions": "1. Why fix m boundary weight vectors as unit vectors?  Can they change after some iterations?\n2. The setting of mu should have a further discussion.\n3. What increases the computational cost of BDNE?  The computational complexity of BDNE should be analyzed.\n4. What advantages does this method have compared to existing exact algorithms when applied to discrete problems?", "limitations": "The longer runtime of the proposed algorithm might also be a limitation that is not thoroughly discussed in the paper.", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The authors introduce bilevel optimization problems, theoretically ensuring that the nadir objective vector is solved.  Although the corresponding algorithm is an approximation algorithm, experimental results show that it can significantly outperform existing heuristic methods.  Moreover, the article is reasonably well organized.  The examples are detailed clearly, as is the new approach.", "weaknesses": "1. The nadir objective vector estimation is just part of the process of solving the original multi-objective optimization problem.  The development of BDNE may be not highly significant.\n2. m boundary weight vectors remain unchanged throughout.  It may waste the computational resources.\n3. Solving the original problem creates a new optimization problem, potentially increasing complexity.  And BDNE does require a longer runtime than the compared algorithms.\n4. The illustration of setting mu is a bit preliminary.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your time and effort in reviewing our work. We are glad to know that you find this work is well organized, the analysis of existing methods is detailed and clear, and our method is demonstrated theoretically and experimentally.\n\nwe address your concerns as follows.\n\n## W1. Significance of BDNE.\nThe nadir objective vector is an essential component of several fundamental operations (e.g., normalization, interaction, and guided search) in multi-objective optimization. In many engineering problems, the nadir objective vector has already been utilized to facilitate optimization [1,2,3].\n\nDespite the introduction of many exact and heuristic methods, a unified paradigm to estimate the nadir objective vector remains absent. Our method is **the first one with theoretical guarantees and general applicability** in multi-objective optimization. Our method can be applied to various scenarios by employing appropriate solvers. Furthermore, the trade-off can be easily determined by decision-makers via setting a parameter.\n\n## W2/Q1. Unchanged boundary subproblems waste computational resources. Can they change after some iterations?\nThese unchanged boundary subproblems use the unit vectors as their weight vectors. They motivate the search for the ideal objective vector, which serves as $\\mathbf{z}^{r1}$. Besides, it enhances population diversity when the adjustable boundary subproblems become similar. In Table 1 of the one-page PDF, BDNE-V2 denotes BDNE removing boundary subproblems with unit vectors. We can find that BDNE outperforms BDNE-V2 across most instances. The effectiveness of these subproblems is demonstrated empirically.\n\nChanging these subproblems after some iterations is an interesting idea. Further investigations will be conducted to explore this.\n\n## W3/Q3. Longer runtime.\nThe runtime for BDNE strongly depends on the implementation. The main loop of our implementation has a time complexity of $O\\left(N^2\\log(N)\\right)$ where $N$ is the population size. The specific analysis is provided as follows. The reproduction procedure has a time complexity of $O(N)$. The calculation of $\\mathbf{r}$ governs the complexity of the selection procedure, which has $O\\left(N^2\\log(N)\\right)$. The adjustment of boundary weight vectors with $O\\left(N\\log\\left(\\frac{N}{m}\\right)\\right)$ is executed periodically. Therefore, **The selection procedure governs the overall complexity**. The main loop has the complexity $O\\left(N^2\\log(N)\\right)$. We will include the computational complexity analysis in the revised version.\n\nWe use an effective selection procedure stated in [4], which can facilitate the application of BDNE to various problems. We can significantly reduce the complexity by using a **simple selection procedure** or choosing an **alternative solver**, which deserves further investigation.\n\n## W4/Q2. Criteria of setting $\\mu$.\n$\\mu>0$ is a user-defined parameter, indicating a bounded trade-off preferred by decision-makers. Once $\\mu$ is determined, $\\alpha$ in Eq. (3) can be calculated (see Lines 155-162). If the preferences of decision-makers are not available, $\\mu$ can be set to a reasonably large value. In the experimental studies, we demonstrate that BDNE with $\\mu=100$ can have an overall good performance. We will improve the clarity in the revised paper.\n\n## Q4. BDNE versus exact methods on discrete problems.\nA comparison of our methods to existing exact methods is summarized in the following table. The exact method involves a more complicated optimization task, which includes more single-objective optimization problems or slack variables. Some exact methods require the variable to be discrete. Moreover, existing exact methods do not accommodate a user-defined trade-off.\n\n|    Method   | Number of single-objective optimization problems | Number of slack variables | Discrete variable | User-defined trade-off |\n|:-----------:|:------------------------------------------------:|:-------------------------:|:-----------------:|:---------------------------------------:|\n|    KS [5]    |                         2                        |            Null           |    Unnecessary    |               Incompatible              |\n|    KL [6]    |                         2                        |         Increasing        |     Necessary     |               Incompatible              |\n|   FD&IS [7]  |                         2                        |         Increasing        |     Necessary     |               Incompatible              |\n| BDNE (ours) |                         1                        |            Null           |    Unnecessary    |                Compatible               |\n\nWe choose an exact solver for BDNE to validate its effectiveness empirically. BDNE has a leading performance in terms of runtime (please refer to Common Concern 2).\n\n## References\n[1] Weerasuriy et al. Performance evaluation of population-based metaheuristic algorithms and decision-making for multi-objective optimization of building design. Building and Environment, 2021.\n\n[2] Mena et al. Multi-objective two-stage stochastic unit commitment model for wind-integrated power systems: A compromise programming approach. International Journal of Electrical Power \\& Energy Systems, 2023.\n\n[3] Ekhtiari et al. Optimizing the dam site selection problem considering sustainability indicators and uncertainty: An integrated decision-making approach. Journal of Cleaner Production, 2023.\n\n[4] Zheng et al. A generalized scalarization method for evolutionary multi-objective optimization. AAAI, 2023.\n\n[5] Kirlik et al. Computing the nadir point for multiobjective discrete optimization problems. Journal of Global Optimization, 2015.\n\n[6] Köksalan et al. Finding nadir points in multi-objective integer programs. Journal of Global Optimization, 2015.\n\n[7] Özpeynirci et al. On nadir points of multiobjective integer programming problems. Journal of Global Optimization, 2017.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "s3AWdFBmhF", "reviewer": "Reviewer_2guY", "summary": "This paper proposes a nadir point estimation method for evolutionary multi-objective optimization, named BDNE. BDNE decomposes the MOP into boundary subproblems and uses a bilevel architecture to optimize them. Theoretical analysis and empirical results demonstrate the effectiveness of the proposed method.", "questions": "Please refer to *Weaknesses*.", "limitations": "No concerns.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "This paper studies a problem: nadir point specification. A method based on decomposition is proposed, which is different from the past approaches. Some mathematical properties of the proposed decomposition method are demonstrated. An empirical study is conducted to highlight the effectiveness of the proposed method.", "weaknesses": "Generally, this paper is not well written, and the empirical study is not well organized.\n\n## Presentation\nI believe that interested readers can easily follow the authors' reasoning from the Abstract to Section 2, and the research background of this paper is also explained very clearly. However, starting from Section 3, it becomes very confusing. In Section 3.1, the authors introduce the boundary subproblem (Eq. 3) without providing any motivation for doing so. Although the authors title Section 2 as Motivation, I feel it actually serves as Related Work because this part only summarizes some previous work and does not touch on how the authors are thinking about this problem from a new perspective. After Eq. 3, the authors propose a new dominance relation and its three properties. I am very curious why the authors emphasize these three properties, as they do not seem to be used later in the paper. Subsequently, the authors present some theorems but do not sufficiently explain the relationship between these theorems and the new method proposed in this paper. In Section 3.2, the authors use a new boundary subproblem (Eq. 9) instead of Eq. 3 discussed in Section 3.1, which makes it unclear whether these mathematical properties in Section 3.1 are related to the proposed BDNE algorithm. Additionally, these properties only hold under very ideal assumptions (L128-L130).\n\nMoreover, I suggest that the authors use some illustrations when introducing these new concepts, such as the boundary subproblem and cone-domination, to better help readers understand these concepts. Additionally, it would be worthwhile to explain the motivation behind them. Another area for improvement is the tables in the paper. The authors have recorded the experimental data of the baseline and BDNE in separate tables (Table 3 and Table 4), which makes it difficult for readers to compare the numbers. The authors could merge these two tables into one, making the data comparison more intuitive. Tables 7-9 have the same issue.\n\n## Experiment\nThe empirical study of this paper does not adequately demonstrate the significance of BDNE in MOO. The experiments only show that BDNE can determine the nadir point more accurately than the baseline. However, I believe that many readers are more interested in the significance of an accurate nadir point for MOAs, such as whether it can improve the algorithm's convergence ability or enhance the diversity of the solution set. Currently, most MOAs do not have an independent mechanism to determine the nadir point, so now there might not have been a consensus in the MOO field on the necessity and significance of such an independent algorithm that is designed just to get the nadir point. Therefore, this paper is expected to demonstrate this clearly. For instance, the authors mention that the nadir point can be used for normalization, but normalization may not require a very accurate estimate of the nadir point. A rough estimation usually works as well. Many algorithms do not even have a normalization process. In practical applications, the scales of different objectives can be adjusted manually. In summary, I believe that the contribution of this paper to the field of MOO is limited and the authors did not adequately demonstrate its practical value.\n\nHere are some minor remarks for the experiment part:\n* What criteria were used to select these test problems? These test problems seem to be chosen arbitrarily or selected based on benchmark results after the fact.\n* In the experiments, 180,000 FEs were used just to find the nadir point. Isn't this too many? Current SOTA MOAs generally require less than 50,000 FEs to obtain a well-converged and uniformly distributed solution set for these test problems.\n* Why do some test problems have 3, 5, and 8 objectives, while some only have 3 objectives, e.g., both MaF2 and DTLZ5 can be configured with any number of objective functions, but they only have 3 objectives in the experiment.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your time and effort in reviewing our work. We are glad to know that you find our method is novel and has theoretical guarantees.\n\nWe address your concerns as follows.\n\n## W1. Presentation.\n**Transition from Section 2 to Section 3.**\nThank you for raising this concern. It is better to choose ``Related Works'' as the title of Section 2. We will also include transitional statements at the beginning of Section 3.\n\n**Role of properties.**\nThe three properties imply that cone domination defines a strict partial order. These properties are not utilized subsequently. We apologize for the implicit statement and will simplify the description based on your response. \n\n**Relationship between theorems and the new method.**\nWe believe the relationship is clearly stated. Each theorem is associated with a corresponding explanation or utilized in a specific context. We may improve clarity by providing a summary.\n\nTheorems 1 and 2 are primary theoretical foundations for employing BDNE to determine the nadir objective vector. The user-friendly parameter $\\mu$ in BDNE is proposed based on Theorem 3. Theorem 5 is instrumental in some strategies of BDNE (e.g., the coping strategy for flat fitness). Theorem 4 extends Theorem 1. While it is not directly related to BDNE, it is crucial for proving Theorem 5.\n\n**Illustrations of new concepts.**\nThank you for the suggestion. We will show the level surfaces of boundary subproblems and their optimal solutions on an example $PF$ (see Figure 1 of the one-page PDF). Cone domination and proper Pareto optimality are not new concepts. We have cited relevant studies in our paper.\n\n**Motivation behind mentioning concepts.**\nCone domination has a strong connection with the boundary subproblem as reported in Theorem 2, which is the motivation for mentioning this concept. Proper Pareto optimality is introduced to replace the obscure parameter (i.e., $\\alpha$) with an easy-to-understand one (i.e., $\\mu$). We will improve the clarity in the revised paper.\n\n**Tables.**\nThank you for the suggestion. We will present the results in one table. An example is Table 1 of the one-page PDF.\n\n## W2. Significance of the accurate nadir objective vector.\nWe agree with you that normalization may not require an exact nadir objective vector. However, an accurate nadir objective vector is important in many scenarios and many exact methods are proposed in [1,2]. We list some consequences of inaccurate estimation of the nadir objective vector as follows:\n\n* Inaccurate nadir objective vectors **degrade** the performance of exact algorithms [3], evolutionary algorithms [4], and multi-objective learning [5].\n* An accurate nadir objective vector is often the **assumption** of interactive algorithms [6,7]. Inaccurate nadir objective vectors may cause biased decisions.\n\nExisting exact methods have limitations in applicability (e.g., continuous problems). Heuristic methods only perform well on manually designed benchmark problems since they often have simple feasible objective regions [4,8,9]. Real-world problems usually have irregular feasible objective regions, making their nadir objective vectors difficult to estimate [10,11]. Therefore, we propose BDNE, which is **the first method with theoretical guarantees and general applicability** in multi-objective optimization. Our method can easily adopt various solvers for different tasks and achieve a trade-off between runtime and accuracy.\n\n## Q1. Eq. (3) versus Eq. (9).\nThe mathematical properties of Eq. (3) remain valid for Eq. (9). The solutions associated with the critical points are invariant after the normalization (i.e., scaling and translation), which is straightforward. We further explain the reasonability behind this conversion in Lines 185-188. \n\n## Q2. Ideal assumptions in Lines 128-130.\nThe statements in Lines 128-130 refer to an ideal method, **not** ideal assumptions. This ideal method aims to demonstrate the preliminary feasibility of boundary decomposition in identifying the nadir objective vector. It motivates us to propose the BLOP, which is a practical optimization task.\n\n## Q3. Criteria used to select test problems.\nPlease refer to Common Concern 3.\n\n## Q4. Too many function evaluations.\nOur method can achieve a trade-off between runtime and accuracy. We aim to ensure the algorithm converges sufficiently, validating our theoretical claims empirically. Consequently, we allocate a large number of function evaluations for each algorithm.\n\n## Q5. Results on scalable problems with 3, 5, and 8 objectives.\nOur theoretical results hold for any number of objectives. You can refer to Common Concern 3 for an explanation and the supplementary experiments.\n\n## References\n\n[1] Computing the nadir point for multiobjective discrete optimization problems. Journal of Global Optimization, 2015.\n\n[2] On nadir points of multiobjective integer programming problems. Journal of Global Optimization, 2017.\n\n[3] New $\\epsilon$-constraint methods for multi-objective integer linear programming: A Pareto front representation approach. EJOR, 2023.\n\n[4] A new two-stage evolutionary algorithm for many-objective optimization. TEVC, 2019.\n\n[5] Hypervolume maximization: A geometric view of Pareto set learning. NeurIPS, 2023.\n\n[6] Multiobjective optimization: Interactive and evolutionary approaches. 2008.\n\n[7] A mini-review on preference modeling and articulation in multi-objective optimization: current status and challenges. Complex \\& Intelligent Systems, 2017.\n\n[8] Regular Pareto front shape is not realistic. CEC, 2019.\n\n[9] A survey of normalization methods in multiobjective evolutionary algorithms. TEVC, 2021.\n\n[10] An easy-to-use real-world multi-objective optimization problem suite. Applied Soft Computing, 2020.\n\n[11] A benchmark-suite of real-world constrained multi-objective optimization problems and some baseline results. Swarm and Evolutionary Computation, 2021.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
Dear AC and Reviewers,

We would like to thank you for the insightful comments and feedback on our paper. Overall, the reviewers agree that this work is important (NNkD) and well-written (NNkD, wp71), the analysis of existing methods is convincing (NNkD) /clear (wp71), the proposed method is concise (3RPX) /novel (2guY) and has broad applicability (3RPX, NNkD).

We address some common concerns raised by different reviewers in this response.

## C1. Significance (wp71, 2guY).
**Nadir objective vector.**
The nadir objective vector is a fundamental concept of multi-objective optimization, and it has been widely used in many multi-objective optimization methods (not only heuristic but also exact methods)'s operations, such as normalization, interaction, and guided search. There have been many studies demonstrating the importance of accurate estimation of the nadir objective vector [1,2,3] and its effectiveness in facilitating the optimization of real-world problems [4,5,6].

**BDNE.**
Heuristic methods do not have theoretical guarantees, while exact methods have limitations in applicability. Therefore, we propose BDNE, which is **the first method with theoretical guarantees and general applicability** in multi-objective optimization. Our method can easily adopt various solvers for different tasks and achieve a trade-off between runtime and accuracy. Furthermore, the trade-off can be easily determined by decision-makers via setting a parameter.


## C2. BDNE adopts an exact solver for discrete problems (3RPX, NNkD, wp71).
To demonstrate that BDNE can be competitive on other problems, we apply BDNE to the discrete problem and choose an exact solver. We test BDNE on the multi-objective assignment problem (MOAP) and the multi-objective knapsack problem (MOKP). 3 instances are randomly generated for each problem. The runtimes in seconds are shown in the following table. "TO" represents timeout. Compared with existing exact methods, BDNE still demonstrates superior performance in terms of runtime.

|Problem|$m$|$n$|KS [7]|KL [8]|FD&IS [9]|BDNE|
|:-------:|:---:|:------------:|:----:|:----:|:-----:|:-------:|
|MOAP|3|20$\times$20|340|4375|687|**222**|
||||405|1249|1471|**183**|
||||394|1214|915|**182**|
||4|10$\times$10|4279|575|TO|**212**|
||||8028|1189|TO|**273**|
||||4724|431|TO|**160**|
|MOKP|3|200|1703|270|826|**166**|
||||1976|77|238|**62**|
||||1500|131|283|**92**|
||4|50|1562|28|10211|**24**|
||||1106|53|14256|**36**|
||||412|21|3013|**15**|


## C3. Criteria used to select benchmarks (3RPX, 2guY).
Since some benchmark problems are designed too specially (e.g., triangle-like $PF$), they cannot reflect the difficulty for estimating the nadir objective vector of real-world problems. Therefore, the problems with complicated feasible objective regions are used in our experimental study. To comprehensively compare the algorithms and avoid showing similar results, we select the problems with different kinds of feasible objective regions from several test suites. Specifically, we employ 4 new and 6 existing test problems (28 instances in total), including instances with many objectives (e.g., 5 and 8 objectives cases), weakly Pareto-optimal boundaries (e.g., TN1-TN4 and mDTLZ3), linear $PF$s (e.g., TN1 and TN3), convex $PF$s (e.g., mDTLZ3), concave $PF$s (e.g., TN2, TN4, and DTLZ3), irregular $PF$s (e.g., TN3, TN4, DTLZ5, IMOP4, and IMOP6).

The following table summarizes the complete results on all the test problems by showing "Total +/=/-". "+", "=" or "-" denotes that the performance of the corresponding algorithm is statistically better than, similar to, or worse than that of BDNE based on Wilcoxon's rank sum test at 0.05 significant level. DTLZ, MP-DMP, and ML-DMP are not used in our experimental study, as the MaF test suite already covers them. We can find that our method still outperforms the other algorithms on most instances.

|Problem|# instances|EC-NSGA-II|DNPE|BDNE|
|:-------------:|:-----------:|:----------:|:--------:|:---------:|
|MaF1-MaF7|21|1/0/20|5/2/14| \ |
|MaF8-MaF9|6|0/0/6|1/0/5| \ |
|MaF10-MaF13|12|5/0/7|0/1/11| \ |
|mDTLZ1-mDTLZ4|12|0/0/12|1/2/9|\  |
|IMOP4-IMOP8|5|0/0/5|0/1/4| \ |
|Average rank||2.5893(3)|2.125(2)|1.2857(1)|


##
Best Regards,
Paper13080 Authors


## References
[1] Mesquita-Cunha et al. New $\epsilon$-constraint methods for multi-objective integer linear programming: A Pareto front representation approach. EJOR, 2023.

[2] Zhang et al. Hypervolume maximization: A geometric view of Pareto set learning. NeurIPS, 2023.

[3] Branke et al. Multiobjective optimization: Interactive and evolutionary approaches. 2008.

[4] Weerasuriy et al. Performance evaluation of population-based metaheuristic algorithms and decision-making for multi-objective optimization of building design. Building and Environment, 2021.

[5] Mena et al. Multi-objective two-stage stochastic unit commitment model for wind-integrated power systems: A compromise programming approach. International Journal of Electrical Power \& Energy Systems, 2023.

[6] Ekhtiari et al. Optimizing the dam site selection problem considering sustainability indicators and uncertainty: An integrated decision-making approach. Journal of Cleaner Production, 2023.

[7] Kirlik et al. Computing the nadir point for multiobjective discrete optimization problems. Journal of Global Optimization, 2015.

[8] Köksalan et al. Finding nadir points in multi-objective integer programs. Journal of Global Optimization, 2015.

[9] Özpeynirci et al. On nadir points of multiobjective integer programming problems. Journal of Global Optimization, 2017.

Meta-review: This paper proposes a method for nadir objective vector estimation in multi-objective optimization based on the formulation of bilevel optimization. The experimental evaluation, including real-world problems, demonstrates the effectiveness and potential of the proposed method.

This paper treats an important problem and is well-written. The theoretical discussion is one of the strengths of this paper. All reviewers' scores are Accept or Weak Accept, and they recognize the novelty and effectiveness of the proposed method. Because the reviewers' opinions are consistent, I would recommend accepting this paper.
Decision: Accept (poster)