On solving a d.c. programming problem by a sequence of linear programs (Q1186273)

Consider the problem of finding the global minimum of the difference of two convex functions over a closed convex set in \(R^ n\), that is \[ \text{glob }\min(f(x)-g(x))\quad\text{s.t. } h_ j(x)\leq 0\;(j=1,\dots,J),\tag{P} \] where \(f\), \(g\), \(h_ j\) are finite convex functions on \(R^ n\). Problem (P) is usually called a d.c. optimization problem and general properties have been investigated by \textit{J.-B. Hiriart-Urruty} [in: Convexity and duality in optimization, Proc. Symp., Groningen/Neth. 1984, Lect. Notes Econ. Math. Syst. 256, 37-70 (1985; Zbl 0591.90073)], by \textit{Hoang Tuy} [Math. Program. Study 30, 150-182 (1987; Zbl 0619.90061)], \textit{P. M. Pardalos} and \textit{J. B. Rosen} [``Constrained global optimization: algorithms and applications'' (1987; Zbl 0638.90064)] and by the first, second and third author [Ann. Oper. Res. 25, No. 1-4, 1-18 (1990; Zbl 0717.90057)]. It can be transformed by introducing an additional variable \(t\) into the equivalent concave minimization problem \[ \text{glob }\min(t-g(x))\quad\text{s.t. } f(x)\leq t,\;h_ j(x)\leq 0\;(j=1,\dots,J).\leqno(CP) \] For solving the (CP) problem branch and bounds methods or outer approximation procedures have been proposed, but these techniques have proved to be numerically expensive. An algorithm by the first and third author and \textit{H. P. Benson} [Math. Program., Ser. A 50, No. 2, 259-274 (1991; Zbl 0734.90092)] which combines both techniques has successfully overcome some drawbacks. Following this attempt, a new algorithm is presented, which shows to be numerically more appealing. The authors prove the convergence of the new procedure and report some numerical results.