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]

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

2018 Impact Factor: 1.025

Tools

Metrics

  • PDF downloads (66)
  • HTML views (1037)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2019 American Institute of Mathematical Sciences