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

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.

Recommendations

Cites work

Cited in

(4)

This page was built for publication: A generalized Dantzig-Wolfe decomposition principle for a class of nonconvex programming problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1321648)