American Institute of Mathematical Sciences

Advanced
April  2019, 15(2): 893-908. doi: 10.3934/jimo.2018076

A semidefinite relaxation algorithm for checking completely positive separable matrices

Anwa Zhou 1,, and  Jinyan Fan 2,

1. 

Department of Mathematics, Shanghai University, Shanghai 200444, China
2. 

School of Mathematical Sciences, and MOE-LSC, Shanghai Jiao Tong University, Shanghai 200240, China

* Corresponding author: Anwa Zhou

Received  July 2017 Revised  November 2017 Published  June 2018

A symmetric matrix $A$ is completely positive (CP) if there exists an entrywise nonnegative matrix $V$ such that $A = VV ^T$. A real symmetric matrix is called completely positive separable (CPS) if it can be written as a sum of rank-1 Kronecker products of completely positive matrices. This paper studies the CPS problem. A criterion is given to determine whether a given matrix is CPS, and a specific CPS decomposition is constructed if the matrix is CPS.

Keywords: Completely positive matrices, completely positive separability, moment problems, semidefinite algorithm.
Mathematics Subject Classification: Primary: 15A23, 15B48, 44A60, 90C22.
Citation: Anwa Zhou, Jinyan Fan. A semidefinite relaxation algorithm for checking completely positive separable matrices. Journal of Industrial & Management Optimization, 2019, 15 (2) : 893-908. doi: 10.3934/jimo.2018076
References:
[1]

N. Arima, S. Kim and M. Kojima, A quadratically constrained quadratic optimization model for completely positive cone programming, SIAM J. Optim., 23 (2013), 2320-2340.  doi: 10.1137/120890636.  Google Scholar

[2]

A. Berman and N. Shaked-Monderer, Completely Positive Matrices, World Scientific Publishing Co., Inc., River Edge, NJ, 2003. doi: 10.1142/9789812795212.  Google Scholar

[3]

S. Burer, On the copositive representation of binary and continuous nonconvex quadratic programs, Math. Program., Ser. A, 120 (2009), 479-495.  doi: 10.1007/s10107-008-0223-z.  Google Scholar

[4]

R. Curto and L. Fialkow, Truncated K-moment problems in several variables, J. Operator Theory, 54 (2005), 189-226.   Google Scholar

[5]

G. Dahl, J. M. Leinaas, J. Myrheim and E. Ovrum, A tensor product matrix approximation problem in quantum physics, Linear Algebra Appl., 420 (2007), 711-725.  doi: 10.1016/j.laa.2006.08.026.  Google Scholar

[6]

J. Demmel, Applied Numerical Linear Algebra, SIAM, Philadelphia, PA, 1997. doi: 10.1137/1.9781611971446.  Google Scholar

[7]

A. C. Doherty, P. A. Parrilo and F. M. Spedalieri, Complete family of separability criteria, Phy. Rev. A, 69 (2004), 022308. doi: 10.1103/PhysRevA.69.022308.  Google Scholar

[8]

P. J. Dickinson and L. Gijben, On the computational complexity of membership problems for the completely positive cone and its dual, Comput. Optim. Appl., 57 (2014), 403-415.  doi: 10.1007/s10589-013-9594-z.  Google Scholar

[9]

I. Dukanovic and F. Rendl, Copositive programming motivated bounds on the stability and the chromatic numbers, Math. Program., Ser. A, 121 (2010), 249-268.  doi: 10.1007/s10107-008-0233-x.  Google Scholar

[10]

L. Gurvits, Classical deterministic complexity of Edmonds' problem and quantum entanglement, in Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing, ACM, New York, (2003), 10-19. doi: 10.1145/780542.780545.  Google Scholar

[11]

L. Gurvits and H. Barnum, Largest separable balls around the maximally mixed bipartite quantum state, Phys. Rev. A, 66 (2002), 062311. doi: 10.1103/PhysRevA.66.062311.  Google Scholar

[12]

D. Henrion and J. B. Lasserre, Detecting global optimality and extracting solutions in GloptiPoly, Positive polynomials in control, Lecture Notes in Control and Inform. Sci. , Springer, Berlin, 312 (2005), 293-310. doi: 10.1007/10997703_15.  Google Scholar

[13]

D. Henrion, J. B. Lasserre and J. Loefberg, GloptiPoly 3: Moments, optimization and semidefinite programming, Optim. Methods Softw., 24 (2009), 761-779.  doi: 10.1080/10556780802699201.  Google Scholar

