Boundary Decomposition for Nadir Objective Vector Estimation

Authors: ruihao  zheng
zhenkun  wang
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 02:57:20

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.

Main paper: 
 introduction: 
 The multi-objective optimization problem (MOP) can be written as min. f (x) = (f 1 (x), . . . , f m (x)) ⊺ , s.t. x ∈ Ω,where x = (x 1 , . . . , x n ) ⊺ is the decision vector (also called solution), and Ω ⊂ R n denotes the feasible region. f : R n → R m is composed of m objective functions, and f (x) is the objective vector corresponding to x. Definition 1. Given two vectors u, v ∈ R m , u is said to dominate v (denoted as u ≺ v), if and only if u i ≤ v i for every i ∈ {1, . . . , m} and u j < v j for at least one j ∈ {1, . . . , m}. Definition 2. A decision vector x * and the corresponding objective vector f (x * ) are Pareto-optimal, if there is no x ∈ Ω such that f (x) dominates f (x * ) according to Definition 1. Definition 3. A decision vector x * ∈ Ω and the corresponding objective vector f (x * ) are weakly Pareto-optimal, if there does not exist another decision vector x ∈ Ω such that f i (x) < f i (x * ) for all i = 1, . . . , m. Definition 4. The set of all Pareto-optimal solutions is called the Pareto set (denoted as P S), and the set of all Pareto-optimal objective vectors is called the Pareto front (denoted as P F ). Definition 5. The relative complement of the P F in the set of all weakly Pareto-optimal objective vectors is called the weakly Pareto-optimal boundary (denoted as W P B).Definition 6. The ideal objective vector z ide is composed of the lower bounds of the P F , i.e., z ide i = min x∈P S f i (x) for i = 1, . . . , m. The nadir objective vector z nad consists of the upper bounds of the P F , i.e., z nad i = max x∈P S f i (x) for i = 1, . . . , m. Definition 7. For the i-th objective function f i with i ∈ {1, . . . , m}, an objective vector z (i) c is called the critical point of f i if it is Pareto-optimal and has the worst f i value, i.e., z (i) c ∈ {f (x)|x = arg max x∈P S f i (x)}. The nadir objective vector is often determined by obtaining the critical point on each objective, since z nad i = z (i) c i for each i ∈ {1, . . . , m}.The nadir objective vector is a fundamental concept of multi-objective optimization and has been widely applied to real-world problems [1, 2, 3] . 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 [4, 5] 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 offers a comprehensive view of the P F for decision-makers, which can facilitate the application of preference-based algorithms [11, 12, 2] . For example, an accurate nadir objective vector is the assumption of many interactive algorithms. A poor approximation may cause biased decisions. In addition, the nadir objective vector and the ideal objective vector are widely used to normalize the objective space [13] . Normalization with an inappropriately estimated nadir objective vector can cause performance deterioration of the optimization algorithm [14, 15] .The ideal objective vector can be acquired by minimizing each objective separately. Unfortunately, obtaining the nadir objective vector is much more complicated [16, 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 on simple MOPs. For example, DTLZ1 has an equilateral-triangle-shaped P F , and its nadir objective vector can be easily estimated using several heuristic methods [9] . However, when the MOP possesses a complicated feasible objective region (e.g., an irregular P F and the W P B), all heuristic methods fail to approximate the nadir objective vector accurately.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 blackbox 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 a particular boundary subproblem under mild conditions (i.e., the critical point satisfies proper Pareto optimality). We also prove that the optimal solution to 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 comparing the optimal solutions of boundary subproblems. The upper-level optimization seeks each objective'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.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. The main contributions of this paper are summarized at the end of the introduction.Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the 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 or 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. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
related works: 
 Existing nadir objective vector estimation methods can be divided into two categories: 1) exact methods and 2) heuristic methods.Exact Method. Exact methods are all designed for discrete MOPs and cannot be applied to other problems. For example, the methods in [18, 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] . m bilevel optimization problems are 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 followsEQUATIONwhere S is an iteratively improved solution set. S can be specified as the population of the multiobjective evolutionary algorithm (MOEA) [22] (denoted as SF1). When the population is the P S, 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 P S. However, this is almost impossible because retaining inferior solutions, such as weakly Pareto-optimal or dominance-resistant ones, in the population is often inevitable [23] . 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 2b and Figure 2f (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 can be obtained by identifying extreme points in the population. In [27, 28, 29] , 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 or 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., L 2 [31] and L ∞ [32] ), the perpendicular distance [33] , and the cosine similarity [9] . In [34] , each objective is associated with a single-objective 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 4 and Table 4 that all methods incorrectly estimate the critical points as well as the nadir objective vector.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 5).Guidelines:• The answer NA means that the paper has no 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 (e.g., independence assumptions, noiseless settings, model well-specification, 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 on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a 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, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to 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 fairness. • 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 acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
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 an integer as opposed to [18, 19] and involves simpler optimization tasks compared to [21] . Our method also enables finding the nadir objective vector, unlike heuristic methods. Furthermore, our method supports using a user-defined trade-off. In the following, we begin by introducing boundary decomposition and establishing its theoretical foundations. After that, we develop a 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.We define a boundary subproblem for the i-th objective asEQUATIONwhere w i is called the boundary weight vector of the i-th objective, z r is a reference point, and 0 < α < 1. w i satisfies three conditions: 1) w i i = 0; 2) ∀j ∈ {1, . . . , m}, w i j ≥ 0; 3) ∃ j ∈ {1, . . . , m}, w i j > 0. The definition of the boundary subproblem is inspired by the modified weighted Tchebycheff metric [35] . The contour surface of the boundary subproblem is illustrated in Figure 1 . 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. Definition 8 (From [36] ). Let z be the image of an objective vector z, whereEQUATION)Given a value of α and two objective vectors u and v, u is said to cone-dominate v (denoted as u ≺ c v) if and only if ũ ≺ ṽ.Definition 9. Given a value of α, an objective vector is cone-optimal if no objective vector can cone-dominate it.Theorem 1. The optimal objective vector to the boundary subproblem with w i (denoted as z * ) must be Pareto-optimal, if and only if ∃j ∈ {1, . . . , m} \ {i} such that z r j ≤ z * j .Theorem 2. Let z r j ≤ z(i) c j for every j ∈ {1, . . . , m} \ {i}. z (i) c uniquely solves the boundary subproblem withEQUATIONif and only if z (i) c is cone-optimal.Corollary 1. To ensure the validity of Theorem 2 without further information, it is necessary to satisfy the condition z r j ≤ z(i) c j for every j ∈ {1, . . . , 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 a strict partial order (see Appendix F.1 for details) and belongs to the family of generalized Pareto domination [37] . We assume that the critical points are cone-optimal and a set of objective vectors is obtained by optimizing infinitely sampling boundary subproblems.According to Theorems 1 and 2, this set is a subset of the P F and the critical points are included in it. 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 x ∈ Ω, we haveEQUATIONwhere j satisfies f j (x * ) < f j (x).Theorem 3. An objective vector is cone-optimal, if and only if the objective vector is Pareto-optimal and the value of α satisfiesEQUATION)Corollary 2. A cone-optimal objective vector is also properly Pareto-optimal.The following question arises: under what conditions can a solution be considered cone-optimal? Let u = (0, 1, 1) ⊺ and v = (0.2, 0.5, 0.5) ⊺ be a critical point and Pareto-optimal objective vector, respectively. If α = 0.5, then v ≺ c u (since ũ = (1, 2, 2) ⊺ and ṽ = (0.8, 1.1, 1.1) ⊺ ); If α = 0.1, then u ⊀ c v and v ⊀ c u (since ũ = (0.2, 1.2, 1.2) ⊺ and ṽ = (0.32, 0.62, 0.62) ⊺ ). The critical point is cone-dominated if an excessive α 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 P S into proper and improper ones. The definition of proper Pareto optimality is shown in Definition 10. That is, a 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 α is bounded by M as shown in Theorem 3. Corollary 2 is established accordingly. We can let α be a sufficiently small value such that the critical points are cone-optimal. Theorem 4. Let z * be an objective vector satisfying z r j ≤ z * j for every j ∈ {1, . . . , m} \ {i}. If an objective vector z ′ does not cone-dominate z * and z * i ≥ z ′ i , then z * has a lower function value than z ′ with respect to some boundary subproblem of the i-th objective.Corollary 3. Let z e consist of the optimal values of m BLOPs and {z|z ≺ z e } be the promising region. Any Pareto-optimal objective vector outside the promising region fails to address the trade-off of decision-makers, namely, M > µ.The remaining issue is that M is not known in advance, making it difficult to set α according to M . We introduce a user-defined parameter µ (µ > 0) and let α = m (m-1)µ+m . µ represents the upper bound of the trade-off between the k-th and l-th objectives, where k = arg max 1≤j≤m f j (x * )-f j (x) and l = arg max 1≤j≤m f j (x) -f j (x * ). In other words, µ is the amount of increment in the value of one objective function that the decision-maker is willing to tolerate in exchange for a one-unit decrement in another objective function. If the preference of decision-makers about µ is available, we have the guarantee shown in Corollary 3 derived from Theorems 3 and 4. Corollary 3 can guarantee to obtain a satisfactory nadir objective vector. When the preference is not provided, µ can take a sufficiently large value. On the one hand, if a finite trade-off M exists for the critical point, then µ can take an appropriate value from [M, ∞) to obtain the nadir objective vector. On the other hand, M → ∞ results in α → 0, which means the corresponding objective vector is not properly Pareto-optimal. In practical terms, a Pareto-optimal solution with a very large value of M does not essentially differ from an inferior solution for decision-makers. If the critical points are improper, using a generally agreeable value of µ is reasonable. Theorem 5. The optimal objective vector to the boundary subproblem with w i (denoted as z * ) must be cone-optimal (or properly Pareto-optimal), if ∃j ∈ {1, . . . , m} \ {i} such that z r j < z * j . Theorem 6. Let z r j < z * j for every j ∈ {1, . . . , m} \ {i}. If an objective vector z * is optimal for the boundary subproblem with w i , z * must be an optimal objective vector to the boundary subproblem withEQUATIONMoreover, we can make minor modifications to Theorem 1, resulting in Theorem 5. Theorem 6 can be deduced using Theorem 5. Theorem 6 reveals the relationship between the boundary subproblem's optimal solution and the boundary weight vector, which is useful for designing the algorithm in Section 3.3.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 Paretooptimal objective vectors and 2) identifying critical points from Pareto-optimal ones. In the 2-objective 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) ⊺ and (0, 1) ⊺ as the weight vectors. This is because solving the boundary subproblem with w i is equivalent to solving that with βw i where β > 0 is a constant. Unfortunately, the critical points cannot be obtained by a fixed boundary subproblem when the MOP involves three or more objectives. That is, both goals cannot be achieved simultaneously. This motivates the formulation of a bilevel optimization problem (BLOP) for each objective to achieve the two goals: the lower-level optimization problem (LLOP) 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 is 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 z r j = 0 for j = 1, . . . , m in Eq. ( 3) and introduce two reference points z r1 and z r2 (z r2 j > z r1 j for j = 1, . . . , m) for normalization. Then, the boundary subproblem with normalization can be written asEQUATIONwheref ′ k (x) = (f k (x) -z r1 k )/ z r2 k -z r1 k for k = 1, . . . , m.In this formulation, z r1 should be set according to Theorem 1 and Corollary 1. For example, it is reasonable to set z r1 to z ide sincez ide j ≤ f j (x) for j = 1, . . . , m such that (1 -α)f ′ j (x) + α m m k=1 f ′ k (x) ≥ 0.Furthermore, z r2 should be set according to [40] . Secondly, several boundary subproblems might have the same optimal solution. On the one hand, solving the boundary subproblem with w i is equivalent to solving that with βw i where β > 0 is a constant. We can let m j=1∧j̸ =i w i j = 1. On the other hand, Theorem 6 indicates that the optimal objective vectors to 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 to the distance between the boundary weight vector and its optimal objective vector. Let x * be the optimal solution of the boundary subproblem with w i . In this paper, we calculate the distance asEQUATIONLet ϵ be a sufficiently small constant, l ∈ {1, . . . , m} \ {i}, and I = {1, . . . , m} \ {i, l}. Finally, the BLOP with respect to the i-th objective for i = 1, . . . , m has the ULOP formulated as max.EQUATIONwhere x * is the optimal decision vector to the LLOP of the following form min.EQUATION)The search is performed on the original decision space in the LLOP, while the search space of the ULOP can be viewed as R m-2 (i.e., (m -2)-dimensional Euclidean space). For the i-th objective, the ULOP uses a boundary weight vector w i as a solution and requires maximizing the i-th penalized objective function value of the Pareto-optimal 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 1, where µ is the user-defined upper bound of the trade-off (see Section 3.1 for details). Three following issues should be specified: determine the reference points z r1 and z r2 , choose suitable single-objective optimizers, and set the stopping criteria.To evaluate the viability of BDNE, we implement it for black-box MOPs. We adopt evolutionary algorithms as the solvers in BDNE. Each ULOP uses CMA-ES [41] to search the eligible boundary Generate boundary weight vectors by the solvers of unstopped ULOPs.Minimize LLOPs with the generated boundary weight vectors by the corresponding solvers.Update parameters: z r1 and z r2 (optional); parameters in 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 [41] . 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] . 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 as well as the LLOP. We use τ u and τ l to denote the maximum number of iterations for the ULOP and the LLOP respectively. z r1 is set to the current best objective function values. z r2 is constructed by the current best objective function values of m ULOPs. Initially, EC-NSGA-II [22] runs for τ l iterations. The minimum and maximum objective function values of its final population determine the settings of z r1 and z r2 . Then z r1 is updated once a new solution is generated. z r2 is only renewed when the parameters of CMA-ES update. During the optimization process, z r1 and z r2 iteratively approximate z ide and z nad respectively.Upper-Level Optimization. m ULOPs represents m CMA-ES procedures. Let ι = N m -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 i,j , j = 1, . . . , ι} denote the set of adjustable boundary weight vectors for the i-th objective. Initially, most of them are 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 is initialized to the vector with (m -1) elements being 1 m-1 (e.g., 0,EQUATION⊺). The remaining m ones, which are m different unit vectors, are fixed throughout the optimization of m 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 i,j ∈ A be the best solution so far for the subproblem with w i,j , and then the fitness of w i,j is defined as f i x i,j -ϵd w i,j , x i,j . 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 [44, 45] . Subsequently, the boundary weight vectors of the i-th objective are updated as follows:Step 1 W ← {w i,j , j = 1, . . . , ι} and then delete ⌊ ι 2 ⌋ the worst boundary weight vector in W .Step 2 Transform the best one in W according to Eq. (10) .Step 3 Create ⌊ ι 2 ⌋ new ones via the i-th CMA-ES procedure and integrate them into W .The updated z r2 may substantially alter the normalized space in Eq. ( 9), potentially changing the optimal solution to the LLOP. As Theorem 6 reports, Step 2 can effectively preserve the best solution for the LLOP, irrespective of changes in the normalized space. Particularly, in the last iteration of the ULOP (i.e., the τ u -th iteration), w i,1 , . . . , w i,ι are all changed to the boundary weight vector with the best fitness for i = 1, . . . , m. More computational resources are allocated to the i-th objective's current best LLOP in the final iteration. It 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 1 Use binary tournament selection based on π to obtain the mating pool from P .Step 2 Apply reproduction operators to create an offspring set of size N (denoted as O).π is a utility vector including utility values of solutions in P . A solution with a lower utility value is more likely to enter the mating pool. The selection procedure is performed as follows:Step 1 Calculate r = r 1 , . . . , r |P ∪O| ⊺ for P ∪ O.Step 2 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 ∪ O for the new generation of A.k ∈ P ∪ O, we let R k i,j be the ascending rank of g bdn i (x k |w i,j , z r1 , z r2 , α) within g bdn i (x|w i,j , z r1 , z r2 , α) | x ∈ P ∪ O . r k is formulated as r k = min (i,j)∈I {R k i,j } where I = {(i, j)|i = 1 . . . , m, j = 1, . . . , ι}.x k with a smaller r k implies a higher quality.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? • The experimental setting should be presented in the core of the paper to a 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, or as supplemental material. 
experimental setup: 
 Instances. We proposed 4 scalable test problems denoted as TN1-TN4. The feasible objective regions of TN1 and TN2 are shown in Figure 2a and Figure 2e . The P F of TN1 is a (m -1)-dimensional simplex. TN2 has a concave P F constructed by two (m -1)-dimensional 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 B. Moreover, we select problems with different shapes of feasible objective regions, including 6 existing test problems [46, 47, 48, 49] (DTLZ3, mDTLZ3, MaF2, DTLZ5, IMOP4, and IMOP6) and 4 real-world problems [50, 51, 52] (MP-DMP, ML-DMP, 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 P F s of RE3-4-7 and RE5-3-1 are unknown and represented by their current best solution sets. and the standard deviation across all runs for each instance. The performance rank on each instance is 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 rank sum test at 0.05 significant level. "∆" indicates the gap between the mean metric value of the corresponding algorithm and that of BDNE. The best mean metric values are also emphasized.Table 3 shows 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 TN1 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-II suffers from dominance-resistant 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 P F and the W P B can cause significant challenges for heuristic methods.We have proposed a new scalarization method, which can define specific boundary subproblems to find the nadir objective vector under mild conditions. We have formulated m BLOPs using boundary subproblems and designed a corresponding algorithm framework called BDNE. We have also conducted experimental studies to 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 as an independent algorithm (i.e., estimate the nadir objective vector beforehand). In the future, we will investigate how to integrate BDNE into the iteration of an algorithm to enhance its overall performance (see Appendix E.4 for 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. This is an appendix for "Boundary Decomposition for Nadir Objective Vector Estimation". Specifically, 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 µ, and the comparison with other heuristic methods (Appendix E); • Properties of the cone domination and proofs of theorems and corollaries (Appendix F).Existing heuristic methods for the nadir objective vector estimation can be divided into two categories [15] : 1) straightforward methods and 2) extreme-point-based methods. We use an example P F to illustrate the drawbacks of heuristic methods in estimating the nadir objective vector. As shown in Figure 3 , the P F consists of two triangles and is concave. We uniformly sample 225 points along the P F in order to include sufficient critical points. We use these sampled points as each method's population and test its performance in estimating the nadir objective vector.The experimental results are summarized in Table 4 and plotted in Figure 4 . We can observe from Table 4 that all methods incorrectly estimate the nadir objective vector. Specifically, Figure 4 show that all methods except for SF4 acquire the critical points of f 1 and f 2 but miss that of f 3 . As shown in Figure 3 , the critical point of f 3 is distant from every axis and thereby difficult to obtain by these methods. Table 4 : Estimated nadir objective vectors of existing heuristic methods. The nadir objective vector is (1, 1, 1.5) ⊺ . "SFx" denotes the straightforward method; "EPx" denotes the extreme-point-based method. Parameters settings: the minimum number of selected points is set to 10 for SF3 and SF4; λ in EP6 is set to 100.Method Result SF2 [24] (1, 1, 1.14) ⊺ SF3 [25] (1, 1, 1) ⊺ SF4 [26] (0.88, 0.96, 1.2) ⊺ EP1 [29] (1, 1, 1) ⊺ EP2 [28] (1, 1, 1) ⊺ EP3 (L2) [31] (L∞) [32] (1, 1, 1.18) ⊺ (1, 1, 1.39) ⊺ EP4 [33] (1, 1, 1.18) ⊺ EP5 [9] (1, 1, 1.39) ⊺ EP6 [34] (1, 1, 1.18) ⊺ 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 are its vertices. We design two problem generators that have controllable critical points.Each objective function of the proposed test problem generators takes the following formEQUATIONwhere s i is a constant such that different objectives can have different ranges of values; x ∈ Ω = [0, 1] n ⊂ R n , and x I = (x 1 , . . . , x m ) ⊺ and x II = (x m+1 , . . . , x n ) ⊺ are subvectors of x. g i (x II ) ≥ 0 is called the distance function, which specifies asEQUATIONh i (x I ) is termed as the position function, which determines the shape of the P F .The P F is a simplex. Firstly, we define y(x I ) : [0, 1] m → [0, 1] m as a base. It returns an mdimensional vector (y 1 , . . . , y m ) ⊺ as followsEQUATION{y(x I )|x I ∈ [0, 1] m } is an (m -1)-dimensional unit simplex. Then the position function value vector is calculated byEQUATIONwhere V = [v 1 , . . . , v m ] determines vertices of the P F . When s = (1, . . . , 1) ⊺ , v i is a vertex of the P F . Any v i should be non-dominated. V is the particular parameter to be specified. The critical points depend on the settings of V .The P F is two adjacent simplices. We modify the base of Generator 1 toEQUATIONEQUATIONandEQUATIONthe position function value vector isEQUATIONwhereEQUATIONThe P F of this generator consists of two simplices. Assume that s = (1, . . . , 1) ⊺ . The vertices of two simplices are the column vectors of V and V ′ respectively. The difference between V and V ′ is the last column. That is to say, two simplices share many common edges and they are adjacent. u is the particular parameter to be specified. The unique critical point of f 3 is u. The critical points of other objectives are the same as the inverted unit simplex whose objective vectors on any edge are critical points. We use the proposed test problem generators to obtain 4 scalable MOPs denoted as TN1-TN4. We first specify 1 matrix and 3 vectors:EQUATION• s 1 = (1, . . . , 1) ⊺ ;• if m = 3, s 2 = (1, 100, 10000) ⊺ ; otherwise, s 2 = (1, 100, 10000, 1, . . . , 1) ⊺ ;• if m = 3, u 1 = (0.9, 0.7, 1.5) ⊺ ; otherwise, u 1 = (0.9, 0.7, 1.5, 0.9, . . . , 0.9) ⊺ .Then the test problems are summarized in Table 5 . We can find that V 1 is obtained by modifying such matrix: an m × m square matrix with zeros on the main diagonal and ones elsewhere. This matrix implies that the P F is an inverted unit simplex whose objective vectors on any edge are critical points (e.g., mDTLZ1 [48] ). The modified vertices are the first and the second ones and the modification performs across f 1 to f 3 . Consequently, the critical points of f 1 , f 2 , and f 3 are some vertices only. For example, we show the feasible objective region of the 3-objective TN1 in Figure 5 . Vertices (0, 1.2, 1) ⊺ and (1, 1, 0) ⊺ 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 f 3 is unsupported (i.e., there exists convex combinations of objective vectors that dominate the critical point [57] ), making the P F exhibit a concave shape. Besides, the critical point of f 3 is distant from all axes and not optimal for any objective. TN3 and TN4 are extended from TN1 and TN2 respectively. They have huge magnitude differences between some objective functions.Table 5 : Parameter settings of TN1-TN4.Problem Generator Parameters Nadir objective vectorTN1 1 s = s 1 , V = V1 (1, 1.2, 1, . . . , 1) ⊺ TN3 2 s = s 1 , u = u 1 (1, 1, 1.5, 1, . . . , 1) ⊺ TN3 1 s = s 2 , V = V1 (1, 120, 10000, 1, . . . , 1) ⊺ TN4 2 s = s 2 , u = u 1(1, 100, 15000, 1, . . . , 1) ⊺ Figure 5 and Figure 6 also indicate these 4 problems process the W P B. The W P B has evident dominance resistance [23] . That is, the objective vectors of the W P B are usually non-dominated in the population, especially in many objective cases. The reason is that each of them can only improve k (1 ≤ k ≤ m -1) objectives to obtain an objective vector dominating it. Thus, they are difficult to distinguish from the population. The W P B 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 k = 1 on the W P B exhibit severe dominance resistance, even when presenting in 3-objective cases. Unfortunately, how to cope with the W P B is still an open question [58] .In experiments, our codes rely on the MATLAB-based platform called PlatEMO [59] , which is freely available for research purposes (see https://github.com/BIMK/PlatEMO). 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 128GB of RAM. We report the runtime for each algorithm on each instance in Table 6 . DNPE exhibits the shortest runtime, followed by ECR-NSGA-II. BDNE has a longer runtime than these two representative algorithms.We want to emphasize the runtime for BDNE strongly depends on 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 our BDNE implementation has a time complexity of O N log(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 r governs the complexity of the selection procedure, which has O N 2 log(N ) . The adjustment of boundary weight vectors with O N log N m is executed periodically. Therefore, The selection procedure governs the overall complexity, and the main loop has the complexity O N 2 log(N ) . We can significantly reduce the complexity by using a simple selection procedure or choosing an alternative solver, which deserves further investigation. Many real-world problems, such as logistics dispatch, printed-circuit 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-makers 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 to various problems by employing appropriate solvers. Furthermore, the parameter µ, which indicates the tolerance of decision-makers for trade-offs, could also be an important component in developing a more user-friendly multi-criteria decision system.On the downside, relying solely on the nadir objective vector for decision-making can be risky. Decision-makers should use additional information for a more informed and comprehensive decision. Moreover, the leakage of the nadir objective vector might inadvertently expose problem information and user preferences. This is particularly troublesome in certain applications where the confidentiality of such information is paramount, indicating a 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.We conduct a more comprehensive 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 are nearly impossible to apply to other types of MOPs. Nevertheless, we will propose the implementation of BDNE for the discrete MOP. Audiences can follow our work at https://github.com/EricZheng1024/BDNE.We investigate 3 schemes in BDNE. "CFF" denotes the coping strategy for flat fitness (see Section 3.2). "TBW" denotes the transformation of the best boundary weight vector (see Step 2 of the upper-level optimization in Section 3.3). "BSU" denotes the boundary subproblems using unit vectors as their weight vectors (see the upper-level optimization in Section 3.3). We investigate the impact of parameters in BDNE. Recall that µ is the user-defined upper bound of the trade-off, and τ u denotes the maximum number of iterations involved in the upper-level optimization.The Pareto-optimal objective vector, situated on the boundary of a convex P F , usually has a substantially higher value of M (see Definition 10) than that in the central region. We test BDNE with different settings of µ on mDTLZ2, since this problem has a convex P F and thus effectively discloses the impact of µ. We consider 6 values for µ: 1, 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 7 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 µ decreases. A smaller µ implies that decision-makers have a 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. Different MOPs have different difficulties in estimating the nadir objective vector. To clearly show the effects of τ u , we employ TN4, which possesses a complicated feasible objective region. Figure 8 plots the results. The value for τ u begins at 2, increases by 2, and ends at 18, while τ l remains 200.E ′ = m i=1 (ẑ nad i -z ide i )/(z nad i -z ide i ) 2 . FigureThe runtime is getting shorter as the value of τ u decreases, which is straightforward. Besides, the relationship between the runtime and τ u is linear. The curve of E versus τ u exhibits a declining trend with intermittent fluctuations. Generally, the error is getting smaller (or the accuracy is getting higher) as the value of τ u increases. The fluctuations occur because the lower-level optimization algorithm is stochastic (i.e., it does not guarantee the attainment of a Pareto-optimal solution within a finite number of iterations). In previous sections, we employ theoretical analysis, illustrative examples, and experimental comparisons with two representative baseline methods to demonstrate the advantage of BDNE over the existing heuristic ones. To more comprehensively validate the effectiveness of BDNE, we present the experimental results comparing our method with the remaining heuristic methods in Table 8 . The majority of heuristic methods cannot surpass our method on any instance, while our method significantly outperforms them on most instances. Table 9 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 (∆ < 0.03). In contrast, BDNE has remarkably better performance than EP1 on many instances. For example, ∆ < -0.3 on TN4 and TN4; ∆ < -1.5 on 5-and 8-objective DTLZ2; ∆ < -12 on 5-objective ML-DMP. For EP4, the better result only appears on 3-objective ML-DMP, and the gap is very small (∆ < 10 -4 ). EP4 shows poor results on the rest of the instances. We can conclude that our method still outperforms other heuristic methods. We present BDNE as an independent algorithm in 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 "V1". 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 [42] 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. V1 or V2 consumes 12 additional function evaluations for nadir objective vector estimation in each iteration, and as a result, it uses about 230 fewer iterations than the original MOEA.The statistical results of the hypervolume metric [61] are reported in Table 10 . The results of Wilcoxon's rank sum test are shown by two symbols in {+, =, -} in the cell. The first and second symbols are the comparison results with V1 and V2, respectively. We begin by analyzing the comparative results of the MOEA and V1. Both MOEA/D-V1 and NSGA-III-V1 significantly outperform their original versions, respectively. Besides, MOEA/D-V1 exhibits clearly smaller standard deviations compared with its original versions (e.g., 0.0106 versus 0.00289), indicating more stable performance. Analogously, NSGA-III-V1 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 V1, indicating the promising region determined by BDNE is 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 to improve the performance of an algorithm. EQUATIONIn 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 Pareto-optimal boundaries (e.g., TN1-TN4 and mDTLZ3), linear P F s (e.g., TN1 and TN3), convex P F s (e.g., mDTLZ3), concave P F s (e.g., TN2, TN4, and DTLZ3), irregular P F s (e.g., TN3, TN4, DTLZ5, IMOP4, and IMOP6).Table 11 summarizes the complete results on all the test problems by showing "Total +/=/-". DTLZ, MP-DMP, and ML-DMP are absent in this experiment, as the MaF test suite already covers them. Besides, IMOP1-IMOP3 are non-scalable 2-objective MOPs, which are also omitted. We can find that our method outperforms the two representative algorithms on most instances. Table 12 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 values of negative gaps can be very large. Besides, BDNE always ranks second on these instances, exhibiting competitive performance. In short, BDNE still shows its superiority on the three test suites. Proof. Since ũi = ũi for i = 1, . . . , m, we have u ⊀ c u.Property 2 (Anti-symmetry). If u ≺ c v, then v ⊀ c u.Proof. Since u ≺ c v, we have ũ ≺ ṽ. Thus, v ⊀ c u according to Definition 8.Property 3 (Transitivity). If t ≺ c u and u ≺ c v, then t ≺ c v.Proof. Since t ≺ c u and u ≺ c v, we have t ≺ ũ and ũ ≺ ṽ. According to the transitivity of Pareto domination, t ≺ ṽ. Therefore, t ≺ c v.The three properties imply that cone domination defines a strict partial order.Proof. Without loss of generality, we let z r j = 0 for j = 1, . . . , m. (Sufficiency) Let z * j ≥ z r j = 0 for at least one j ∈ {1, . . . , m} \ {i}. We consider an objective vector z satisfying z * ≺ z. We haveEQUATIONConsequently,EQUATIONSince ∃j ∈ {1, . . . , m} \ {i} such that z * j ≥ 0, we can deduce maxEQUATIONThe 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 z r j > z * j for each j ∈ {1, . . . , m} \ {i}. We consider z j = z * j + ϵ j for j = 1, . . . , m where ϵ j ≥ 0 is a sufficiently small value such that z * j < zj < z r j = 0. Then the following equation holds maxEQUATIONwhich indicates that z dominated by z * can also be optimal for the boundary subproblem. But this is a contradiction.Proof. Without loss of generality, we let z r j = 0 for j = 1, . . . , m. Since z(i) c j ≥ z r j for every j ∈ {1, . . . , m} \ {i}, we haveEQUATION(Sufficiency) Let z (i) c be cone-optimal. We assume that z, rather than z (i) c , is the optimal objective vector to this boundary subproblem. That is,EQUATIONSince z ⊀ c z (i) c and w i i • z(i) c i = 0, Eq. ( 28) implies that z(i) c i < zi and z(i) c j > zj for all j ∈ {1, . . . , m} \ {i}. Theorem 1 signifies z is Pareto-optimal, and thus the corresponding objective function value is larger than that of the critical point (i.e., zEQUATIONThere exists an index l ̸ = i such that zEQUATIONwhich means maxEQUATIONThis conclusion conflicts with the assumption. z (i) c is optimal for this boundary subproblem. Since z can be arbitrary, z (i) c is also the unique optimal objective vector.(Necessity) Let z (i) c uniquely solve the boundary subproblem withEQUATIONWe assume that z cone-dominates z (i) c . ThenEQUATIONConsequently,EQUATIONindicating that z (i) c is not uniquely optimal for the boundary subproblem. But this is a contradiction.Proof. Since the index l in Inequality (30) is not arbitrary, z (i) c j should be larger than z r j for j = 1, . . . , m.Proof. We first prove that a cone-optimal objective vector is Pareto-optimal. Letting z * be a coneoptimal objective vector and z ∈ {f (x)|x ∈ Ω}, we haveEQUATIONSinceEQUATIONthen ∃k, z * k -z k < 0.We now prove that α ≤ m (m-1)M +m holds for a cone-optimal objective vector. Given a Pareto-optimal objective vector z * and an objective vector z ∈ {f (x)|x ∈ Ω}, to make sure that z * is Pareto-optimal for each z, the following inequality should hold minEQUATIONSince ∃j, z * j -z j < 0, we haveEQUATIONThe Definition 10 is equivalent to a properly Pareto-optimal decision vector x * ∈ Ω satisfying that maxEQUATIONwhere x ∈ Ω and max 1≤j≤m f j (x) -f j (x * ) > 0. According to Inequalities (38) and ( 39), we haveEQUATIONThenEQUATIONSince max 1≤j≤m (z j -z * j ) > 0, thenEQUATIONIf a cone-optimal objective vector is not properly Pareto-optimal, α ≤ 0 should hold according to Theorem 3. Therefore, a cone-optimal objective vector has a finite value of M , indicating it is properly Pareto-optimal. However, α > 0 as shown in Definition 8. The formal proof is as follows.Proof. Let z * be a cone-optimal objective vector. We assume that z * is not properly Pareto-optimal. Then there exists an objective vector z such that maxEQUATIONSince z * is a Pareto-optimal objective vector, we haveEQUATIONThe inequality can be rewritten as EQUATIONThe proof is analogous to the sufficiency proof of Theorem 2.Proof. Without loss of generality, we let z r j = 0 for j = 1, . . . , m. According to Theorem 6, we can let w i j = β/z * j for every j ∈ {1, . . . , m} \ {i}. Then we have maxEQUATIONwhere β is a constant.Suppose that z ′ yields a lower function value than z * for the boundary subproblem with w i . That is, maxEQUATIONand z * ⊀ z ′ according to Theorem 1. Since z ′ ⊀ c z * , Eq. ( 47) implies that z * i < z′ i and z * j > z′ j for every j ∈ {1, . . . , m} \ {i}. Based on z *EQUATIONThere exists an index l ̸ = i such that z * l < z ′ l . Therefore,EQUATIONwhich means maxEQUATIONThis conclusion conflicts with the assumption.Proof. According to Theorem 3, the Pareto-optimal objective vector deviating from the user-defined trade-off is cone-dominated by some objective vector. And Theorem 4 reports the cone-optimal objective vector that maximizes a given objective is optimal for at least one boundary subproblem.F.9 Proof of Theorem 5The proof is modified from the sufficiency proof of Theorem 1.Proof. Without loss of generality, we let z r j = 0 for j = 1, . . . , m. We consider an objective vector z satisfying z * ≺ c z. Then we haveEQUATIONConsequently,EQUATIONSince ∃j ∈ {1, . . . , m} \ {i} such that z * j > 0, we can deduceEQUATIONz can not be optimal for the boundary subproblem. Therefore, the optimal solution to the boundary subproblem must be cone-optimal. According to Corollary 2, the optimal solution is also properly Pareto-optimal.F.10 Proof of Theorem 6Proof. Let z r j = 0 for j = 1, . . . , m. Suppose that z, rather than z * , is optimal for the subproblem with w * . Letting w * j z * j = β for j ∈ {1, . . . , m} \ {i} where β > 0 is a constant, we have wEQUATIONSince z * is properly Pareto-optimal according to Theorem 5, we have w * j > 0, j ̸ = i. We can deduce that z * j > zj ≥ 0 for j ∈ {1, . . . , m} \ {i}. For the subproblem with w i we obtainEQUATIONwhich implies z, rather than z * , is the optimal objective vector to the boundary subproblem with w i . This is a contradiction.NeurIPS Paper Checklist 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments? 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, confidence intervals, or statistical significance tests, at 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).• Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness 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 a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an 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 a 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 as 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 or 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 to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe 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)? 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 a 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 a best faith effort. 12. Licenses for existing assets Question: 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? Answer: [Yes] Justification: See Appendix C. Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a 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 the 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 a dataset.The source code is available at https://github.com/EricZheng1024/BDNE. 
 
 Appendix:  


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 1. The algorithm proposed in this paper is an approximation algorithm rather than an exact one.
2. The algorithm is general. Its performance may be unsatisfactory for some specific problems.
3. The lower-level optimization problem consists of a series of single-objective subproblems, limiting the applicability of some multi-objective optimization algorithms.
questions: questions: 1. Is there evidence of really complicated feasible objective spaces from industrial applications?
2. The algorithm for the lower-level optimization problem appears to be quite complicated.  Can we consider changing it to a different one?
3. Can evolutionary algorithms be used in the optimization problems proposed by Gokhan et al. (2015)?
4. How are the benchmarks chosen in the experiment?
5. What is the performance if coping strategies for flat fitness are eliminated?
6. I also wonder about the effects of removing the subproblems with unit vectors.
7. I recommend providing a more detailed analysis of the deficiencies of the heuristic methods.
limitations: 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.
paper_summary: paper_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.
strength_weakness: strength_weakness: I do not find any obvious weakness, but I have the following questions:

