Outer Approximation Algorithms for Canonical Reverse-Polar Problems

In this paper we propose a novel generalization of the canonical DC
problem and we study the convergence of outer approximation (cutting
planes) algorithms for its solution which use an “approximated” oracle for
checking the global optimality conditions to the problem. Although the
approximated optimality conditions are similar to those of the canonical
DC problem, the new class of Canonical Reverse Polar (CRP) problems is
shown to significantly differ from its special case. We also show that outer
approximation approaches for DC problems need be substantially modi-
fied in order to cope with (CRP); interestingly, some outer approximation
approaches for the latter cannot be applied to the formers, thus the more
general problem allows for novel algorithms. We develop a hierarchy of
conditions that guarantee the convergence of cutting plane algorithms;
relying on these conditions, we build four cutting plane algorithms for
solving (CRP), which seem to be new and cannot be reduced to each
other.