[14]

V. Jeyakumar, J. B. Lasserre and G. Li, On Polynomial Optimization over Non-compact Semi-algebraic Sets, J. Optim. Theory Appl., 163 (2014), 707-718.  doi: 10.1007/s10957-014-0545-3.  Google Scholar

[15]

J. B. Lasserre, Global optimization with polynomials and the problem of moments, SIAM J. Optim., 11 (2001), 796-817.  doi: 10.1137/S1052623400366802.  Google Scholar

[16]

J. B. Lasserre, Moments, Positive Polynomials and Their Applications, Imperial College Press, London, 2010.  Google Scholar

[17]

M. Laurent, Sums of squares, moment matrices and optimization over polynomials, Emerging Applications of Algebraic Geometry, Springer, New York, 149 (2009), 157-270. doi: 10.1007/978-0-387-09686-5_7.  Google Scholar

[18]

Z. Luo and L. Qi, Completely positive tensors: Properties, easily checkable subclasses, and tractable relaxations, SIAM. J. Matrix Anal. Appl., 37 (2016), 1675-1698.  doi: 10.1137/15M1025220.  Google Scholar

[19]

K. G. Murty and S. N. Kabadi, Some NP-complete problems in quadratic and nonlinear programming, Math. Program., 39 (1987), 117-129.  doi: 10.1007/BF02592948.  Google Scholar

[20]

J. Nie, Certifying convergence of Lasserre's hierarchy via flat truncation, Math. Program., Ser. A, 142 (2013), 485-510.  doi: 10.1007/s10107-012-0589-9.  Google Scholar

[21]

J. Nie, The $\mathcal{A}$-truncated K-moment problem, Found. Comput. Math., 14 (2014), 1243-1276.  doi: 10.1007/s10208-014-9225-9.  Google Scholar

[22]

J. Nie, Linear optimization with cones of moments and nonnegative polynomials, Math. Program., Ser. B, 153 (2015), 247-274.  doi: 10.1007/s10107-014-0797-6.  Google Scholar

[23]

J. Nie, Optimality conditions and finite convergence of Lasserre's hierarchy, Math. Program., Ser. A, 146 (2014), 97-121.  doi: 10.1007/s10107-013-0680-x.  Google Scholar

[24]

J. Nie and X. Zhang, Positive maps and separable matrices, SIAM J. Optim., 26 (2016), 1236-1256.  doi: 10.1137/15M1018514.  Google Scholar

[25]

M. Putinar, Positive polynomials on compact semi-algebraic sets, Indiana Univ. Math. J., 42 (1993), 969-984.  doi: 10.1512/iumj.1993.42.42045.  Google Scholar

[26]

L. Qi, Eigenvalues of a real supersymmetric tensor, J. Symbolic Comput., 40 (2005), 1302-1324.  doi: 10.1016/j.jsc.2005.05.007.  Google Scholar

[27]

L. Qi, F. Wang and Y. Wang, Z-Eigenvalue methods for a global optimization polynomial optimization problem, Math. Program., Ser. A, 118 (2009), 301-306.  doi: 10.1007/s10107-007-0193-6.  Google Scholar

[28]

P. Rosakis, Ellipticity and deformations with discontinuous deformation gradients in finite elastostatics, Arch. Rational Mech. Anal., 109 (1990), 1-37.  doi: 10.1007/BF00377977.  Google Scholar

[29]

H. C. Simpson and S. J. Spector, On copositive matrices and strong ellipticity for isotropic elastic materials, Arch. Rational Mech. Anal., 84 (1983), 55-68.  doi: 10.1007/BF00251549.  Google Scholar

[30]

J. F. Sturm, SeDuMi 1.02: A MATLAB toolbox for optimization over symmetric cones, Optim. Methods Softw., 11/12 (1999), 625-653.  doi: 10.1080/10556789908805766.  Google Scholar

[31]

M. J. Todd and Y. Ye, Approximate Farkas lemmas and stopping rules for iterative infeasible-point algorithms for linear programming, Math. Program., Ser. A, 81 (1998), 1-21.  doi: 10.1007/BF01584841.  Google Scholar

[32]

Y. Wang and M. Aron, A reformulation of the strong ellipticity conditions for unconstrained hyperelastic media, J. Elasticity, 44 (1996), 89-96.  doi: 10.1007/BF00042193.  Google Scholar

[33]

