December  2018, 8(4): 413-440. doi: 10.3934/naco.2018026

Optimization problems with orthogonal matrix constraints

1. 

Department of Mathematics and Statistics, Wright State University, 3640 Colonel Glenn Highway Dayton, OH 45435, U.S.A

2. 

Department of Mathematics and Statistics, Air Force Institute of Technology, 2950 Hobson Way, Wright Patterson Air Force Base, OH 45433, USA

* Corresponding author: Manil T. Mohan

M. T. Mohan's current address Department of Mathematics, Indian Institute of Technology Roorkee-IIT Roorkee, Haridwar Highway, Roorkee, Uttarakhand 247 667, INDIA

Received  May 2017 Revised  August 2018 Published  September 2018

The optimization problems involving orthogonal matrices have been formulated in this work. A lower bound for the number of stationary points of such optimization problems is found and its connection to the number of possible partitions of natural numbers is also established. We obtained local and global optima of such problems for different orders and showed their connection with the Hadamard, conference and weighing matrices. The application of general theory to some concrete examples including maximization of Shannon, Rény, Tsallis and Sharma-Mittal entropies for orthogonal matrices, minimum distance orthostochastic matrices to uniform van der Waerden matrices, Cressie-Read and K-divergence functions for orthogonal matrices, etc are also discussed. Global optima for all orders has been found for the optimization problems involving unitary matrix constraints.

Citation: K. T. Arasu, Manil T. Mohan. Optimization problems with orthogonal matrix constraints. Numerical Algebra, Control & Optimization, 2018, 8 (4) : 413-440. doi: 10.3934/naco.2018026
References:
[1] P.-A. AbsilR. Mahony and R. Sepulchre, Optimization Algorithms on Matrix Manifolds, Princeton University Press, Princeton, NJ, 2008.  doi: 10.1515/9781400830244.  Google Scholar
[2]

K. T. Arasu, M. T. Mohan, A. Pathak and R. J. Ramya, Entropy optimal orthogonal matrices, Submitted for Journal Publication, 2018. Google Scholar

[3]

K. T. Arasu and M. T. Mohan, Entropy of orthogonal matrices and minimum distance orthostochastic matrices from the uniform van der Waerden matrix, Submitted for Journal Publication, 2018. Google Scholar

[4]

R. Bhatia, Matrix Analysis, Graduate Texts in Mathematics, Springer, New York, 1997 doi: 10.1007/978-1-4612-0653-8.  Google Scholar

[5]

O. Chterental and D. Ž. Ɖoković, On orthostochastic, unistochastic and qustochastic matrices, Linear Algebra and its Applications, 428 (2008), 1178-1201.  doi: 10.1016/j.laa.2007.09.022.  Google Scholar

[6]

N. Cressie and T. R. C. Read, Multinomial goodness of fit, Journal of the Royal Statistical Society, B, 46 (1984), 440-464.   Google Scholar

[7]

P. DelsarteJ. M. Goethals and J. J. Seidel, Orthogonal matrices with zero diagonal Ⅱ, Canadian Journal of Mathematics, ⅩⅩⅩⅢ (1971), 816-832.  doi: 10.4153/CJM-1971-091-x.  Google Scholar

[8]

A. EdelmanT. A. Arias and S. T. Smith, The geometry of algorithms with orthogonality constraints, SIAM Journal of Matrix Analysis and Applications, 20 (1999), 303-353.  doi: 10.1137/S0895479895290954.  Google Scholar

[9]

H. G. GadiyarK. M. Sangeeta MainiR. Padma and H. S. Sharatchandra, Entropy and Hadamard matrices, Journal of Physics A: Mathematical and General, 36 (2003), 109-112.  doi: 10.1088/0305-4470/36/7/103.  Google Scholar

[10]

J. Gallier, Basics of Classical Lie Groups: The Exponential Map, Lie Groups, and Lie Algebras, Chapter 14, in "Geometric Methods and Applications", the series Texts in Applied Mathematicsolume, 38 (2001), 367–414. doi: 10.1007/978-1-4613-0137-0_14.  Google Scholar

