This paper proposes an approach based on surrogate models to reduce the computational cost of evidence-based robust design optimization. Evidence Theory provides two quantitative measures, Belief and Plausibility, that defines the lower and upper probability that a given proposition is true under uncertainty. The maximization of the Belief is of great interest to the designers because it provides the design solution such that a given proposition on the system budgets is always true, given the current evidence on the set of uncertain design parameters. The paper introduces a novel min-max multi-objective optimization algorithm to maximize the Belief in multiple conicting propositions. Then an approach based on surrogate models is presented to substantially reduce the computational cost associated with the optimization of the design solutions that maximize the Belief in the given proposition. A simple test case of spacecraft system design is presented will illustrate how to apply the proposed approach.