A. Zhou and J. Fan, The CP-matrix completion problem, SIAM. J. Matrix Anal. Appl., 35 (2014), 127-142.  doi: 10.1137/130919490.  Google Scholar

show all references

References:
[1]

N. Arima, S. Kim and M. Kojima, A quadratically constrained quadratic optimization model for completely positive cone programming, SIAM J. Optim., 23 (2013), 2320-2340.  doi: 10.1137/120890636.  Google Scholar

[2]

A. Berman and N. Shaked-Monderer, Completely Positive Matrices, World Scientific Publishing Co., Inc., River Edge, NJ, 2003. doi: 10.1142/9789812795212.  Google Scholar

[3]

S. Burer, On the copositive representation of binary and continuous nonconvex quadratic programs, Math. Program., Ser. A, 120 (2009), 479-495.  doi: 10.1007/s10107-008-0223-z.  Google Scholar

[4]

R. Curto and L. Fialkow, Truncated K-moment problems in several variables, J. Operator Theory, 54 (2005), 189-226.   Google Scholar

[5]

G. Dahl, J. M. Leinaas, J. Myrheim and E. Ovrum, A tensor product matrix approximation problem in quantum physics, Linear Algebra Appl., 420 (2007), 711-725.  doi: 10.1016/j.laa.2006.08.026.  Google Scholar

[6]

J. Demmel, Applied Numerical Linear Algebra, SIAM, Philadelphia, PA, 1997. doi: 10.1137/1.9781611971446.  Google Scholar

[7]

A. C. Doherty, P. A. Parrilo and F. M. Spedalieri, Complete family of separability criteria, Phy. Rev. A, 69 (2004), 022308. doi: 10.1103/PhysRevA.69.022308.  Google Scholar

[8]

P. J. Dickinson and L. Gijben, On the computational complexity of membership problems for the completely positive cone and its dual, Comput. Optim. Appl., 57 (2014), 403-415.  doi: 10.1007/s10589-013-9594-z.  Google Scholar

[9]

I. Dukanovic and F. Rendl, Copositive programming motivated bounds on the stability and the chromatic numbers, Math. Program., Ser. A, 121 (2010), 249-268.  doi: 10.1007/s10107-008-0233-x.  Google Scholar

[10]

L. Gurvits, Classical deterministic complexity of Edmonds' problem and quantum entanglement, in Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing, ACM, New York, (2003), 10-19. doi: 10.1145/780542.780545.  Google Scholar

[11]

L. Gurvits and H. Barnum, Largest separable balls around the maximally mixed bipartite quantum state, Phys. Rev. A, 66 (2002), 062311. doi: 10.1103/PhysRevA.66.062311.  Google Scholar

[12]

D. Henrion and J. B. Lasserre, Detecting global optimality and extracting solutions in GloptiPoly, Positive polynomials in control, Lecture Notes in Control and Inform. Sci. , Springer, Berlin, 312 (2005), 293-310. doi: 10.1007/10997703_15.  Google Scholar

[13]

D. Henrion, J. B. Lasserre and J. Loefberg, GloptiPoly 3: Moments, optimization and semidefinite programming, Optim. Methods Softw., 24 (2009), 761-779.  doi: 10.1080/10556780802699201.  Google Scholar

[14]

V. Jeyakumar, J. B. Lasserre and G. Li, On Polynomial Optimization over Non-compact Semi-algebraic Sets, J. Optim. Theory Appl., 163 (2014), 707-718.  doi: 10.1007/s10957-014-0545-3.  Google Scholar

[15]

J. B. Lasserre, Global optimization with polynomials and the problem of moments, SIAM J. Optim., 11 (2001), 796-817.  doi: 10.1137/S1052623400366802.  Google Scholar

[16]

J. B. Lasserre, Moments, Positive Polynomials and Their Applications, Imperial College Press, London, 2010.  Google Scholar

[17]

M. Laurent, Sums of squares, moment matrices and optimization over polynomials, Emerging Applications of Algebraic Geometry, Springer, New York, 149 (2009), 157-270. doi: 10.1007/978-0-387-09686-5_7.  Google Scholar

[18]

Z. Luo and L. Qi, Completely positive tensors: Properties, easily checkable subclasses, and tractable relaxations, SIAM. J. Matrix Anal. Appl., 37 (2016), 1675-1698.  doi: 10.1137/15M1025220.  Google Scholar

[19]

K. G. Murty and S. N. Kabadi, Some NP-complete problems in quadratic and nonlinear programming, Math. Program., 39 (1987), 117-129.  doi: 10.1007/BF02592948.  Google Scholar

