Abstract
Motivated by recent interest in group-symmetry in semidefinite programming, we propose a numerical method for finding a finest simultaneous block-diagonalization of a finite number of matrices, or equivalently the irreducible decomposition of the generated matrix \({*}\)-algebra. The method is composed of numerical-linear algebraic computations such as eigenvalue computation, and automatically makes full use of the underlying algebraic structure, which is often an outcome of physical or geometrical symmetry, sparsity, and structural or numerical degeneracy in the given matrices. The main issues of the proposed approach are presented in this paper under some assumptions, while the companion paper gives an algorithm with full generality. Numerical examples of truss and frame designs are also presented.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Bai Y., de Klerk E., Pasechnik D.V., Sotirov R.: Exploiting group symmetry in truss topology optimization. Optim. Eng. 10, 331–349 (2009)
Barker G.P., Eifler L.Q., Kezlan T.P.: A non-commutative spectral theorem. Linear Algebra Appl. 20, 95–100 (1978)
Borchers B.: CSDP 2.3 user’s guide, a C library for semidefinite programming. Optim. Methods Softw. 11 & 12, 597–611 (1999)
de Klerk E., Pasechnik D.V., Schrijver A.: Reduction of symmetric semidefinite programs using the regular \({*}\)-representation. Math. Program. Ser. B 109, 613–624 (2007)
de Klerk E., Sotirov R.: Exploiting group symmetry in semidefinite relaxations of the quadratic assignment problem. Math. Program. Ser. A 122, 225–246 (2010)
Eberly W., Giesbrecht M.: Efficient decomposition of separable algebras. J. Symbol. Comput. 37, 35–81 (2004)
Gatermann K., Parrilo P.A.: Symmetry groups, semidefinite programs, and sums of squares. J. Pure Appl. Algebra 192, 95–128 (2004)
Gijswijt, D.: Matrix Algebras and Semidefimite Programming Techniques for Codes. Ph.D. thesis, University of Amsterdam (2005)
Henrion D., Lasserre J.B.: Convergent relaxations of polynomial matrix inequalities and static output feedback. IEEE Trans. Automat. Control 51, 192–202 (2006)
Hol, C.W.J., Scherer, C.W.: Sum of squares relaxations for polynomial semidefinite programming. In: Proceedings of Symposium on Mathematical Theory of Networks and Systems (MTNS), Leuven, Belgium (2004)
Jansson, L., Lasserre, J.B., Riener, C., Theobald, T.: Exploiting symmetries in SDP-relaxations for polynomial optimization. LAAS-report, Toulouse, September 2006
Kanno, Y., Ohsaki, M.: Eigenvalue Optimization of Structures via Polynomial Semidefinite Programming. METR 2007-31, Department of Mathematical Informatics, University of Tokyo (2007)
Kanno Y., Ohsaki M., Murota K., Katoh N.: Group symmetry in interior-point methods for semidefinite program. Optim. Eng. 2, 293–320 (2001)
Kojima, M.: Sums of squares relaxations of polynomial semidefinite programs. Research Report B-397, Tokyo Institute of Technology (November 2003)
Kojima, M., Kojima, S., Hara, S.: Linear algebra for semidefinite programming. Research Report B-290, Tokyo Institute of Technology (October 1994). Also in: RIMS Kokyuroku 1004, pp. 1–23, Kyoto University (1997)
Kojima M., Muramatsu M.: An extension of sums of squares relaxations to polynomial optimization problems over symmetric cones. Math. Program. 110, 315–336 (2007)
Kojima M., Muramatsu M.: A note on sparse SOS and SDP relaxations for polynomial optimization problems over symmetric cones. Comput. Optim. Appl. 42, 31–41 (2009)
Lam T.Y.: A First Course in Noncommutative Rings, 2nd edn. Springer, New York (2001)
Lamberti L., Pappalettere C.: An efficient sequential linear programming algorithm for engineering optimization. J. Eng. Des. 16, 353–371 (2005)
Lasserre J.B.: Global optimization with polynomials and the problems of moments. SIAM J. Optim. 11, 796–817 (2001)
Maehara, T., Murota, K.: A numerical algorithm for block-diagonal decomposition of matrix \({*}\)-algebras with general irreducible components. Jpn. J. Ind. Appl. Math. (2010, to appear)
Miller W. Jr: Symmetry Groups and Their Applications. Academic Press, New York (1972)
Nesterov Yu., Nemirovskii A.: Interior-Point Polynomial Algorithms in Convex Programming. SIAM, Philadelphia (1994)
Ohsaki M., Fujisawa K., Katoh N., Kanno Y.: Semi-definite programming for topology optimization of trusses under multiple eigenvalue constraints. Comput. Methods Appl. Mech. Eng. 180, 203–217 (1999)
Pólik, I.: Addendum to the SeDuMi user guide: version 1.1. Advanced Optimization Laboratory, McMaster University, Ontario (2005). http://sedumi.mcmaster.ca
Serre J.-P.: Linear Representations of Finite Groups. Springer, Berlin (1977)
Sturm J.F.: Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. Optim. Methods Softw. 11 & 12, 625–653 (1999)
Toh K.C., Todd M.J., Tütüncü R.H.: SDPT3—a MATLAB software package for semidefinite programming, version 1.3. Optim. Methods Softw. 11 & 12, 545–581 (1999)
Vallentin F.: Symmetry in semidefinite programs. Linear Algebra Appl. 430, 360–369 (2009)
Waki, H., Kim, S., Kojima, M., Muramatsu, M., Sugimoto, H.: SparsePOP: a sparse semidefinite programming relaxation of polynomial optimization problems. ACM Trans. Math. Softw. 35(15), (2008)
Wedderburn, J.H.M.: Lectures on Matrices. American Mathematical Society, New York (1934); Dover, Mineola (2005)
Wolkowicz H., Saigal R., Vandenberghe L.: Handbook of Semidefinite Programming: Theory, Algorithms, and Applications. Kluwer, Boston (2000)
Yamashita M., Fujisawa K., Kojima M.: Implementation and evaluation of SDPA6.0 (SemiDefinite Programming Algorithm 6.0). Optim. Methods Softw. 18, 491–505 (2003)
Yang B.: Stress, Strain, and Structural Dynamics. Academic Press, Burlington (2005)
Author information
Authors and Affiliations
Corresponding author
Additional information
The first draft of this paper appeared as the technical report “A numerical algorithm for block-diagonal decomposition of matrix \({*}\)-algebras,” issued in September 2007 as METR 2007-52, Department of Mathematical Informatics, University of Tokyo, and also as Research Report B-445, Department of Mathematical and Computing Sciences, Tokyo Institute of Technology.
About this article
Cite this article
Murota, K., Kanno, Y., Kojima, M. et al. A numerical algorithm for block-diagonal decomposition of matrix \({*}\)-algebras with application to semidefinite programming. Japan J. Indust. Appl. Math. 27, 125–160 (2010). https://doi.org/10.1007/s13160-010-0006-9
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s13160-010-0006-9