A Matrix Nearness Problem: What is the Nearest Doubly Stochastic Matrix to a given Matrix?

Pawoumodom L. Takouda

RAIRO - Operations Research (2010)

  • Volume: 39, Issue: 1, page 35-54
  • ISSN: 0399-0559

Abstract

top
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.

How to cite

top

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 39.1 (2010): 35-54. <http://eudml.org/doc/105321>.

@article{Takouda2010,
abstract = {
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. },
author = {Takouda, Pawoumodom L.},
journal = {RAIRO - Operations Research},
keywords = {Approximation matricielle; projections alternées.; matrix approximation; alternating projection method},
language = {fre},
month = {3},
number = {1},
pages = {35-54},
publisher = {EDP Sciences},
title = {Un problème d'approximation matricielle : quelle est la matrice bistochastique la plus proche d'une matrice donnée ?},
url = {http://eudml.org/doc/105321},
volume = {39},
year = {2010},
}

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
DA - 2010/3//
PB - EDP Sciences
VL - 39
IS - 1
SP - 35
EP - 54
AB - 
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.
LA - fre
KW - Approximation matricielle; projections alternées.; matrix approximation; alternating projection method
UR - http://eudml.org/doc/105321
ER -

References

top
  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. Theory79 (1994) 418–443.  Zbl0833.46011
  3. H. Bauschke and J. Borwein, On projection algorithms for solving convex feasibility problems. SIAM Rev.38 (1996) 367–426.  Zbl0865.47039
  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.  
  5. H. Brezis, Analyse fonctionnelle. Théories et Applications. Masson (1983).  Zbl0511.46001
  6. P. Combettes, Hilbertian convex feasibility problem: Convergence of projection methods. Appl. Math. Optim.35 (1997) 311–330.  Zbl0872.90069
  7. R. Escalante, Dykstra's algorithm for a constrained least-squares matrix problem. Numerical Linear Algebra Appl.3 (1996) 459–471.  Zbl0908.90207
  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.  Zbl0728.65034
  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.  Zbl0969.15007
  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.  Zbl0681.65029
  11. N.J. Higham, Computing the nearest correlation matrix – a problem from finance. IMA J. Numer. Anal.22 (2002) 329–343.  Zbl1006.65036
  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).  
  13. R.B. Horn and C.R. Johnson, Matrix Analysis. Cambridge University Press (1985). (Reprinted in 1991, 1992).  Zbl0576.15001
  14. R.N. Khoury, Closest matrices in the space of generalized doubly stochastic matrices. J. Math. Anal. Appl.222 (1998) 562–568.  Zbl0911.15013
  15. R. Rockafeller and R.J.-B. Wets, Variational Analysis. Grundlehren der mathematischen Wissenchaften 317. Springer-Verlag, Berlin, Heidelberg (1998).  
  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 : . Submitted.  URIhttp://mip.ups-tlse.fr/publi/2002.html
  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”, 41e année161 (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).  

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.