A generalized Dantzig-Wolfe decomposition principle for a class of nonconvex programming problems (Q1321648)

The authors consider the d.c. optimization problem \(f(x)\to \min h_ i(x)\leq g(x)\), \(i=1,2,\dots,m\), \(x\in X\), where \(f\), \(h_ i\), \(g\) are finite convex functions on the closed convex set \(X\). Using the generalized slater condition \(\inf_{x\in X}\max_{u\in \partial(h- g)(\bar x)}\langle u,x-\bar x\rangle<0\), (\(\partial(h- g)(\bar x)\) denotes Clarke's subdifferential) it is shown (Theorem 2) that \[ d(x):= \sum_{i=1}^ m \lambda_ i h_ i(x)+\langle u,x\rangle+ \alpha,\;u\in\mathbb{R}^ n,\;\alpha \in\mathbb{R},\;\lambda_ i\geq 0, \] is an optimal price function. \(d(x)\) is called an optimal price function iff any vector \(\bar x\in X\) satisfying \[ f(\bar x)+ d(\bar x)= \min_{x\in X} (f(x)+ d(x)),\;d(\bar x)= 0,\;h_ j(\bar x)\leq g(\bar x) \] is a solution of the reviewer. With the dual \(F(u)\to\min u\in\text{dom }g^*\) such that \(F(u):= \inf\{f(x)\mid h_ i(x)\leq\langle x,u\rangle- g^*(u)\), \(i= 1,2,\dots, m\), \(x\in X\}\) strong duality holds, i.e. \(\min(1)= \min(2)\). The relaxation \[ G(x,t):= \inf \{f(x)\mid h_ i(x)\leq \langle x,u\rangle- t,\;i= 1,2,\dots,m,\;x\in X\} \] of \(F(u)\) yields the equivalent quasiconcave optimization problem \(G(u,t)\to\min g^*(u)\leq t\), \(u\in \text{dom }g^*\). Combining approximation schemes for the solving of the reviewer with some dual-primal algorithm and the computation of the function \(G(u,t)\) they get a finite algorithm determining an \(\varepsilon\)-solution for separable programming problems of the type of the reviewer. In the realization cutting plane methods are used. This new method seems to be efficient at least for the above nonconvex separable programming problems to find the global optimal solution.