On covering method for d.c. optimization. (Q5928427)

The authors consider the problem to maximize a d.c. function \(f\) over a polytope \(X\). It is assumed that the decomposition of \(f\) into two convex functions is known, i.e. \(f(x)=f_1(x)+f_2(x)\) where \(f_1(x)\) is convex and \(f_2(x)\) is concave on an open set containing \(X\). If this problem is solved by a covering algorithm one may use the convex bounding functions \(k_i(x):=f_1(x)+(f_2(x_i)+ \xi_2(x_i)'(x-x_i))\) where \(\xi_2(x_i)\) is an arbitrary subgradient of \(f_2\) at \(x_i\). In this case the subproblem \(\max_{x \in X}\min_{1 \leq i \leq n}k_i(x)\) can be formulated as a convex maximization problem with linear constraints. For solving this subproblem power diagrams may be helpful. Computational results on 3 multidimensional test problems are reported.