-
Previous Article
A difference of convex optimization algorithm for piecewise linear regression
- JIMO Home
- This Issue
-
Next Article
Test of copositive tensors
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 |
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.
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. |
[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. 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. |
[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. 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. |
[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. |
[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. 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. |
[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. 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. |
[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. 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. |
[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. 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. |
[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. |
[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. 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. |
[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] |
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
Tools
Metrics
Other articles
by authors
[Back to Top]