1. 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?

2. How should one select a value for the parameter mu in BDNE?

3. 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?

3. I notice that the error on CRE5-3-1 is large (about 20%). Please explain this.

4. Why are algorithms only tested on continuous problems?
questions: questions: Refer to the above comments.
limitations: limitations: The discussion in the conclusion section is comprehensive enough.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
2. m boundary weight vectors remain unchanged throughout.  It may waste the computational resources.
3. Solving the original problem creates a new optimization problem, potentially increasing complexity.  And BDNE does require a longer runtime than the compared algorithms.
4. The illustration of setting mu is a bit preliminary.
questions: questions: 1. Why fix m boundary weight vectors as unit vectors?  Can they change after some iterations?
2. The setting of mu should have a further discussion.
3. What increases the computational cost of BDNE?  The computational complexity of BDNE should be analyzed.
4. What advantages does this method have compared to existing exact algorithms when applied to discrete problems?
limitations: limitations: The longer runtime of the proposed algorithm might also be a limitation that is not thoroughly discussed in the paper.
paper_summary: paper_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.
strength_weakness: strength_weakness: Generally, this paper is not well written, and the empirical study is not well organized.

## Presentation
I 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).

Moreover, 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.

## Experiment
The 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.

Here are some minor remarks for the experiment part:
* 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.
* 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.
* 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.
questions: questions: Please refer to *Weaknesses*.
limitations: limitations: No concerns.