[11]

A. V. GeramitaJ. M. Geramita and J. Seberry, Orthogonal designs, Linear and Multilinear Algebra, 3 (1976), 381-206.  doi: 10.1080/03081087608817121.  Google Scholar

[12]

A. V. Geramita and J. Seberry, Orthogonal Designs: Quadratic Forms and Hadamard Matrices, Marcel Dekker, New York-Basel, 1979.  Google Scholar

[13]

B. K. P. Horn, Closed form solution of absolute orientation using unit quaternions, Journal of the Optical Society A, 4 (1987), 629-642.  doi: 10.1364/JOSAA.4.000629.  Google Scholar

[14]

Z. Q. Ma, Group Theory for Physicists, World Scientific, Singapore 2007. doi: 10.1142/6596.  Google Scholar

[15]

A. W. Marshall, I. Olkin and B. C. Arnold, Inequalities: Theory of Majorization and Its Applications, Springer Series in Statistics, New York, 2011. doi: 10.1007/978-0-387-68276-1.  Google Scholar

[16]

M. T. Mohan, On some p−almost Hadamard matrices, Accepted in Operators and Matrices, 2018. Google Scholar

[17]

H. Nakzato, Set of 3 × 3 orthostochastic matrices, Nihonkai Mathematics Journal, 7 (1996), 83-100.   Google Scholar

[18]

A. Nemirovski, Sums of random symmetric matrices and quadratic optimization under orthogonality constraints, Mathematical Programming, 109 (2007), 283-317.  doi: 10.1007/s10107-006-0033-0.  Google Scholar

[19]

J. Nocedal and S. J. Wright, Numerical Optimization, Springer Series in Operations Research and Financial Engineering, 2nd ed. Springer, New York, 2006  Google Scholar

[20]

R. E. A. C. Paley, On orthogonal matrices, Journal of Mathematics and Physics, 12 (1933), 311-320.  doi: 10.1002/sapm1933121311.  Google Scholar

[21]

D. R. Stinson Combinatorial Designs: Constructions and Analysis, Springer-Verlag New York, Inc., 2004.  Google Scholar

[22]

B. D. Sharma and D. P. Mittal, New non-additive measures of entropy for discrete probability distributions, Journal of Mathematical Sciences, 10 (1975), 28-40.   Google Scholar

[23]

F. Szöllősi, Construction, classification and parametrization of complex Hadamard matrices, PhD Thesis, https://arXiv.org/abs/1110.5590, 2011. Google Scholar

[24]

V. WeberJ. Vande VondeleJ. Hütter and A. M. Niklasson, Direct energy functional minimization under orthogonality constraints, The Journal of Chemical Physics, 128 (2008), 84-113.  doi: 10.1063/1.2841077.  Google Scholar

[25]

Z. Wen and W. Yin, A feasible method for optimization with orthogonality constraints, Math. Program., Ser. A, 142 (2013), 397-434.  doi: 10.1007/s10107-012-0584-1.  Google Scholar

[26]

K. ŻyczkowskiM. KuśW. Słomczyński and H.-J. Sommers, Random unistochastic matrices, Journal of Physics A: Mathematical and General, 36 (2003), 3425-3450.  doi: 10.1088/0305-4470/36/12/333.  Google Scholar

show all references

References:
[1] P.-A. AbsilR. Mahony and R. Sepulchre, Optimization Algorithms on Matrix Manifolds, Princeton University Press, Princeton, NJ, 2008.  doi: 10.1515/9781400830244.  Google Scholar
[2]

K. T. Arasu, M. T. Mohan, A. Pathak and R. J. Ramya, Entropy optimal orthogonal matrices, Submitted for Journal Publication, 2018. Google Scholar

[3]

K. T. Arasu and M. T. Mohan, Entropy of orthogonal matrices and minimum distance orthostochastic matrices from the uniform van der Waerden matrix, Submitted for Journal Publication, 2018. Google Scholar

