Abstract
We present a matrix scaling problem calledtruncated scaling and describe applications arising in economics, urban planning, and statistics. We associate a dual pair of convex optimization problems to the scaling problem and prove that the existence of a solution for the truncated scaling problem is characterized by the attainment of the infimum in the dual optimization problem. We show that optimization problems used by Bacharach (1970), Bachem and Korte (1979), Eaves et al. (1985), Marshall and Olkin (1968) and Rothblum and Schneider (1989) to study scaling problems can be derived as special cases of the dual problem for truncated scaling. We present computational results for solving truncated scaling problems using dual coordinate descent, thereby showing that truncated scaling provides a framework for modeling and solving large-scale matrix scaling problems.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
M. Bacharach,Biproportional Matrices and Input-Output Change (Cambridge University Press, London, 1970).
A. Bachem and B. Korte, “On the RAS algorithm,”Computing 23 (1979) 189–198.
M.L. Balinski and G. Demange, “An axiomatic approach to proportionality between matrices,” Technical Report, S.U.N.Y, Institute for Decision Sciences (Stony Brook, August 1987).
M.L. Balinski and G. Demange, “Algorithms for proportional matrices in reals and integers,”Mathematical Programming 45 (1989) 193–210.
R. Bapat and T.E.S. Raghavan, “An extension of a theorem of Darroch and Ratcliff in loglinear models and its application to scaling multidimensional matrices,”Linear Algebra and its Applications 114/115 (1989) 705–715.
T. Barker, F. Van der Ploeg and M. Weale, “A balanced system of national accounts for the United Kingdom,”The Review of Income and Wealth 30 (1984) 461–485.
D.P. Bertsekas, P.A. Hossein and Paul Tseng, “Relaxation methods for network flow problems with convex arc costs,”SIAM Journal of Control and Optimization 251 (1987) 1219–1243.
D.P. Bertsekas and J.N. Tsitsiklis,Parallel and Distributed Computation (Prentice-Hall, Englewood Cliffs, NY, 1989).
L.M. Bregman, “Proof of the convergence of Sheleikhovskii's method for a problem with transportation constraints,”USSR Computational Mathematics and Mathematical Physics 1 (1967) 191–204.
Y. Censor, “On linearly constrained entropy maximization,”Linear Algebra and its Applications 80 (1986) 191–195.
A. Drud, “Models for estimating social accounting matrices,” Technical Report, The World Bank (Washington, DC, 1985).
B.C. Eaves, A.J. Hoffman, U.G. Rothblum and H. Schneider, “Line-sum-symmetric scalings of square nonnegative matrices,”Mathematical Programming Studies 25 (1985) 1124–141.
T. Elfving, “On some methods for entropy maximization and matrix scaling,”Linear Algebra and its Applications 34 (1980) 321–339.
J. Eriksson, “A note on solution of large sparse maximum entropy problems with linear equality constraints,”Mathematical Programming 18 (1980) 146–154.
S. Erlander,Optimal Spatial Interaction and the Gravity Model. Lecture Notes in Economics and Mathematical Systems, Vol. 173 (Springer, Berlin, 1980).
L.R. Ford Jr. and D.R. Fulkerson,Flows in Networks (Princeton University Press, Princeton, NJ, 1962).
J. Franklin and J. Lorenz, “On the scaling of multidimensional matrices,”Linear Algebra and its Applications 114/115 (1989) 717–735.
R.S. Krupp, “Properties of Kruithof's projection method,”Bell System Technical Journal 58 (1979) 517–538.
A.W. Marshall and I. Olkin, “Scaling of matrices to achieve specified row and column sums,”Numerishe Mathematik 12 (1968) 83–90.
R.E. Miller and P.D. Blair,Input-Output Analysis: Foundations and Extensions (Printice-Hall, Englewood Cliffs, NJ, 1985).
E.E. Osborne, “On pre-conditioning of matrices,”Journal of the Association of Computing Machinery 7 (1960) 338–345.
R.T. Rockafellar,Convex Analysis (Princeton University Press, Princeton, NJ, 1970).
R.T. Rockafellar,Network Flows and Monotropic Optimization (Wiley, New York, 1984).
U.G. Rothblum, “Generalized scalings satisfying linear equalities,”Linear Algebra and its Applications 114/115 (1989) 765–783.
U.G. Rothblum and H. Schneider, “Scaling of matrices which have prespecified row sums and column sums via optimization,”Linear Algebra and its Applications 114/115 (1989) 737–764.
M.H. Schneider, “Matrix scaling, entropy minimization, and conjugate duality (I): Positivity conditions,”Linear Algebra and its Applications 114/115 (1989) 785–813.
M.H. Schneider and S.A. Zenios, “A comparative study of algorithm for matrix balancing,” to appear in:Operations Research (1990).
P. Tseng, “Dual ascent methods for problems with strictly convex costs and linear constraints: A unified approach,” Technical Report LIDS-P-1792, MIT, Center for Intelligent Control Systems (Cambridge, MA, 1989).
P. Tseng and D.P. Bertsekas, “Relaxation methods for problems with strictly convex separable costs and linear constraints,”Mathematical Programming 38 (1987) 303–321.
S.A. Zenios, “A note on the solution of very large matrix balancing problems,” Decision Sciences Working Paper 88-09-02, The Wharton School, University of Pennsylvania (Philadelphia, PA, 1988).
Author information
Authors and Affiliations
Additional information
Research supported in part by NSF grants ECS 8718971 and ECS 8943458.
Rights and permissions
About this article
Cite this article
Schneider, M.H. Matrix scaling, entropy minimization, and conjugate duality (II): The dual problem. Mathematical Programming 48, 103–124 (1990). https://doi.org/10.1007/BF01582253
Issue Date:
DOI: https://doi.org/10.1007/BF01582253