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 modified 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.