[20]

J. Nie, Certifying convergence of Lasserre's hierarchy via flat truncation, Math. Program., Ser. A, 142 (2013), 485-510.  doi: 10.1007/s10107-012-0589-9.  Google Scholar

[21]

J. Nie, The $\mathcal{A}$-truncated K-moment problem, Found. Comput. Math., 14 (2014), 1243-1276.  doi: 10.1007/s10208-014-9225-9.  Google Scholar

[22]

J. Nie, Linear optimization with cones of moments and nonnegative polynomials, Math. Program., Ser. B, 153 (2015), 247-274.  doi: 10.1007/s10107-014-0797-6.  Google Scholar

[23]

J. Nie, Optimality conditions and finite convergence of Lasserre's hierarchy, Math. Program., Ser. A, 146 (2014), 97-121.  doi: 10.1007/s10107-013-0680-x.  Google Scholar

[24]

J. Nie and X. Zhang, Positive maps and separable matrices, SIAM J. Optim., 26 (2016), 1236-1256.  doi: 10.1137/15M1018514.  Google Scholar

[25]

M. Putinar, Positive polynomials on compact semi-algebraic sets, Indiana Univ. Math. J., 42 (1993), 969-984.  doi: 10.1512/iumj.1993.42.42045.  Google Scholar

[26]

L. Qi, Eigenvalues of a real supersymmetric tensor, J. Symbolic Comput., 40 (2005), 1302-1324.  doi: 10.1016/j.jsc.2005.05.007.  Google Scholar

[27]

L. Qi, F. Wang and Y. Wang, Z-Eigenvalue methods for a global optimization polynomial optimization problem, Math. Program., Ser. A, 118 (2009), 301-306.  doi: 10.1007/s10107-007-0193-6.  Google Scholar

[28]

P. Rosakis, Ellipticity and deformations with discontinuous deformation gradients in finite elastostatics, Arch. Rational Mech. Anal., 109 (1990), 1-37.  doi: 10.1007/BF00377977.  Google Scholar

[29]

H. C. Simpson and S. J. Spector, On copositive matrices and strong ellipticity for isotropic elastic materials, Arch. Rational Mech. Anal., 84 (1983), 55-68.  doi: 10.1007/BF00251549.  Google Scholar

[30]

J. F. Sturm, SeDuMi 1.02: A MATLAB toolbox for optimization over symmetric cones, Optim. Methods Softw., 11/12 (1999), 625-653.  doi: 10.1080/10556789908805766.  Google Scholar

[31]

M. J. Todd and Y. Ye, Approximate Farkas lemmas and stopping rules for iterative infeasible-point algorithms for linear programming, Math. Program., Ser. A, 81 (1998), 1-21.  doi: 10.1007/BF01584841.  Google Scholar

[32]

Y. Wang and M. Aron, A reformulation of the strong ellipticity conditions for unconstrained hyperelastic media, J. Elasticity, 44 (1996), 89-96.  doi: 10.1007/BF00042193.  Google Scholar

[33]

A. Zhou and J. Fan, The CP-matrix completion problem, SIAM. J. Matrix Anal. Appl., 35 (2014), 127-142.  doi: 10.1137/130919490.  Google Scholar

[1]

Horst R. Thieme. Remarks on resolvent positive operators and their perturbation. Discrete & Continuous Dynamical Systems - A, 1998, 4 (1) : 73-90. doi: 10.3934/dcds.1998.4.73
[2]

Haiyan Wang. Existence and nonexistence of positive radial solutions for quasilinear systems. Conference Publications, 2009, 2009 (Special) : 810-817. doi: 10.3934/proc.2009.2009.810
[3]

Ka Luen Cheung, Man Chun Leung. Asymptotic behavior of positive solutions of the equation $ \Delta u + K u^{\frac{n+2}{n-2}} = 0$ in $IR^n$ and positive scalar curvature. Conference Publications, 2001, 2001 (Special) : 109-120. doi: 10.3934/proc.2001.2001.109
[4]

Zaihong Wang, Jin Li, Tiantian Ma. An erratum note on the paper: Positive periodic solution for Brillouin electron beam focusing system. Discrete & Continuous Dynamical Systems - B, 2013, 18 (7) : 1995-1997. doi: 10.3934/dcdsb.2013.18.1995
[5]

