×

A matrix approximation problem: what doubly stochastic matrix is closest to a given matrix. (Un problème d’approximation matricielle: quelle est la matrice bistochastique la plus proche d’une matrice donnée?) (French. English summary) Zbl 1102.90043

Summary: We are interested in the doubly stochastic matrix nearness problem, namely to find and element of the set of doubly stochastic \(n\times n\) matrices which is closest to a given real \(n\times n\) matrix. Instances of this problem occur in different fields: aggregation of preferences in operational research, calculus of variations and shape optimisation, etc. We propose here a direct study via the projection theorem and a numerical resolution inspired by the alternating projection algorithm of Boyle-Dykstra.

MSC:

90C25 Convex programming
15B51 Stochastic matrices
PDFBibTeX XMLCite
Full Text: DOI Numdam EuDML

References:

[1] H. Bauschke , Projections Algorithms and Monotone Operators . Ph.D. thesis, Simon Fraser University ( 1996 ).
[2] H. Bauschke and J. Borwein , Dykstra’s alternating projection algorithm for two sets . J. Approx. Theory 79 ( 1994 ) 418 - 443 . Zbl 0833.46011 · Zbl 0833.46011 · doi:10.1006/jath.1994.1136
[3] H. Bauschke and J. Borwein , On projection algorithms for solving convex feasibility problems . SIAM Rev. 38 ( 1996 ) 367 - 426 . Zbl 0865.47039 · Zbl 0865.47039 · doi:10.1137/S0036144593251710
[4] J.P. Boyle and R.L. Dykstra , A method for finding projections onto the intersection of convex sets in Hilbert spaces , in Advances in Order Restricted Statistical Inference, edited by R.L. Dykstra, T. Robertson and F.T. Wright. Springer-Verlag. Lect. Notes Statist. ( 1985 ) 28 - 47 . Zbl 0603.49024 · Zbl 0603.49024
[5] H. Brezis , Analyse fonctionnelle . Théories et Applications. Masson ( 1983 ). MR 697382 | Zbl 0511.46001 · Zbl 0511.46001
[6] P. Combettes , Hilbertian convex feasibility problem: Convergence of projection methods . Appl. Math. Optim. 35 ( 1997 ) 311 - 330 . Zbl 0872.90069 · Zbl 0872.90069 · doi:10.1007/BF02683333
[7] R. Escalante , Dykstra’s algorithm for a constrained least-squares matrix problem . Numerical Linear Algebra Appl. 3 ( 1996 ) 459 - 471 . Zbl 0908.90207 · Zbl 0908.90207 · doi:10.1002/(SICI)1099-1506(199611/12)3:6<459::AID-NLA82>3.0.CO;2-S
[8] W. Glunt , T. Hayden , S. Hong and J. Wells , An alternating projection algorithm for computing the nearest Euclidian distance matrix . SIAM J. Matrix Anal. Appl. 11 ( 1990 ) 589 - 600 . Zbl 0728.65034 · Zbl 0728.65034 · doi:10.1137/0611042
[9] W. Glunt , T. Hayden and R. Reams , The nearest “doubly stochastic” matrix to a real matrix with the same first moment . Numer. Linear Algebra Appl. 5 ( 1998 ) 475 - 482 . Zbl 0969.15007 · Zbl 0969.15007 · doi:10.1002/(SICI)1099-1506(199811/12)5:6<475::AID-NLA155>3.0.CO;2-5
[10] N.J. Higham , Matrix nearness problems and applications . In Applications of Matrix Theory, edited by M.J.C. Gover and S. Barnett. Oxford University Press ( 1989 ) 1 - 27 . Zbl 0681.65029 · Zbl 0681.65029
[11] N.J. Higham , Computing the nearest correlation matrix - a problem from finance . IMA J. Numer. Anal. 22 ( 2002 ) 329 - 343 . Zbl 1006.65036 · Zbl 1006.65036 · doi:10.1093/imanum/22.3.329
[12] J.-B. Hiriart-Urruty and C. Lemaréchal , Convex analysis and minimization algorithms . Grundlehren der mathematischen Wissenchaften 305 & 306. Springer-Verlag, Berlin, Heidelberg ( 1993 ). (New printing in 1996). Zbl 0795.49002 · Zbl 0795.49002
[13] R.B. Horn and C.R. Johnson , Matrix Analysis . Cambridge University Press ( 1985 ). (Reprinted in 1991, 1992). MR 832183 | Zbl 0576.15001 · Zbl 0576.15001 · doi:10.1017/CBO9780511810817
[14] R.N. Khoury , Closest matrices in the space of generalized doubly stochastic matrices . J. Math. Anal. Appl. 222 ( 1998 ) 562 - 568 . Zbl 0911.15013 · Zbl 0911.15013 · doi:10.1006/jmaa.1998.5970
[15] R. Rockafeller and R.J.-B. Wets , Variational Analysis . Grundlehren der mathematischen Wissenchaften 317. Springer-Verlag, Berlin, Heidelberg ( 1998 ). MR 1491362 | Zbl 0888.49001 · Zbl 0888.49001 · doi:10.1007/978-3-642-02431-3
[16] P. Takouda , Un problème d’approximation matricielle : quelle est la matrice bistochastique la plus proche d’une matrice donnée ? Technical report, Laboratoire MIP, Université Paul Sabatier, Toulouse 3, 2002. Research Report MIP 02 - 21 . Accessible on the web at the url : http://mip.ups-tlse.fr/publi/2002.html. Submitted.
[17] P. Takouda , Problèmes d’approximations matricielle linéaire conique : approches par projections et via optimisation sous contraintes de semi-définie positivité . Ph.D. thesis, Université Paul Sabatier - Toulouse III (Septembre 2003).
[18] P. Takouda , Résolution d’un problème d’agrégation de préférence en approximant par des matrices bistochastiques . Mathématiques et Sciences Humaines, “Recherche opérationnelle et aide à la décision”, 41\(^e\) année 161 ( 2003 ) 77 - 97 . Aussi rapport interne numéro 03 - 08 , du laboratoire MIP de l’Université Paul Sabatier, Toulouse.
[19] E. Zarantonello , Projections on convex sets in Hilbert spaces and spectral theory , in Contributions to Nonlinear Functionnal Analysis, edited by E.E. Zarantonello, number 27 in University of Wisconsin. Mathematics Research Center Publications, Academic Press, New york ( 1971 ) 1 - 38 . Proceeding on the special session on Optimization and Nonlinear Analysis, Jerusalem (May 1995). Zbl 0281.47043 · Zbl 0281.47043
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.