-
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] |
Ye Tian, Shucherng Fang, Zhibin Deng, Qingwei Jin. Cardinality constrained portfolio selection problem: A completely positive programming approach. Journal of Industrial and 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 and Continuous Dynamical Systems, 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 and 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 and Management Optimization, 2013, 9 (3) : 703-721. doi: 10.3934/jimo.2013.9.703 |
[5] |
Chengjin Li. Parameter-related projection-based iterative algorithm for a kind of generalized positive semidefinite least squares problem. Numerical Algebra, Control and Optimization, 2020, 10 (4) : 511-520. doi: 10.3934/naco.2020048 |
[6] |
Xueting Tian. Topological pressure for the completely irregular set of birkhoff averages. Discrete and Continuous Dynamical Systems, 2017, 37 (5) : 2745-2763. doi: 10.3934/dcds.2017118 |
[7] |
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 |
[8] |
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 |
[9] |
Alberto Boscaggin, Maurizio Garrione. Positive solutions to indefinite Neumann problems when the weight has positive average. Discrete and Continuous Dynamical Systems, 2016, 36 (10) : 5231-5244. doi: 10.3934/dcds.2016028 |
[10] |
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. |
[11] |
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 |
[12] |
Roberto Camassa. Characteristics and the initial value problem of a completely integrable shallow water equation. Discrete and Continuous Dynamical Systems - B, 2003, 3 (1) : 115-139. doi: 10.3934/dcdsb.2003.3.115 |
[13] |
Fulvia Confortola, Elisa Mastrogiacomo. Feedback optimal control for stochastic Volterra equations with completely monotone kernels. Mathematical Control and Related Fields, 2015, 5 (2) : 191-235. doi: 10.3934/mcrf.2015.5.191 |
[14] |
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 |
[15] |
Deepak Kumar Nayak, Sudhansu Sekhar Routray, Susanta Kumar Paikray, Hemen Dutta. A fuzzy inventory model for Weibull deteriorating items under completely backlogged shortages. Discrete and Continuous Dynamical Systems - S, 2021, 14 (7) : 2435-2453. doi: 10.3934/dcdss.2020401 |
[16] |
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 |
[17] |
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 |
[18] |
Xing Liu, Yijing Sun. Multiple positive solutions for Kirchhoff type problems with singularity. Communications on Pure and Applied Analysis, 2013, 12 (2) : 721-733. doi: 10.3934/cpaa.2013.12.721 |
[19] |
Jinggang Tan. Positive solutions for non local elliptic problems. Discrete and Continuous Dynamical Systems, 2013, 33 (2) : 837-859. doi: 10.3934/dcds.2013.33.837 |
[20] |
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 |
2020 Impact Factor: 1.801
Tools
Metrics
Other articles
by authors
[Back to Top]