[4]

R. Bhatia, Matrix Analysis, Graduate Texts in Mathematics, Springer, New York, 1997 doi: 10.1007/978-1-4612-0653-8.  Google Scholar

[5]

O. Chterental and D. Ž. Ɖoković, On orthostochastic, unistochastic and qustochastic matrices, Linear Algebra and its Applications, 428 (2008), 1178-1201.  doi: 10.1016/j.laa.2007.09.022.  Google Scholar

[6]

N. Cressie and T. R. C. Read, Multinomial goodness of fit, Journal of the Royal Statistical Society, B, 46 (1984), 440-464.   Google Scholar

[7]

P. DelsarteJ. M. Goethals and J. J. Seidel, Orthogonal matrices with zero diagonal Ⅱ, Canadian Journal of Mathematics, ⅩⅩⅩⅢ (1971), 816-832.  doi: 10.4153/CJM-1971-091-x.  Google Scholar

[8]

A. EdelmanT. A. Arias and S. T. Smith, The geometry of algorithms with orthogonality constraints, SIAM Journal of Matrix Analysis and Applications, 20 (1999), 303-353.  doi: 10.1137/S0895479895290954.  Google Scholar

[9]

H. G. GadiyarK. M. Sangeeta MainiR. Padma and H. S. Sharatchandra, Entropy and Hadamard matrices, Journal of Physics A: Mathematical and General, 36 (2003), 109-112.  doi: 10.1088/0305-4470/36/7/103.  Google Scholar

[10]

J. Gallier, Basics of Classical Lie Groups: The Exponential Map, Lie Groups, and Lie Algebras, Chapter 14, in "Geometric Methods and Applications", the series Texts in Applied Mathematicsolume, 38 (2001), 367–414. doi: 10.1007/978-1-4613-0137-0_14.  Google Scholar

[11]

A. V. GeramitaJ. M. Geramita and J. Seberry, Orthogonal designs, Linear and Multilinear Algebra, 3 (1976), 381-206.  doi: 10.1080/03081087608817121.  Google Scholar

[12]

A. V. Geramita and J. Seberry, Orthogonal Designs: Quadratic Forms and Hadamard Matrices, Marcel Dekker, New York-Basel, 1979.  Google Scholar

[13]

B. K. P. Horn, Closed form solution of absolute orientation using unit quaternions, Journal of the Optical Society A, 4 (1987), 629-642.  doi: 10.1364/JOSAA.4.000629.  Google Scholar

[14]

Z. Q. Ma, Group Theory for Physicists, World Scientific, Singapore 2007. doi: 10.1142/6596.  Google Scholar

[15]

A. W. Marshall, I. Olkin and B. C. Arnold, Inequalities: Theory of Majorization and Its Applications, Springer Series in Statistics, New York, 2011. doi: 10.1007/978-0-387-68276-1.  Google Scholar

[16]

M. T. Mohan, On some p−almost Hadamard matrices, Accepted in Operators and Matrices, 2018. Google Scholar

[17]

H. Nakzato, Set of 3 × 3 orthostochastic matrices, Nihonkai Mathematics Journal, 7 (1996), 83-100.   Google Scholar

[18]

A. Nemirovski, Sums of random symmetric matrices and quadratic optimization under orthogonality constraints, Mathematical Programming, 109 (2007), 283-317.  doi: 10.1007/s10107-006-0033-0.  Google Scholar

[19]

J. Nocedal and S. J. Wright, Numerical Optimization, Springer Series in Operations Research and Financial Engineering, 2nd ed. Springer, New York, 2006  Google Scholar

[20]

R. E. A. C. Paley, On orthogonal matrices, Journal of Mathematics and Physics, 12 (1933), 311-320.  doi: 10.1002/sapm1933121311.  Google Scholar

[21]

D. R. Stinson Combinatorial Designs: Constructions and Analysis, Springer-Verlag New York, Inc., 2004.  Google Scholar

