A semidefinite relaxation algorithm for checking completely positive separable matrices

Previous Article
Test of copositive tensors
JIMO Home
This Issue
Next Article
A difference of convex optimization algorithm for piecewise linear regression

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.

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]	Ye Tian, Shucherng Fang, Zhibin Deng, Qingwei Jin. Cardinality constrained portfolio selection problem: A completely positive programming approach. Journal of Industrial & Management Optimization, 2016, 12 (3) : 1041-1056. doi: 10.3934/jimo.2016.12.1041
[2]	Christopher Hoffman. Subshifts of finite type which have completely positive entropy. Discrete & Continuous Dynamical Systems - A, 2011, 29 (4) : 1497-1516. doi: 10.3934/dcds.2011.29.1497
[3]	Zhi-Bin Deng, Ye Tian, Cheng Lu, Wen-Xun Xing. Globally solving quadratic programs with convex objective and complementarity constraints via completely positive programming. Journal of Industrial & Management Optimization, 2018, 14 (2) : 625-636. doi: 10.3934/jimo.2017064
[4]	Ye Tian, Shu-Cherng Fang, Zhibin Deng, Wenxun Xing. Computable representation of the cone of nonnegative quadratic forms over a general second-order cone and its application to completely positive programming. Journal of Industrial & Management Optimization, 2013, 9 (3) : 703-721. doi: 10.3934/jimo.2013.9.703
[5]	Xueting Tian. Topological pressure for the completely irregular set of birkhoff averages. Discrete & Continuous Dynamical Systems - A, 2017, 37 (5) : 2745-2763. doi: 10.3934/dcds.2017118
[6]	Răzvan M. Tudoran. On the control of stability of periodic orbits of completely integrable systems. Journal of Geometric Mechanics, 2015, 7 (1) : 109-124. doi: 10.3934/jgm.2015.7.109
[7]	Joaquim Borges, Josep Rifà, Victor Zinoviev. Completely regular codes by concatenating Hamming codes. Advances in Mathematics of Communications, 2018, 12 (2) : 337-349. doi: 10.3934/amc.2018021
[8]	Alberto Boscaggin, Maurizio Garrione. Positive solutions to indefinite Neumann problems when the weight has positive average. Discrete & Continuous Dynamical Systems - A, 2016, 36 (10) : 5231-5244. doi: 10.3934/dcds.2016028
[9]	Vladimir S. Matveev and Petar J. Topalov. Metric with ergodic geodesic flow is completely determined by unparameterized geodesics. Electronic Research Announcements, 2000, 6: 98-104.
[10]	Joaquim Borges, Josep Rifà, Victor A. Zinoviev. Families of nested completely regular codes and distance-regular graphs. Advances in Mathematics of Communications, 2015, 9 (2) : 233-246. doi: 10.3934/amc.2015.9.233
[11]	Roberto Camassa. Characteristics and the initial value problem of a completely integrable shallow water equation. Discrete & Continuous Dynamical Systems - B, 2003, 3 (1) : 115-139. doi: 10.3934/dcdsb.2003.3.115
[12]	Fulvia Confortola, Elisa Mastrogiacomo. Feedback optimal control for stochastic Volterra equations with completely monotone kernels. Mathematical Control & Related Fields, 2015, 5 (2) : 191-235. doi: 10.3934/mcrf.2015.5.191
[13]	Joaquim Borges, Josep Rifà, Victor A. Zinoviev. On $q$-ary linear completely regular codes with $\rho=2$ and antipodal dual. Advances in Mathematics of Communications, 2010, 4 (4) : 567-578. doi: 10.3934/amc.2010.4.567
[14]	G. Infante. Positive solutions of nonlocal boundary value problems with singularities. Conference Publications, 2009, 2009 (Special) : 377-384. doi: 10.3934/proc.2009.2009.377
[15]	John R. Graef, Lingju Kong, Qingkai Kong, Min Wang. Positive solutions of nonlocal fractional boundary value problems. Conference Publications, 2013, 2013 (special) : 283-290. doi: 10.3934/proc.2013.2013.283
[16]	Jinggang Tan. Positive solutions for non local elliptic problems. Discrete & Continuous Dynamical Systems - A, 2013, 33 (2) : 837-859. doi: 10.3934/dcds.2013.33.837
[17]	Xing Liu, Yijing Sun. Multiple positive solutions for Kirchhoff type problems with singularity. Communications on Pure & Applied Analysis, 2013, 12 (2) : 721-733. doi: 10.3934/cpaa.2013.12.721
[18]	John V. Baxley, Philip T. Carroll. Nonlinear boundary value problems with multiple positive solutions. Conference Publications, 2003, 2003 (Special) : 83-90. doi: 10.3934/proc.2003.2003.83
[19]	Friedemann Brock, Leonelo Iturriaga, Justino Sánchez, Pedro Ubilla. Existence of positive solutions for $p$--Laplacian problems with weights. Communications on Pure & Applied Analysis, 2006, 5 (4) : 941-952. doi: 10.3934/cpaa.2006.5.941
[20]	J. R. L. Webb. Remarks on positive solutions of some three point boundary value problems. Conference Publications, 2003, 2003 (Special) : 905-915. doi: 10.3934/proc.2003.2003.905

American Institute of Mathematical Sciences