Approximate optimality conditions and stopping criteria in canonical DC programming
Giancarlo Bigi, Antonio Frangioni and Qinghua Zhang
Summary
In this paper we study approximate optimality conditions
for the Canonical DC (CDC) optimization problem and their
relationships with stopping criteria for a large class of
solution algorithms for the problem. In fact, global
optimality conditions for CDC are very often restated in
terms of a nonconvex optimization problem, that has to be
solved each time the optimality of a given tentative solution
has to be checked. Since this is in principle a costly task,
it makes sense to only solve the problem approximately,
leading to an inexact stopping criteria and therefore to
approximate optimality conditions. In this framework, it is
important to study the relationships between the approximation
in the stopping criteria and the quality of the solutions that
the corresponding approximated optimality conditions may
eventually accept as optimal, in order to ensure that a small
tolerance in the stopping criteria does not lead to a
disproportionally large approximation of the optimal value.
To this aim, we consider an alternative
equivalent formulation of the CDC problem, which
is based on a polar characterization
of the nonconvex constraint. This formulation allows to express
the optimality conditions in a geometric fashion such that
their ``optimization version'', which has already been exploited in
some algorithmic schemes, does not involve any representation of
the reverse-convex constraint set through a convex function.
We discuss the polar formulation and the corresponding optimality
conditions and we introduce the related approximate version that
can be exploited as a stopping criterion in algorithms.
We develop conditions ensuring that the approximation error of the
optimal value and the tolerance is linear; these turn out to be
closely related with the well-known concept of regularity of a CDC problem,
actually coinciding with the latter if the reverse-constraint
set is a polyhedron.
The original paper is available at http://dx.doi.org/10.1080/10556780903178048.
My Home Page