Comments: title: Thank you very much for your comment [2/2].
Thank you very much for your comment [1/2].
comment: We sincerely thank you for raising your score and are glad to know your major concerns have been satisfactorily addressed. We will include a more comprehensive empirical comparison in our final version. Thank you very much for your time and valuable suggestions, which will greatly help us improve our manuscript.
Thank you for your response. Now most of my major concerns have been satisfactorily addressed, so I increased my rating. I know it is very difficult to prepare the additional results during the rebuttal period, so I do appreciate your efforts. However, I strongly suggest the authors incorporate a more comprehensive and solid empirical study in the camera-ready version (if accepted) including a comparison with other strong baselines on more test problems and an ablation study to explore how BDNE helps improve the performance of MOAs in practical scenarios. I think a wide range of audiences may be interested in these results.
Thank you very much for your time and effort in reviewing our work, and we are glad to know your concerns have been resolved.
Thank you very much for raising your score and appreciating our previous response. 

We sincerely appreciate your valuable suggestions. We will add these discussions and revise our manuscript accordingly.
Thank you very much for your feedback, and we are pleased to hear that some of your concerns have been adequately addressed. We address your remaining concerns as follows.

In our original manuscript, we mainly use theoretical analysis and illustrative examples to demonstrate the advantage of our method over the existing heuristic ones. We believe this is sufficient to validate the shortcomings of these current methods. Therefore, we only use two representative baselines in our empirical study. To more comprehensively illustrate the effectiveness of our method, we present the experimental results of the other heuristic methods in the following table. We can find that our method still outperforms the other methods.


| Problem      | $m$ | 2017 [1]         | 2018 [2]          | 2019 [3]            | 2019 [4]             | 2021 [5]          | 2022 [6]                | 2022 [7]            | 2023 [8]          | BDNE                   |
|--------------|-----|------------------|-------------------|---------------------|----------------------|-------------------|-------------------------|---------------------|-------------------|------------------------|
| TN1          | 3   | 2.232±1.36(9)-   | 0.8477±0.2477(7)- | 1.044±0.2409(8)-    | 0.2026±1.58e-07(5)-  | 0.3735±0.3905(6)- | 1.708e-15±3.328e-15(2)= | 0.09419±0.1188(3)-  | 0.1704±0.2911(4)- | 3.144e-16±6.649e-16(1) |
| TN2          | 3   | 1.456±0.9491(9)- | 0.5103±0.2975(7)- | 1.054±8.842e-15(8)- | 0.2231±3.543e-07(3)- | 0.437±0.2457(6)-  | 0.3333±0(5)-            | 0.1506±0.28(2)-     | 0.266±0.211(4)-   | 0.0001722±0.0005349(1) |
| TN3          | 3   | 2.151±1.429(9)-  | 0.7755±0.2774(7)- | 1±0(8)-             | 0.2628±4.023e-08(5)- | 0.2744±0.2297(6)- | 6.388e-16±9.846e-16(2)= | 0.04554±0.03419(3)- | 0.1234±0.1045(4)- | 2.388e-16±2.32e-16(1)  |
| TN4          | 3   | 1.348±0.8802(9)- | 0.4879±0.3249(7)- | 1.054±1.748e-15(8)- | 0.3367±4.039e-08(5)- | 0.4094±0.1397(6)- | 0.3333±0(4)-            | 0.1554±0.265(2)-    | 0.2631±0.1829(3)- | 4.924e-05±5.587e-05(1) |
| Average rank |     | 9(9)             | 7(7)              | 8(8)                | 4.5(5)               | 6(6)              | 3.25(3)                 | 2.5(2)              | 3.75(4)           | 1(1)                   |


In Common Concern 2, we also present experimental results demonstrating the promising performance of our method in comparison to exact methods. We will supplement these experiments in the revised paper and release our code upon publication. We hope the above discussion can address your remaining concerns. Please let us know if you have any further concerns.

[1] Nadir point estimation for many-objective optimization problems based on emphasized critical regions. Soft Computing, 2017.

[2] A constrained decomposition approach with grids for evolutionary multiobjective optimization. TEVC, 2018.

[3] Distance-based subset selection for benchmarking in evolutionary multi/many-objective optimization. TEVC, 2019.

[4] IGD indicator-based evolutionary algorithm for many-objective optimization problems. TEVC, 2019.

[5] A many-objective evolutionary algorithm based on a two-round selection strategy. TCYB, 2021.

[6] Multiobjective Optimization-Aided Decision-Making System for Large-Scale Manufacturing Planning. TCYB, 2022.

[7] A twin-archive guided decomposition based multi/many-objective evolutionary algorithm. Swarm and Evolutionary Computation, 2022.

[8] A many-objective evolutionary algorithm with adaptive convergence calculation. Applied Intelligence, 2023.
I thank the authors for their effective responses, and I have increased my score to 7 and will vote for acceptance. I appreciate the added experiments and the discussion, which are comprehensive and useful.
I suggest the authors add these discussions to the final version. Meanwhile, a more detailed summary of the advantages or weaknesses of the proposed method compared to existing ones would be beneficial to underscore this paper's significance and positioning.
Thank you for the rebuttal. My concerns have been resolved, so I will maintain the positive score.
Thank you for your response. Some of my concerns have been adequately addressed. However, the authors mentioned that there are around 8,000 papers focusing on nadir point estimation. However, there are only two baselines presented in this paper, and they were 7 years ago. I think the empirical study in this paper can be further improved, and the current evaluation is not very comprehensive. I am still worried about whether the method proposed in this paper is more effective than existing ones.
We notice that your rating remains unchanged. Could you please let us know if your previous concerns have been addressed?

