Approximate optimality conditions and stopping criteria in canonical DC programming

Giancarlo Bigi, Antonio Frangioni and Qinghua Zhang


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

My Home Page