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

A semidefinite relaxation algorithm for checking completely positive separable matrices

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.

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. ArimaS. 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. DahlJ. M. LeinaasJ. 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. HenrionJ. 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. JeyakumarJ. 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. QiF. 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. ArimaS. 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. DahlJ. M. LeinaasJ. 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. HenrionJ. 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. JeyakumarJ. 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. QiF. 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

Metrics

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

Other articles
by authors

[Back to Top]