Outer approximation algorithms for canonical DC problems

Giancarlo Bigi, Antonio Frangioni and Qinghua Zhang


Nonconvex optimization problems often arise from applications in engineering, economics and other fields. Often, these problems either have a natural formulation or can be reformulated as DC optimization problems, that is nonconvex problems where the objective function is the difference of two convex functions and the constraint can be expressed as the set difference of two convex sets. In turn, every DC optimization problem can be reduced to the so-called canonical DC problem through standard transformations, which provide a linear objective function while preserving the structure of the constraint.
Several algorithms to solve the canonical DC problem have been proposed; many of them are modifications of the first cutting plane algorithm proposed by Tuy. In this paper, we consider the canonical DC problem relying on an alternative equivalent formulation based on a polar characterization of the constraint. We define a unified algorithmic framework for outer approximation type algorithms, which are based on an "oracle" for checking the global optimality conditions, and we study different sets of conditions which guarantee its convergence to an (approximated) optimal solution. As the oracle is the most computationally demanding part of the approach, we allow working with an approximated oracle which solves the related (nonconvex) optimization problem only approximately. Because of this, we briefly investigate approximate optimality conditions in order to derive bounds on the quality of the obtained solution. Our analysis identifies two main classes of approaches, which give rise to six different implementable algorithms, four of which can't be reduced to the original cutting plane algorithm by Tuy and its modifications.
The paper is organized as follows. In Section 2 the polar based reformulation of the canonical DC problem is introduced, and the well-known optimality conditions are recalled. In Section 3 we propose a notion of approximate oracle and we define corresponding approximate optimality conditions, investigating the relationships between the exact optimal value and the approximate optimal values. In Section 4 a thorough convergence analysis is carried out for the "abstract" unified algorithmic framework, and then six different implementable algorithms are proposed which fit within the framework. Finally, some conclusions are drawn in the last section.

The original paper is available at http://dx.doi.org/10.1007/s10898-009-9415-1. A Technical Report version is available here.

My Home Page