The general duality theory in mathematical programming has widened the concept of prices from the traditional linear prices or multipliers to the nonlinear price functions. The resulting major advantages can be stated in two respects. The first advantage is the reduction of the duality gap resulting from the release of the linear restriction on the optimal dual solutions. The second advantage of the general duality lies in the rich economic interpretations of the optimal price functions for the economic problems with nonconvexities. This thesis treats this general duality theory both from the viewpoints of solution methods and the concept of prices. Consequently we have two distinct purposes of this thesis, one for solution methods and the other for a new concept of price function.
Motivated from the recent developments of the decomposition methods using the general duality and price functions, we have tried to identify the relations between the primal decompositions and the dual decompositions. Unlike other studies of the same interest we have excluded the masterproblems and concentrated only on the subproblems. We have identified significant relations between the primal subproblems and dual subproblems even where there may exist a positive Lagrangean duality gap. We call these relations the epsilon-symmetric relations between the two decomposition methods. To test the validity of our results we have selected a special class of mixed integer programs and the results have been encouraging.
The study on the concept of a price function in this thesis generalizes the concept of average shadow prices, first developed for integer programming, to general mathematical programming. We have defined the average shadow price for a given activity and the concept of average price function. We have identified some relating properties of them and discussed rich economic interpretations involved. Furthermore we have suggested some practical procedures of obtaining the upper bounds and lower bounds of the average shadow prices and discussed the convergence of a theoretical algorithm to compute the exact values of them. As a significant by-product of our average price function, we have found that the average analysis well fits the general duality framework. These have resulted in a construction of a new general dual problem which provides the strong duality theorem for mathematical programming in general. We have constructed the new general dual problem and proved the strong duality theorems by using the concept of the average price function. The new dual problem has reduced the total class of price functions into much smaller one irrespective of special areas of mathematical programming. This may be the start of the new average duality theory in contrast with the traditional (marginal) duality theory.
