We consider solving a group of dual optimization problems that share a core structure: Every primal problem of the group is obtained by the right-hand side variation of constraints in the original primal problem, while the other core part of the original primal problem, such as the objective and the left-hand side of the constraints, are kept fixed.
Since evaluations of the dual function are usually expensive in dual optimization, many algorithms are designed to reduce evaluations.
However, they are tailored to solve one dual problem. We propose a framework of algorithms based on cutting plane methods to reduce total evaluations for multiple dual optimization problems.
In the proposed algorithms, we construct a tree of evaluation points in which a route from the root node to a leaf node corresponds to a sequence of evaluation points for one dual problem, and the root node corresponds to an initial point that is common for all dual problems. Since essential parts of the evaluations are invariable among the group of dual problems, we can reuse the information. Our numerical experiments endorse the efficiency of the proposed algorithms.