Sandwiching algorithms, also known as Benson-type algorithms, approximate the nondominated set of convex bounded multiobjective optimization problems by constructing and iteratively improving polyhedral inner and outer approximations. Using a set-valued metric, an estimate of the approximation quality is determined as the distance between the inner and outer approximation. The convergence of the algorithm is evaluated with respect to this approximation quality.
We show the convergence rate of a class of Sandwiching algorithms by extending results for a similar algorithm for the approximation of convex compact sets. In particular, we derive requirements for the nondominated set to have a twice continuously differentiable boundary.
We show that two common quality indicators, the polyhedral gauge and the epsilon indicator, fulfill the necessary requirements and explicitly state the convergence rate for these two indicators.
Under sufficient regularity assumptions, the convergence rate is optimal.