Jianping Gao, Shangjiang Guo, Wenxian Shen. Persistence and time periodic positive solutions of doubly nonlocal Fisher-KPP equations in time periodic and space heterogeneous media. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2645-2676. doi: 10.3934/dcdsb.2020199
[6]

Zhiming Guo, Zhi-Chun Yang, Xingfu Zou. Existence and uniqueness of positive solution to a non-local differential equation with homogeneous Dirichlet boundary condition---A non-monotone case. Communications on Pure & Applied Analysis, 2012, 11 (5) : 1825-1838. doi: 10.3934/cpaa.2012.11.1825
[7]

Hirofumi Notsu, Masato Kimura. Symmetry and positive definiteness of the tensor-valued spring constant derived from P1-FEM for the equations of linear elasticity. Networks & Heterogeneous Media, 2014, 9 (4) : 617-634. doi: 10.3934/nhm.2014.9.617
[8]

Alexandr Mikhaylov, Victor Mikhaylov. Dynamic inverse problem for Jacobi matrices. Inverse Problems & Imaging, 2019, 13 (3) : 431-447. doi: 10.3934/ipi.2019021
[9]

J. Frédéric Bonnans, Justina Gianatti, Francisco J. Silva. On the convergence of the Sakawa-Shindo algorithm in stochastic control. Mathematical Control & Related Fields, 2016, 6 (3) : 391-406. doi: 10.3934/mcrf.2016008
[10]

Demetres D. Kouvatsos, Jumma S. Alanazi, Kevin Smith. A unified ME algorithm for arbitrary open QNMs with mixed blocking mechanisms. Numerical Algebra, Control & Optimization, 2011, 1 (4) : 781-816. doi: 10.3934/naco.2011.1.781
[11]

Teddy Pichard. A moment closure based on a projection on the boundary of the realizability domain: 1D case. Kinetic & Related Models, 2020, 13 (6) : 1243-1280. doi: 10.3934/krm.2020045
[12]

Ian Schindler, Kyril Tintarev. Mountain pass solutions to semilinear problems with critical nonlinearity. Conference Publications, 2007, 2007 (Special) : 912-919. doi: 10.3934/proc.2007.2007.912
[13]

Valeria Chiado Piat, Sergey S. Nazarov, Andrey Piatnitski. Steklov problems in perforated domains with a coefficient of indefinite sign. Networks & Heterogeneous Media, 2012, 7 (1) : 151-178. doi: 10.3934/nhm.2012.7.151
[14]

Vieri Benci, Sunra Mosconi, Marco Squassina. Preface: Applications of mathematical analysis to problems in theoretical physics. Discrete & Continuous Dynamical Systems - S, 2021, 14 (5) : i-i. doi: 10.3934/dcdss.2020446
[15]

M. Mahalingam, Parag Ravindran, U. Saravanan, K. R. Rajagopal. Two boundary value problems involving an inhomogeneous viscoelastic solid. Discrete & Continuous Dynamical Systems - S, 2017, 10 (6) : 1351-1373. doi: 10.3934/dcdss.2017072
[16]

Xue-Ping Luo, Yi-Bin Xiao, Wei Li. Strict feasibility of variational inclusion problems in reflexive Banach spaces. Journal of Industrial & Management Optimization, 2020, 16 (5) : 2495-2502. doi: 10.3934/jimo.2019065
[17]

Deren Han, Zehui Jia, Yongzhong Song, David Z. W. Wang. An efficient projection method for nonlinear inverse problems with sparsity constraints. Inverse Problems & Imaging, 2016, 10 (3) : 689-709. doi: 10.3934/ipi.2016017
[18]

Samir Adly, Oanh Chau, Mohamed Rochdi. Solvability of a class of thermal dynamical contact problems with subdifferential conditions. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 91-104. doi: 10.3934/naco.2012.2.91
[19]

Elvise Berchio, Filippo Gazzola, Dario Pierotti. Nodal solutions to critical growth elliptic problems under Steklov boundary conditions. Communications on Pure & Applied Analysis, 2009, 8 (2) : 533-557. doi: 10.3934/cpaa.2009.8.533
[20]

Petra Csomós, Hermann Mena. Fourier-splitting method for solving hyperbolic LQR problems. Numerical Algebra, Control & Optimization, 2018, 8 (1) : 17-46. doi: 10.3934/naco.2018002

2019 Impact Factor: 1.366

Tools

Metrics

  • PDF downloads (136)
  • HTML views (1241)
  • Cited by (1)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences