Research map / Learning theory and algorithms / Combinatorial and search optimization
Boundary Decomposition for Nadir Objective Vector Estimation
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes BDNE, a bilevel boundary-decomposition method that estimates the nadir objective vector of general black-box MOPs with convergence guarantees, and beats ECR-NSGA-II and DNPE on 28 instances.
Problem
Estimating the nadir objective vector of multi-objective optimization problems; existing exact methods only work on discrete MOPs and heuristic methods fail on complicated feasible objective regions (irregular PF, weakly Pareto-optimal boundary).
Approach
Scalarize the MOP into boundary subproblems using a cone-transformed modified Tchebycheff metric, and formulate per-objective bilevel optimization where the upper level (CMA-ES) adjusts boundary weight vectors to maximize each objective at its Pareto-optimal solution found by the lower-level MOEA, so that the optimal solutions converge to critical points and the nadir.
Key results
- BDNE attains the best average rank (1.07) over 28 instances in the error metric, versus 2.04 for DNPE and 2.89 for ECR-NSGA-II; it is significantly better on 27 of 28 instances against ECR-NSGA-II and 26 against DNPE.
- On the proposed TN1-TN4 problems with complicated feasible regions, BDNE's mean error stays below about 0.03 while DNPE and ECR-NSGA-II errors are around 0.17-12.7.
- BDNE is slower than the baselines: runtime is roughly 2-3x that of ECR-NSGA-II and DNPE on the reported instances.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use BDNE instead of DNPE | nadir-vector estimation · TN2 (3 objectives) | error metric: 0.223±3.54e-07 -> 0.000172±0.000535 | Helped |
| use BDNE instead of DNPE | nadir-vector estimation · DTLZ2 (3 objectives) | error metric: 4.29e-10±3.33e-10 -> 1.81e-10±2.82e-10 | Helped |
| use BDNE instead of DNPE | nadir-vector estimation · mDTLZ2 (3 objectives) | error metric: 0.0209±6.14e-06 -> 0.00658±0.00105 | Helped |
| use BDNE instead of DNPE | nadir-vector estimation · MaF2 (3 objectives) | error metric: 0.00888±2.9e-11 -> 0.00888±1.15e-05 | No clear effect |
| use BDNE instead of DNPE | nadir-vector estimation · ML-DMP (3 objectives) | error metric: 0.00699±2.82e-05 -> 0.0162±8.56e-05 | Hurt |
| use BDNE instead of DNPE | nadir-vector estimation · MP-DMP (3 objectives) | error metric: 0.23±8.03e-06 -> 0.00777±2.85e-05 | Helped |
| use BDNE instead of DNPE | nadir-vector estimation · RE3-4-7 (3 objectives) | error metric: 0.545±2.61e-06 -> 0.0787±0.00862 | Helped |
| use BDNE instead of DNPE | nadir-vector estimation · CRE5-3-1 (5 objectives) | error metric: 0.191±7.18e-08 -> 0.191±9.99e-09 | No clear effect |
| add CFF, the flat-fitness coping strategy (ablation) | BDNE · TN2 (3 objectives) | error metric: 0.00016±0.000351 -> 0.000172±0.000535 | No clear effect |
| add TBW, transformation of the best boundary weight vector (ablation) | BDNE · TN2 (3 objectives) | error metric: 0.000783±0.00195 -> 0.000172±0.000535 | No clear effect |
| add CFF and TBW (ablation) | BDNE · TN2 (3 objectives) | error metric: 0.000494±0.000865 -> 0.000172±0.000535 | Mixed |
| add boundary subproblems using unit-vector weights (BSU) (ablation) | BDNE · TN2 (3 objectives) | error metric: 0.00548±0.0137 -> 0.000172±0.000535 | Helped |
Surprising findings
- DNPE, an extreme-point heuristic, is competitive on several standard problems (e.g., MaF2, DTLZ5, DTLZ2) where its extreme points happen to be close to the critical points.
- The heuristic ECR-NSGA-II has large standard deviations on many instances because dominance-resistant solutions mislead the max-over-population estimate.
Limitations
- BDNE is run as an independent offline procedure and its runtime is longer than the heuristic baselines, with complexity O(N^2 log N) per main loop.
- The method has not yet been refined for discrete MOPs; exact-method comparisons are omitted.
- Estimated nadir vectors can be dominated by the exact nadir; the trade-off parameter mu must be set and affects accuracy.
Experimental setup
Datasets: DTLZ2 DTLZ3 mDTLZ2 mDTLZ3 MaF2 DTLZ5 IMOP4 IMOP6 MP-DMP ML-DMP RE3-4-7 CRE5-3-1
Benchmarks: TN1 TN2 TN3 TN4 DTLZ2 DTLZ3 mDTLZ2 MaF2 DTLZ5 IMOP4 IMOP6 MP-DMP
Metrics: nadir error metric E (normalized Euclidean distance) Wilcoxon rank-sum test runtime
Baselines: ECR-NSGA-II DNPE SF2 SF3 SF4 EP1 EP2 EP3 EP4 EP5
Builds on: modified Tchebycheff metric cone domination proper Pareto optimality CMA-ES EC-NSGA-II
Closest papers by meaning
- Boundary Decomposition for Finding Nadir Objective Vector in Multi-Objective Discrete Optimization (AAAI 2025 · similarity 0.95)
- MOBO-OSD: Batch Multi-Objective Bayesian Optimization via Orthogonal Search Directions (NeurIPS 2025 · similarity 0.83)
- Speeding Up the NSGA-II with a Simple Tie-Breaking Rule (AAAI 2025 · similarity 0.82)
- Penalty-based Methods for Simple Bilevel Optimization under Hölderian Error Bounds (NeurIPS 2024 · similarity 0.82)
- MGDA Converges under Generalized Smoothness, Provably (ICLR 2025 · similarity 0.82)
- Double Variance Reduction: A Smoothing Trick for Composite Optimization Problems without First-Order Gradient (ICML 2024 · similarity 0.82)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.