• Previous Article
    An integrated Principal Component Analysis and multi-objective mathematical programming approach to agile supply chain network design under uncertainty
  • JIMO Home
  • This Issue
  • Next Article
    CP and MIP approaches for soccer analysis
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, 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.

[2]

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

[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.

[4]

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

[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.

[6]

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

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[15]

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

[16]

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

[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.

[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.

[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.

[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.

[21]

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

[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.

[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.

[24]

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

[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.

[26]

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

[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.

[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.

[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.

[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.

[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.

[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.

[33]

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

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.

[2]

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

[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.

[4]

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

[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.

[6]

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

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[15]

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

[16]

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

[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.

[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.

[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.

[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.

[21]

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

[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.

[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.

[24]

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

[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.

[26]

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

[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.

[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.

[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.

[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.

[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.

[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.

[33]

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

[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

2017 Impact Factor: 0.994

Article outline

[Back to Top]