Un problème d'approximation matricielle : quelle est la matrice bistochastique la plus proche d'une matrice donnée ?
RAIRO - Operations Research - Recherche Opérationnelle, Tome 39 (2005) no. 1, pp. 35-54.

Nous nous intéressons dans ce travail au problème d'approximation d'une matrice donnée par une matrice bistochastique. Des instances de ce problème peuvent apparaître dans différents domaines : en recherche opérationnelle dans un problème d'agrégation de préférence, en calcul de variations et optimisation de forme entre autres. Nous en proposons dans cet article une étude directe via le théorème de projection et une résolution numérique inspirée par la méthode de projections alternées de Boyle-Dykstra.

We are interested in the following work in the doubly stochastic matrix nearness problem. Instances of this problems occurs in differents 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 projections algorithm of Boyle-Dykstra.

DOI : 10.1051/ro:2005003
Classification : 90C25
Mots-clés : approximation matricielle, projections alternées
@article{RO_2005__39_1_35_0,
     author = {Takouda, Pawoumodom L.},
     title = {Un probl\`eme d'approximation matricielle : quelle est la matrice bistochastique la plus proche d'une matrice donn\'ee ?},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {35--54},
     publisher = {EDP-Sciences},
     volume = {39},
     number = {1},
     year = {2005},
     doi = {10.1051/ro:2005003},
     zbl = {1102.90043},
     language = {fr},
     url = {http://www.numdam.org/articles/10.1051/ro:2005003/}
}
TY  - JOUR
AU  - Takouda, Pawoumodom L.
TI  - Un problème d'approximation matricielle : quelle est la matrice bistochastique la plus proche d'une matrice donnée ?
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2005
SP  - 35
EP  - 54
VL  - 39
IS  - 1
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ro:2005003/
DO  - 10.1051/ro:2005003
LA  - fr
ID  - RO_2005__39_1_35_0
ER  - 
%0 Journal Article
%A Takouda, Pawoumodom L.
%T Un problème d'approximation matricielle : quelle est la matrice bistochastique la plus proche d'une matrice donnée ?
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2005
%P 35-54
%V 39
%N 1
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ro:2005003/
%R 10.1051/ro:2005003
%G fr
%F RO_2005__39_1_35_0
Takouda, Pawoumodom L. Un problème d'approximation matricielle : quelle est la matrice bistochastique la plus proche d'une matrice donnée ?. RAIRO - Operations Research - Recherche Opérationnelle, Tome 39 (2005) no. 1, pp. 35-54. doi : 10.1051/ro:2005003. http://www.numdam.org/articles/10.1051/ro:2005003/

[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

[3] H. Bauschke and J. Borwein, On projection algorithms for solving convex feasibility problems. SIAM Rev. 38 (1996) 367-426. | Zbl

[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

[5] H. Brezis, Analyse fonctionnelle. Théories et Applications. Masson (1983). | MR | Zbl

[6] P. Combettes, Hilbertian convex feasibility problem: Convergence of projection methods. Appl. Math. Optim. 35 (1997) 311-330. | Zbl

[7] R. Escalante, Dykstra's algorithm for a constrained least-squares matrix problem. Numerical Linear Algebra Appl. 3 (1996) 459-471. | Zbl

[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

[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

[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

[11] N.J. Higham, Computing the nearest correlation matrix - a problem from finance. IMA J. Numer. Anal. 22 (2002) 329-343. | Zbl

[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

[13] R.B. Horn and C.R. Johnson, Matrix Analysis. Cambridge University Press (1985). (Reprinted in 1991, 1992). | MR | Zbl

[14] R.N. Khoury, Closest matrices in the space of generalized doubly stochastic matrices. J. Math. Anal. Appl. 222 (1998) 562-568. | Zbl

[15] R. Rockafeller and R.J.-B. Wets, Variational Analysis. Grundlehren der mathematischen Wissenchaften 317. Springer-Verlag, Berlin, Heidelberg (1998). | MR | Zbl

[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 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

Cité par Sources :