[22]

B. D. Sharma and D. P. Mittal, New non-additive measures of entropy for discrete probability distributions, Journal of Mathematical Sciences, 10 (1975), 28-40.   Google Scholar

[23]

F. Szöllősi, Construction, classification and parametrization of complex Hadamard matrices, PhD Thesis, https://arXiv.org/abs/1110.5590, 2011. Google Scholar

[24]

V. WeberJ. Vande VondeleJ. Hütter and A. M. Niklasson, Direct energy functional minimization under orthogonality constraints, The Journal of Chemical Physics, 128 (2008), 84-113.  doi: 10.1063/1.2841077.  Google Scholar

[25]

Z. Wen and W. Yin, A feasible method for optimization with orthogonality constraints, Math. Program., Ser. A, 142 (2013), 397-434.  doi: 10.1007/s10107-012-0584-1.  Google Scholar

[26]

K. ŻyczkowskiM. KuśW. Słomczyński and H.-J. Sommers, Random unistochastic matrices, Journal of Physics A: Mathematical and General, 36 (2003), 3425-3450.  doi: 10.1088/0305-4470/36/12/333.  Google Scholar

Figure 1.  n versus d graph
Figure 2.  Rényi entropy of $2\times 2$ orthogonal matrices
Figure 3.  Sharma-Mittal entropy of $2\times 2$ orthogonal matrices
Figure 4.  Tsallis entropy of $2\times 2$ orthogonal matrices
Table 1.  1 $\leq n\leq $ 20.
$n$ Orthogonal matrix $d({\rm J}_n, {\rm B}_n)$ $n$ Orthogonal matrix $d({\rm J}_n, {\rm B}_n)$
$1$ ${\rm H}_1$ $0$ $11$ $\frac{1}{3}{\rm C}_{10}\oplus{\rm H}_1^*$ $1.054$
$2$ $\frac{1}{\sqrt{2}}{\rm H}_2$ $0$ $12$ $\frac{1}{2\sqrt{3}}{\rm H}_{12}$ $0$
$3$ ${\rm K}_3$ $0.471$ $13$ $\frac{1}{3}{\rm W}_{13, 9}$ $0.667$
$4$ $\frac{1}{2}{\rm H}_4$ $0$ $14$ $\frac{1}{\sqrt{13}}{\rm C}_{14}$ $0.277$
$5$ ${\rm K}_5$ $0.400$ $15$ ${\rm K}_3\otimes{\rm K}_5^{\dagger}$ $0.646$
$6$ $\frac{1}{\sqrt{5}}{\rm C}_6$ $0.447$ $16$ $\frac{1}{4}{\rm H}_{16}$ $0$
$7$ $\frac{1}{2}{\rm W}_{7, 4}$ $0.866$ $17$ $\frac{1}{3}{\rm W}_{17, 9}$ $0.943$
$8$ $\frac{1}{2\sqrt{2}}{\rm H}(8)$ $0$ $18$ $\frac{1}{\sqrt{17}}{\rm C}_{18}$ $0.243$
$9$ ${\rm K}_3\otimes{\rm K}_3$ $0.703$ $19$ $\frac{1}{\sqrt{17}}{\rm C}_{18}\oplus{\rm H}_1^*$ $1.029$
$10$ $\frac{1}{3}{\rm C}_{10}$ $0.333$ $20$ $\frac{1}{2\sqrt{5}}{\rm H}_{20}$ $0$
$^*$By Proposition 4.2, these orthogonal matrices are saddle points and not local minima. The weighing matrices ${\rm W}_{11, 4}$ and ${\rm W}_{19, 9}$ exists for orders $11$ and $19$, but they are also saddle points. The orthostochastic matrices corresponding to the orthogonal matrices $\frac{1}{2}{\rm W}_{11, 4}$ and $\frac{1}{3}{\rm W}_{19, 9}$ are at distances $1.323>1.054$ and $1.054>1.029$, respectively from the the uniform van der Waerden matrices ${\rm J}_{11}$ and ${\rm J}_{19}$. $^{\dagger}$For order $15$, weighing matrix ${\rm W}_{15, 9}$ exist, which are also local minima, by Proposition 4.11. But the orthostochastic matrix corresponding to the orthogonal matrix $\frac{1}{3}{\rm W}_{15, 9}$ is at a distance $0.817>0.646$, from the uniform van der Waerden matrix ${\rm J}_{15}$.
$n$ Orthogonal matrix $d({\rm J}_n, {\rm B}_n)$ $n$ Orthogonal matrix $d({\rm J}_n, {\rm B}_n)$
$1$ ${\rm H}_1$ $0$ $11$ $\frac{1}{3}{\rm C}_{10}\oplus{\rm H}_1^*$ $1.054$
$2$ $\frac{1}{\sqrt{2}}{\rm H}_2$ $0$ $12$ $\frac{1}{2\sqrt{3}}{\rm H}_{12}$ $0$
$3$ ${\rm K}_3$ $0.471$ $13$ $\frac{1}{3}{\rm W}_{13, 9}$ $0.667$
$4$ $\frac{1}{2}{\rm H}_4$ $0$ $14$ $\frac{1}{\sqrt{13}}{\rm C}_{14}$ $0.277$
$5$ ${\rm K}_5$ $0.400$ $15$ ${\rm K}_3\otimes{\rm K}_5^{\dagger}$ $0.646$
$6$ $\frac{1}{\sqrt{5}}{\rm C}_6$ $0.447$ $16$ $\frac{1}{4}{\rm H}_{16}$ $0$
$7$ $\frac{1}{2}{\rm W}_{7, 4}$ $0.866$ $17$ $\frac{1}{3}{\rm W}_{17, 9}$ $0.943$
$8$ $\frac{1}{2\sqrt{2}}{\rm H}(8)$ $0$ $18$ $\frac{1}{\sqrt{17}}{\rm C}_{18}$ $0.243$
$9$ ${\rm K}_3\otimes{\rm K}_3$ $0.703$ $19$ $\frac{1}{\sqrt{17}}{\rm C}_{18}\oplus{\rm H}_1^*$ $1.029$
$10$ $\frac{1}{3}{\rm C}_{10}$ $0.333$ $20$ $\frac{1}{2\sqrt{5}}{\rm H}_{20}$ $0$
$^*$By Proposition 4.2, these orthogonal matrices are saddle points and not local minima. The weighing matrices ${\rm W}_{11, 4}$ and ${\rm W}_{19, 9}$ exists for orders $11$ and $19$, but they are also saddle points. The orthostochastic matrices corresponding to the orthogonal matrices $\frac{1}{2}{\rm W}_{11, 4}$ and $\frac{1}{3}{\rm W}_{19, 9}$ are at distances $1.323>1.054$ and $1.054>1.029$, respectively from the the uniform van der Waerden matrices ${\rm J}_{11}$ and ${\rm J}_{19}$. $^{\dagger}$For order $15$, weighing matrix ${\rm W}_{15, 9}$ exist, which are also local minima, by Proposition 4.11. But the orthostochastic matrix corresponding to the orthogonal matrix $\frac{1}{3}{\rm W}_{15, 9}$ is at a distance $0.817>0.646$, from the uniform van der Waerden matrix ${\rm J}_{15}$.
[1]

