Approximate optimality conditions and stopping criteria in canonical DC programming

Abstract

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 non-convex optimization problem, which 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 of the CDC problem. We develop conditions ensuring that this is the case; 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.

Keywords:

• DC problems
• approximate optimality conditions
• value function
• Lipschitz property

AMS Subject Classification :

• 90C26
• 90C46

Acknowledgements

The work has been partially supported by the grant PRIN 2007 9PLLN7 ‘Nonlinear Optimization, Variational Inequalities and Equilibrium Problems’.