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, 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]

Miguel R. Nuñez-Chávez. Controllability under positive constraints for quasilinear parabolic PDEs. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021024
[4]

Peng Chen, Xiaochun Liu. Positive solutions for Choquard equation in exterior domains. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021065
[5]

Meiqiang Feng, Yichen Zhang. Positive solutions of singular multiparameter p-Laplacian elliptic systems. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021083
[6]

Lidan Wang, Lihe Wang, Chunqin Zhou. Classification of positive solutions for fully nonlinear elliptic equations in unbounded cylinders. Communications on Pure & Applied Analysis, 2021, 20 (3) : 1241-1261. doi: 10.3934/cpaa.2021019
[7]

Claudianor O. Alves, Giovany M. Figueiredo, Riccardo Molle. Multiple positive bound state solutions for a critical Choquard equation. Discrete & Continuous Dynamical Systems, 2021  doi: 10.3934/dcds.2021061
[8]

Ashkan Ayough, Farbod Farhadi, Mostafa Zandieh, Parisa Rastkhadiv. Genetic algorithm for obstacle location-allocation problems with customer priorities. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1753-1769. doi: 10.3934/jimo.2020044
[9]

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
[10]

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
[11]

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
[12]

Qian Cao, Yongli Cai, Yong Luo. Nonconstant positive solutions to the ratio-dependent predator-prey system with prey-taxis in one dimension. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021095
[13]

Said Taarabti. Positive solutions for the $ p(x)- $Laplacian : Application of the Nehari method. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021029
[14]

Fangyi Qin, Jun Wang, Jing Yang. Infinitely many positive solutions for Schrödinger-poisson systems with nonsymmetry potentials. Discrete & Continuous Dynamical Systems, 2021  doi: 10.3934/dcds.2021054
[15]

Kazeem Olalekan Aremu, Chinedu Izuchukwu, Grace Nnenanya Ogwo, Oluwatosin Temitope Mewomo. Multi-step iterative algorithm for minimization and fixed point problems in p-uniformly convex metric spaces. Journal of Industrial & Management Optimization, 2021, 17 (4) : 2161-2180. doi: 10.3934/jimo.2020063
[16]

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
[17]

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
[18]

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

Julian Koellermeier, Giovanni Samaey. Projective integration schemes for hyperbolic moment equations. Kinetic & Related Models, 2021, 14 (2) : 353-387. doi: 10.3934/krm.2021008
[20]

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

2019 Impact Factor: 1.366

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences