Initialization of the Difference of Convex Functions Optimization Algorithm for Nonconvex Quadratic Problems

Abstract

The Difference of Convex functions Algorithm (DCA) is used to solve nonconvex optimization problems, specifically quadratic programming ones, generally by finding approximate solutions. DCA efficiency depends on two basic parameters that directly affect the speed of its convergence towards the optimal solution. The first parameter is the selected decomposition and the second is the assigned initial point. The aim of this study was to create a new algorithm that allows overcoming the need for a pre-selected initial estimate of the DCA. To achieve this aim, we performed an experimental study with 107 test problems using an implementation framework with MATLAB. Assessment was based on key performance indicators: $(a)$ the time required to reach the initial point and solution and $(b)$ the number of iterations. We selected three initial points, the first ($x_0^{lin}$) is the minimum of the linear part of the nonconvex quadratic problem (NCQP), the second ($x_0^{cvx}$) is the approximate global minimum of the convex part, and the third ($x_0^{cve}$) is the approximate global minimum of the concave part. We compared between the minimuma computed by DCA for each of the three initial estimates. The results demonstrated clear advantage of the DCA algorithm with ($x_0^{lin}$). Based on this outcome, we constructed a novel algorithm called Initialized DCA (IDCA) that allows implementation of the DCA with the best initial estimate without the requirement for a pre-determined initial point.