If you have any new concerns, please let us know as well.
Thanks for your further comments. We apologize for the unclear expression. The two trade-offs are different.

``Trade-off in W1.``

This refers to the trade-off between the accuracy of the estimated nadir objective vector and the runtime of BDNE. This trade-off can be controlled by the parameter $\tau_u$. A larger value of $\tau_u$ results in higher accuracy, while a smaller value of $\tau_u$ leads to a shorter runtime. We provide the following experiments to show the effects of $\tau_u$. The first and second tables present statistical results of errors and runtimes, respectively. We can find that the runtime is getting shorter as the value of $\tau_u$ decreases; the error is getting smaller (or the accuracy is getting higher) as the value of $\tau_u$ increases.

|Problem|$m$|2|6|10|14|18|
|--------------|-----|--------------------|----------------------|------------------------|-----------------------|------------------------|
|TN4|3|0.01654±0.01637(5)|0.001661±0.001799(4)|0.0001939±0.0002971(3)|0.000134±0.0004145(2)|5.646e-05±0.0002382(1)|
||5|0.08632±0.05066(5)|0.01003±0.01915(4)|0.009246±0.02555(2)|0.003051±0.007012(1)|0.009329±0.02633(3)|
||8|0.08955±0.09165(5)|0.03703±0.05067(3)|0.04032±0.08866(4)|0.03051±0.04605(2)|0.0255±0.02799(1)|
|Average rank||5(5)|3.6667(4)|3(3)|1.6667(1)|1.6667(1)|

