Premium
Lagrangian dual coordinatewise maximization algorithm for network transportation problems with quadratic costs
Author(s) -
Ohuchi Azuma,
Kaji Ikuo
Publication year - 1984
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230140404
Subject(s) - mathematical optimization , dual (grammatical number) , convexity , mathematics , function (biology) , maximization , quadratic equation , lagrangian , convex function , differentiable function , regular polygon , computer science , art , mathematical analysis , geometry , literature , evolutionary biology , financial economics , economics , biology
This paper gives the Lagrangian dual coordinatewise maximization (LDCM) algorithm for network transportation problems with strictly convex quadratic costs (NTPQ). An explicit expression for the dual function associated with NTPQ is obtained. Some properties of the dual function are shown. Then, using these properties, a procedure which involves successively maximizing the dual function with respect to each of its dual coordinates is applied to obtain the optimal dual solution. Then the optimal primal solution is obtained by substituting the dual solution to the simple expression. Computational results for 200 randomly generated problems reveal the effectiveness of the algorithm. The key idea of applying the Lagrangian dual method to NTPQ is that the objective function of the network problems is strictly convex. This strict convexity allows one to finesse problems that occur in using Lagrangian methods with more general problems. In particular, because the optimal solution of the Lagrangian problem is unique, the dual function is differentiable and an optimal solution to the Lagrangian with optimal multipliers is optimal in the original primal problem. These are strong results that are not true in general.