Outer approximation algorithms for canonical DC problems
Giancarlo Bigi, Antonio Frangioni and Qinghua Zhang
Summary
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