Tao Wu, Yu Lei, Jiao Shi, Maoguo Gong. An evolutionary multiobjective method for low-rank and sparse matrix decomposition. Big Data & Information Analytics, 2017, 2 (1) : 23-37. doi: 10.3934/bdia.2017006

[2]

Charles Fulton, David Pearson, Steven Pruess. Characterization of the spectral density function for a one-sided tridiagonal Jacobi matrix operator. Conference Publications, 2013, 2013 (special) : 247-257. doi: 10.3934/proc.2013.2013.247

[3]

Yuri Fedorov, Božidar Jovanović. Continuous and discrete Neumann systems on Stiefel varieties as matrix generalizations of the Jacobi–Mumford systems. Discrete & Continuous Dynamical Systems, 2021, 41 (6) : 2559-2599. doi: 10.3934/dcds.2020375

[4]

Bing Gao, Rui Gao. On fair entropy of the tent family. Discrete & Continuous Dynamical Systems, 2021, 41 (8) : 3797-3816. doi: 10.3934/dcds.2021017

[5]

Elena Bonetti, Pierluigi Colli, Gianni Gilardi. Singular limit of an integrodifferential system related to the entropy balance. Discrete & Continuous Dynamical Systems - B, 2014, 19 (7) : 1935-1953. doi: 10.3934/dcdsb.2014.19.1935