|Problem|$m$|2|6|10|14|18|
|--------------|-----|-----------------|-----------------|-----------------|----------------|----------------|
|TN4|3|4.551±0.1162(1)|12.52±0.3078(2)|20.04±0.4353(3)|27.44±0.488(4)|34.89±0.645(5)|
||5|8.587±0.2431(1)|23.2±0.3991(2)|37.45±0.5952(3)|51.6±0.8106(4)|65.96±1.079(5)|
||8|16.22±0.2524(1)|44.8±0.6788(2)|72.78±1.144(3)|100.9±1.64(4)|129.1±1.898(5)|
|Average rank||1(1)|2(2)|3(3)|4(4)|5(5)|


``Trade-off in W4/Q2.``

This implies the trade-off between objectives. This trade-off is the parameter $\mu$, determined by the decision-maker. Specifically, $\mu$ is the amount of increment in the value of one objective function that the decision-maker is willing to tolerate **in exchange for a one-unit decrement in another objective function** (in the context of the minimization problem). Each Pareto-optimal solution corresponds to a particular value of $M$ (see Definition 10 in our original manuscript). If $M \leq \mu$, the Pareto-optimal solution aligns with the decision-maker’s preference. Otherwise, the Pareto-optimal solution should be discarded. We refer to the region where the objective vectors dominate the estimated nadir objective vector by BDNE as the promising region. Solutions outside this promising region can be ignored. Without the preference of $\mu$, $\mu$ is set to a reasonably large value, and BDNE finds the exact nadir objective vector. When this preference is available, the estimated nadir objective vector by BDNE may further narrow down the promising region.

we conduct experiments to show the effects of $\mu$. The estimation errors are statistically shown in the following table. We can find that a smaller value makes a larger error. We also examine the position of the estimated nadir objective vector. The estimated one is dominated by the exact one on every instance. These findings indicate that a smaller value of $\mu$ can yield a more refined promising region.

|Problem|$m$|1|5|10|50|100|
|---------|---|---------------------|---------------------|---------------------|----------------------|-----------------------|
|mDTLZ2|3|0.5211±0.0006548(5)|0.1548±0.001253(4)|0.0793±0.002107(3)|0.01325±0.001883(2)|0.006579±0.001046(1)|
||5|0.3927±0.0108(5)|0.08951±0.008372(4)|0.0471±0.003567(3)|0.01099±0.00667(2)|0.004697±0.0004873(1)|
||8|0.2884±0.01397(5)|0.06433±0.004405(4)|0.03188±0.002174(3)|0.005223±0.001297(2)|0.003585±0.004993(1)|
Thank you very much for your prompt reply. The number of function evaluations is the same as in our original manuscript, i.e., 180,000. We confirm that both MOEA/D and MOEA/D-V1 use the same FE budget. MOEA/D-V1 consumes 12 FEs for nadir objective vector estimation in each iteration and uses fewer iterations (about 230 less than MOEA/D).
Thank you for your reply and additional experiments with the discrete problem, which make me more explicit about the significance of the proposed BNDE. However, I am still confused about the "trade-off" in W1 and W4/Q2. If the authors could provide more explanations or illustrations, I would consider raising my rating.
Thank you for your response. This new experiment is very meaningful. Can you report the FE budget for this experiment? 
Do MOEA/D and MOEA/D-V1 use the same budget (including those used in the nadir point estimation)?
``Inaccurate estimates do not constitute a bottleneck for multi-objective optimization algorithms.``

We also respectfully disagree with this statement. Experimental results on existing benchmarks cannot reflect the algorithm's real capability, as these benchmarks are manually designed with special features and can only be used to evaluate the algorithm's specific properties [1]. We provide the following experiment to demonstrate that inaccurate nadir objective vector estimation can have a significant impact on algorithm performance. We consider MOEA/D and NSGA-III. We replace their nadir objective vector estimation methods with ours and denote the variant as "V1". The mean and standard deviation of the hypervolume metric values are reported in the table. We can find that both MOEA/D-V1 and NSGA-III-V1 significantly outperform their original versions, respectively. Additionally, MOEA/D-V1 exhibits clearly smaller standard deviations compared with its original versions (e.g., 0.01 versus 0.003), indicating more stable performance. NSGA-III-V1 also yields stable performance.

