Techniques for exploring the suboptimal setJ. Skaf and S. Boyd
Optimization and Engineering, 11(2):319-337, June 2010. The \(\epsilon\)-suboptimal set \(\mathcal X_\epsilon\) for an optimization problem is the set of feasible points with objective value within \(\epsilon\) of optimal. In this paper we describe some basic techniques for quantitatively characterizing \(\mathcal X_\epsilon\), for a given value of \(\epsilon\), when the original problem is convex, by solving a modest number of related convex optimization problems. We give methods for computing the bounding box of \(\mathcal X_\epsilon\), estimating its diameter, and forming ellipsoidal approximations. Quantitative knowledge of \(\mathcal X_\epsilon\) can be very useful in applications. In a design problem, where the objective function is some cost, large \(\mathcal X_\epsilon\) is good: It means that there are many designs with nearly minimum cost, and we can use this design freedom to improve a secondary objective. In an estimation problem, where the objective function is some measure of plausibility, large \(\mathcal X_\epsilon\) is bad: It means that quite different parameter values are almost as plausible as the most plausible parameter value. |