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

Since Dantzig-Wolfe’s pioneering contribution, the decomposition approach using a pricing mechanism has been developed for a wide class of mathematical programs. For convex programs a linear space of Lagrangean multipliers is enough to define price functions. For general mathematical programs the price functions could be defined by using a subclass of nondecreasing functions. However the space of non-decreasing functions is no longer finite dimensional. In this paper the authors consider a specific nonconvex optimization problem min{f(x):hj(x)•g(x),j=1,...,m,x∈X∈, where f(ë), hj(ë) and g(ë) are finite convex functions and X is a closed convex set. They generalize optimal price functions for this problem in such a way that the parameters of generalized price functions are defined in a finite dimensional space. Combining convex duality and a nonconvex duality the authors can develop a decomposition method to find a globally optimal solution.