We present a new method for inferring the Pareto front in multi-criteria optimization problems. The approach is grounded on an algorithm for learning the boundary between valid and invalid configurations of a multi-dimensional space (X). The algorithm selects sampling points for which it submits membership queries x ∈ X to an oracle. Based on the answers and relying on monotonicity, it constructs an approximation of the boundary. The algorithm generalizes binary search on the continuum from one-dimensional (and linearly-ordered) domains to multi-dimensional (and partially-ordered) ones. The procedure explained in this paper has been applied for the parameter synthesis of extended Signal Temporal Logic (STLe) expressions where the influence of parameters is monotone. Our method has been implemented in a free and publicly available Python library.