Implementation of The Extended Dantzig – Wolfe Method

Abstract

In this paper implementation of the extended Dantzig - Wolfe method to solve a general quadratic programming problem is presented ,that is, obtaining a local minimum of a quadratic function subject to inequality constraints. The method terminates successfully at a KT point in a finite number of steps.  No extra effort is needed when the function is non-convex.

The method solve convex quadratic programming problems.  It is a simplex like procedure to the Dantzig - Wolfe method[1].   So, it is, the same as the Dantzig – Wolfe method when the Hessian matrix of the quadratic function is positive definite[7].

The obvious difference between our method and the Dnatzig – Wolfe method is in the possibility of decreasing the complement of the new variable that has just become non-basic.

In the practical implementation of the method we inherit the computational features of the active set methods using the matrices H, U and T, and in particular the stable features [5]. The features (i.e, the stable features) are achieved by using orthogonal factorizations of the matrix of active constraints when the tableau is complementary.