Modified partial duality theorem and Gradient Shift Coordination method

Although it is possible to solve large scale linear programming and linear steady state control problems hierarchically via convexifying the problem by using Bertsekas’ convexification method, the convergence of the Interaction Balance Method (IBM) tends to be very slow. In this paper, a modified partial duality theorem is introduced and thoroughly proved. To cope with the duality gap a double duality theorem is established. Based on these theorems a Gradient Shift Coordination method (GSC) is derived. The main advantage of this method over IBM is that the convergence is superlinear. A simulation is provided to demonstrate the feature of the algorithm.