|Problem|$m$|MOEA/D|MOEA/D-V1|
|--|--|--|--|
|TN1|3|0.3891±0.01062(2)-|0.3986±0.002891(1)|
|TN2|3|0.2166±0.01537(2)-|0.2271±0.002339(1)|
|TN3|3|0.389±0.01352(2)-|0.3987±0.004753(1)|
|TN4|3|0.2135±0.02198(2)-|0.2269±0.002335(1)|

|Problem|$m$|NSGA-III|NSGA-III-V1|
|--|--|--|--|
|TN1|3|0.3361±0.02089(2)-|0.3769±0.003307(1)|
|TN2|3|0.2114±0.01662(1)=|0.2071±0.002607(2)|
|TN3|3|0.3383±0.02713(2)-|0.3782±0.003549(1)|
|TN4|3|0.1442±0.02976(2)-|0.2096±0.003082(1)|

We hope the above experiment can help you better understand the significance of the accurate nadir objective vector.

[1] Ishibuchi et al. Performance of Decomposition-Based Many-Objective Algorithms Strongly Depends on Pareto Front Shapes. TEVC, 2017.

``Limited contribution to multi-objective optimization.``

We cannot agree with you on this point as well. Nadir point estimation has always been a fundamental yet important research direction in multi-objective optimization, and many papers have been published on this topic. We search on Google Scholar using *("nadir point" OR "nadir objective vector") AND ("estimate" OR "find" OR "compute")* and return over 8,000 results. Compared with existing methods, our method is the first work with theoretical guarantees and general applicability. We would like to emphasize that our method is not only able to accurately estimate the nadir objective vector but also can trade off the accuracy for faster runtime. Our method can cope with scenarios that require the accurate nadir objective vector while ensuring broad applicability to cases that do not need an accurate nadir objective vector.

``How the proposed method could improve the performance of an algorithm?``

We further improve NSGA-III-V1 by focusing the search within the promising region defined by the nadir objective vector. The statistical results of the hypervolume metric are presented in the following table. The improved version of NSGA-III-V1 is termed NSGA-III-V2. According to the results, our method shows great potential to improve the performance of an algorithm. Moreover, we find that NSGA-III-V2 retains more solutions within the promising region compared with NSGA-III-V1 (30 versus 39 on TN1, 25 versus 32 on TN2, 32 versus 38 on TN3, and 25 versus 33 on TN4). This explains the performance improvement and demonstrates the effectiveness of the scheme.

|Problem|$m$|NSGA-III|NSGA-III-V1|NSGA-III-V2|
|--|--|--|--|--|
|TN1|3|0.3361±0.02089(3)-|0.3769±0.003307(2)-|0.3849±0.003166(1)|
|TN2|3|0.2114±0.01662(2)-|0.2071±0.002607(3)-|0.2125±0.002711(1)|
|TN3|3|0.3383±0.02713(3)-|0.3782±0.003549(2)-|0.3821±0.003803(1)|
|TN4|3|0.1442±0.02976(3)-|0.2096±0.003082(2)-|0.213±0.00347(1)|
Thanks for your further comments. Below is our point-to-point response.

``Practical significance of an exact nadir point.``

Firstly, we must clarify that our method is not just an exact algorithm, and its accuracy and runtime can be balanced via a controllable parameter. Secondly, we do not intend to claim that the accurate nadir objective vector is necessary for **all** multi-objective optimization scenarios. What we emphasize is that we should not ignore the cases where the accurate nadir objective vector is essential. There have already been a lot of works devoted to accurate nadir objective vector estimation [1-13]. We provide the following three examples:

* The nadir objective vector frequently serves as the reference point of scalarization methods. Some applications require specifying an accurate nadir objective vector beforehand [10,11]. An underestimated nadir objective vector makes some Pareto-optimal solutions unattainable, whereas an overestimated one results in poor uniformity of obtained objective vectors.
* The nadir objective vector determines the search space for some exact methods, such as AUGM-2. Exact methods without an accurate nadir objective vector may skip some Pareto-optimal solutions or exhibit longer runtimes. A recent experimental analysis can be found in [12].
* Many interactive methods, such as the NIMBUS method, require accurate nadir values to present the promising region of the objective space for decision-makers [13]. If inaccurate nadir values are given, more interactions are conducted or a biased decision is made.

[1] Ehrgott et al. Computation of ideal and nadir values and implications for their use in MCDM methods. EJOR, 2003.

[2] Klamroth et al. Integrating Approximation and Interactive Decision Making in Multicriteria Optimization. OR, 2007.

[3] Dhaenens et al. K-PPM A new exact method to solve multi-objective combinatorial optimization problems. EJOR, 2010.

[4] Florios et al. Generation of the exact Pareto set in Multi-Objective Traveling Salesman and Set Covering Problems. Applied Mathematics and Computation, 2014.

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

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

[7] Boland et al. A new method for optimizing a linear function over the efficient set of a multiobjective integer program. EJOR, 2017.

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

[9] Altamiranda et al. A New Exact Algorithm to Optimize a Linear Function over the Set of Efficient Solutions for Biobjective Mixed Integer Linear Programs. INFORMS Journal on Computing, 2020.

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

[11] 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.

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

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


``Most multi-objective optimization algorithms estimate the nadir point based on the current solution set.``

We respectfully disagree with this statement. Many works show that only multi-objective evolutionary algorithms often use the current solution set to estimate the nadir objective vector [1]. Other widely adopted nadir objective vector estimation methods include the pay-off table method [2], extreme-point-based methods [3], subset-selection-based methods [4], and exact methods [5].

[1] He et al. A survey of normalization methods in multiobjective evolutionary algorithms. TEVC, 2021.

[2] Reeves et al. Minimum values over the efficient set in multiple objective decision making. EJOR, 1988.

[3] Deb et al. An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part I: Solving problems with box constraints. TEVC, 2014.

[4] Mallipeddi et al. A twin-archive guided decomposition based multi/many-objective evolutionary algorithm. Swarm and Evolutionary Computation, 2022.

[5] Özpeynirci et al. On nadir points of multiobjective integer programming problems. Journal of Global Optimization, 2017.
Thank you for your response. My primary concern is that the authors have not adequately addressed the practical significance of an exact nadir point. I would like to emphasize that most existing multi-objective optimization algorithms estimate the nadir point based on the current solution set. While I acknowledge that such estimates are not accurate, they do not constitute a bottleneck for these algorithms. I recognize that the exact calculation of the nadir point is an interesting problem, but I believe that the contribution of this paper to the field of multi-objective optimization is very limited. The empirical study in this paper only demonstrates that the proposed method could accurately calculate the nadir point, but not how the proposed method could improve the performance of a multi-objective optimization algorithm.
We sincerely appreciate your support and are delighted to hear that all your concerns have been addressed.
Thanks for the response. I am glad to see that the proposed method can also work as an exact algorithm and achieve a shorter running time than other existing exact algorithms. The controllable trade-off between running time and accuracy is important and will greatly benefit the development of more advanced multi-objective optimization algorithms. My other concerns have been addressed as well. I will increase my score to 7 and support its acceptance.