[6]

Lars Grüne, Luca Mechelli, Simon Pirkelmann, Stefan Volkwein. Performance estimates for economic model predictive control and their application in proper orthogonal decomposition-based implementations. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021013

[7]

Changpin Li, Zhiqiang Li. Asymptotic behaviors of solution to partial differential equation with Caputo–Hadamard derivative and fractional Laplacian: Hyperbolic case. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021023

[8]

Manfred Einsiedler, Elon Lindenstrauss. On measures invariant under diagonalizable actions: the Rank-One case and the general Low-Entropy method. Journal of Modern Dynamics, 2008, 2 (1) : 83-128. doi: 10.3934/jmd.2008.2.83

[9]

Marcel Braukhoff, Ansgar Jüngel. Entropy-dissipating finite-difference schemes for nonlinear fourth-order parabolic equations. Discrete & Continuous Dynamical Systems - B, 2021, 26 (6) : 3335-3355. doi: 10.3934/dcdsb.2020234

[10]

Eduardo Casas, Christian Clason, Arnd Rösch. Preface special issue on system modeling and optimization. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021008

[11]

Sarra Delladji, Mohammed Belloufi, Badreddine Sellami. Behavior of the combination of PRP and HZ methods for unconstrained optimization. Numerical Algebra, Control & Optimization, 2021, 11 (3) : 377-389. doi: 10.3934/naco.2020032

[12]

Ruonan Liu, Run Xu. Hermite-Hadamard type inequalities for harmonical $ (h1,h2)- $convex interval-valued functions. Mathematical Foundations of Computing, 2021  doi: 10.3934/mfc.2021005

[13]

Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023

[14]

Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399

[15]

Claudia Lederman, Noemi Wolanski. An optimization problem with volume constraint for an inhomogeneous operator with nonstandard growth. Discrete & Continuous Dynamical Systems, 2021, 41 (6) : 2907-2946. doi: 10.3934/dcds.2020391

[16]

Zehui Jia, Xue Gao, Xingju Cai, Deren Han. The convergence rate analysis of the symmetric ADMM for the nonconvex separable optimization problems. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1943-1971. doi: 10.3934/jimo.2020053

[17]

Prabhu Manyem. A note on optimization modelling of piecewise linear delay costing in the airline industry. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1809-1823. doi: 10.3934/jimo.2020047

[18]

Kai Cai, Guangyue Han. An optimization approach to the Langberg-Médard multiple unicast conjecture. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021001

[19]

Hong Seng Sim, Wah June Leong, Chuei Yee Chen, Siti Nur Iqmal Ibrahim. Multi-step spectral gradient methods with modified weak secant relation for large scale unconstrained optimization. Numerical Algebra, Control & Optimization, 2018, 8 (3) : 377-387. doi: 10.3934/naco.2018024

[20]

Mohsen Abdolhosseinzadeh, Mir Mohammad Alipour. Design of experiment for tuning parameters of an ant colony optimization method for the constrained shortest Hamiltonian path problem in the grid networks. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 321-332. doi: 10.3934/naco.2020028

 Impact Factor: 

Metrics

  • PDF downloads (788)
  • HTML views (894)
  • Cited by (2)

Other articles
by authors

[Back to Top]