Extending the descent-ascent algorithm to constrained difference of convex programming

Abstract We investigate Difference of Convex (DC) constrained optimization problems where both the objective function and the constraints are DC and nonsmooth. The problem has applications in a variety of fields, including quadratic programs with complementarity constraints and classification in Machine Learning. We introduce the Constrained Descent-Ascent DC algorithm (CDADC) which generalizes the standard Descent-Ascent framework to incorporate DC constraints using a piecewise affine approximation strategy. The algorithm utilizes the bundle technique to construct models for both the objective and constraint functions. It solves a sequence of convex quadratic subproblems designed to balance objective improvement, proximity to the current iterate, and constraint fulfilment. CDADC avoids evaluation of the objective function’s concave part and, to minimize computational effort, implements bundle resetting whenever a serious step is achieved. We demonstrate finiteness and convergence of the algorithm to a point that satisfies a criterion associated with the B-stationarity notion. The algorithm’s behaviour is illustrated through a couple of numerical examples