Copositivity and complete positivity. Abstracts from the workshop held October 29 – Novermber 4, 2017. (English) Zbl 1409.00070
Summary: A real matrix \(A\) is called copositive if \(x^TAx \geq 0\) holds for all \(x \in \mathbb R^n_+\). A matrix \(A\) is called completely positive if it can be factorized as \(A = BB^T\), where \(B\) is an entrywise nonnegative matrix. The concept of copositivity can be traced back to Theodore Motzkin in 1952, and that of complete positivity to Marshal Hall Jr. in 1958. The two classes are related, and both have received considerable attention in the linear algebra community and in the last two decades also in the mathematical optimization community. These matrix classes have important applications in various fields, in which they arise naturally, including mathematical modeling, optimization, dynamical systems and statistics. More applications constantly arise.
The workshop brought together people working in various disciplines related to copositivity and complete positivity, in order to discuss these concepts from different viewpoints and to join forces to better understand these difficult but fascinating classes of matrices.
The workshop brought together people working in various disciplines related to copositivity and complete positivity, in order to discuss these concepts from different viewpoints and to join forces to better understand these difficult but fascinating classes of matrices.
MSC:
| 00B05 | Collections of abstracts of lectures |
| 00B25 | Proceedings of conferences of miscellaneous specific interest |
| 15B48 | Positive matrices and their generalizations; cones of matrices |
| 15A23 | Factorization of matrices |
| 90C22 | Semidefinite programming |
| 15-06 | Proceedings, conferences, collections, etc. pertaining to linear algebra |
References:
| [1] | Ando T., Completely Positive Matrices, Lecture Notes, The University of Wisconsin, Madison (1991). |
| [2] | Anstreicher K.M., Burer S., Dickinson, P.J.C. An algorithm for computing the CPfactorization of a completely positive matrix. Working paper, 2015. |
| [3] | Berman A., D¨ur M., Shaked-Monderer N., Open Problems in the Theory of Completely Positive and Copositive Matrices. Electronic Journal of Linear Algebra 29 (2015), 46-58. · Zbl 1326.15048 |
| [4] | Berman A., Grone R., Completely positive bipartite matrices, Mathematical Proceedings of the Cambridge Philosophical Society 103 (1988), 269-276. · Zbl 0658.15019 |
| [5] | Berman A., Hershkowitz D. , Combinatorial results on completely positive matrices, Linear Algebra and its Applications, 95 (1987),111-125 . · Zbl 0623.05040 |
| [6] | Berman A., King C. and Shorten R., A characterization of common diagonal stability over cones, Linear and Multilinear Algebra, 60 (2012), 1117-1123. · Zbl 1260.15049 |
| [7] | Berman A., Shaked-Monderer N., Completely positive matrices, World Scientific, 2003. · Zbl 1030.15022 |
| [8] | Berman A., Shaked-Monderer N., Remarks on completely positive matrices, Linear and Multilinear Algebra, 44 (1998), 149-163. · Zbl 0931.15016 |
| [9] | Berman A., Rothblum, U., A note on the computation of the cp-rank. Linear Algebra and its Applications 419 (2006), 1-7. · Zbl 1105.65038 |
| [10] | Bomze I.M., Building a completely positive factorization, Central European Journal of Operations Research (2017), in print. · Zbl 1397.90288 |
| [11] | Bomze I.M., Block pivoting shortcut strategies for detecting copositivity, Linear Algebra and its Applications, 248 (1989), 161-184. · Zbl 0862.65036 |
| [12] | Bomze I.M., D¨ur M., de Klerk E., Roos C., Quist A.J., Terlaky T., On copositive programming and standard quadratic optimization problems, Journal of Global Optimization 18 (2000), 301-320. · Zbl 0970.90057 |
| [13] | Bomze I.M., Eichfelder G., Copositivity detection by difference-of-convex decomposition and ω-subdivision, Mathematical Programming 138 (2013), 365-400. Copositivity and Complete Positivity3075 · Zbl 1267.65060 |
| [14] | Bomze I.M., Schachinger W., Ullrich R., New lower bounds and asymptotics for the cp-rank. SIAM Journal on Matrix Analysis and Applications 36 (1) (2015), 20-37. · Zbl 1326.15050 |
| [15] | Bomze I.M., Schachinger W., Ullrich R., From seven to eleven: completely positive matrices with high cp-rank. Linear Algebra and its Applications 459 (2014), 208-221. · Zbl 1310.15059 |
| [16] | Bundfuss S., D¨ur M.: Algorithmic copositivity detection by simplicial partition. Linear Algebra and its Applications 428 (2008), 1511-1523. · Zbl 1138.15007 |
| [17] | Burer S., On the copositive representation of binary and continuous nonconvex quadratic programs. Mathematical Programming 120 (2009), 479-495. · Zbl 1180.90234 |
| [18] | Cottle R.W., Habetler G.J., Lemke C.E., On classes of copositive matrices. Linear Algebra and its Applications 3 (1970), 295-310. · Zbl 0196.05602 |
| [19] | Deng, Z., Fang, S.C., Jin, Q., Xing, W., Detecting copositivity of a symmetric matrix by an adaptive ellipsoid-based approximation scheme. European Journal of Operational Research 229 (2013), 21-28. · Zbl 1317.90229 |
| [20] | Dickinson P.J.C., Erratum to: On the DJL conjecture for order 6. Operators and Matrices 11(4), (2017), 1197-1200. · Zbl 1417.15049 |
| [21] | Dickinson P.J.C., D¨ur M., Linear time complete positivity and detection and decomposition of sparse matrices. SIAM Journal on Matrix Analysis and Applications 33 (2012), 701-720. · Zbl 1268.65063 |
| [22] | Dickinson P.J.C., Gijben L., On the Computational Complexity of Membership Problems for the Completely Positive Cone and its Dual, Computational Optimization and Applications 57 (2014), 403-415. · Zbl 1330.90103 |
| [23] | Drew J.H., Johnson C.R., Loewy R., Completely positive matrices associated with Mmatrices Linear and Multilinear Algebra 37 (1994), 303-310. · Zbl 0815.15019 |
| [24] | D¨ur M., Copositive Programming – a Survey. In: M. Diehl, F. Glineur, E. Jarlebring, W. Michiels (Eds.), Recent Advances in Optimization and its Applications in Engineering, Springer 2010, pp. 3-20. |
| [25] | Gvozdenovi´c N., Laurent M., The operator Ψ for the chromatic number of a graph. SIAM Journal on Optimization 19 (2008), 572-591. · Zbl 1213.05080 |
| [26] | Groetzner P., D¨ur M., Factorization heuristics for completely positive matrices. Preprint, submitted (2017). |
| [27] | Hildebrand R., Minimal zeros of copositive matrices. Linear Algebra and its Applications 459 (2014), 154-174. · Zbl 1309.15050 |
| [28] | Hildebrand R., The extreme rays of the 5 x 5 copositive cone. Linear Algebra and its Applications 437 (2012), 1538-1547. · Zbl 1259.15045 |
| [29] | Hoffman A.J., Pereira F., On copositive matrices with −1, 0, 1 entries. Journal of Combinatorial Theory 14 (1973), 302-309. · Zbl 0273.15019 |
| [30] | Hiriart-Urruty J.B., Seeger A., A variational approach to copositive matrices. SIAM Review 52 (2010), 593-629. · Zbl 1207.15037 |
| [31] | Ikramov K.D., Savel’eva N., Conditionally definite matrices. Journal of Mathematical Sciences 99 (2000), 1-50. · Zbl 0954.65035 |
| [32] | Kong, Q., Lee, C.Y., Teo, C.P., Zheng, Z., Scheduling arrivals to a stochastic service delivery system using copositive cones. Operations Research 61(3) (2013), 711-726. · Zbl 1273.90090 |
| [33] | Kogan N., Berman A., Characterization of completely positive graphs. Discrete Mathematics 114 (1993), 297-304. · Zbl 0783.05071 |
| [34] | Loewy L., Tam B-S., CP rank of completely positive matrices of order five, Linear Algebra and its Applications, 363 (2003), 161-176. · Zbl 1019.15009 |
| [35] | Maxfield J.E., Minc H., On the matrix equation X′X= A, Proceedings of the Edinburgh Mathematical Society 13(II) (1962), 125-129. · Zbl 0112.25101 |
| [36] | Miller D.A., Zucker S.W., Copositive-plus Lemke algorithm solves polymatrix games, Operations Research Letters 10 (1991), 285-290. · Zbl 0742.90077 |
| [37] | Murty K.G., Kabadi S.N., Some NP-complete problems in quadratic and nonlinear programming. Mathematical Programming 39 (1987), 117-129. · Zbl 0637.90078 |
| [38] | Natarajan K., Teo C.P., Zheng Z., Mixed zero-one linear programs under objective uncertainty: a completely positive representation. Operations Research 59 (2011), 713-728. 3076Oberwolfach Report 52/2017 · Zbl 1231.90304 |
| [39] | Nie J., The A-truncated K-moment problem, Foundations of Computational Mathematics 14 (2014), 1243-1276. · Zbl 1331.65172 |
| [40] | Povh J., Rendl F., Copositive and semidefinite relaxations of the Quadratic Assignment Problem. Discrete Optimization 6 (2009), 231-241. · Zbl 1167.90597 |
| [41] | Povh J., Rendl F., A copositive programming approach to graph partitioning. SIAM Journal on Optimization 18 (2007), 223-241. · Zbl 1143.90025 |
| [42] | Shaked-Monderer N., On the DJL conjecture for order 6. Operators and Matrices 11(1) (2017), 71-88. · Zbl 1366.15030 |
| [43] | Shaked-Monderer N., Bomze I.M., Jarre F., Schachinger W., On the cp-rank and minimal cp factorizations of a completely positive matrix. SIAM Journal on Matrix Analysis and Applications 34 (2013), 355-368. · Zbl 1314.15025 |
| [44] | Sponsel J., Bundfuss S., D¨ur M., An improved algorithm to test copositivity. Journal of Global Optimization 52 (2012), 537-551. · Zbl 1250.65061 |
| [45] | Sponsel J., D¨ur M., Factorization and Cutting Planes for Completely Positive Matrices by Copositive Projection. Mathematical Programming 143 (2014), 211-229. · Zbl 1286.90106 |
| [46] | Tanaka, A., Yoshise, A., An LP-based algorithm to test copositivity. Pacific Journal of Optimization 11 (2015), 101-120. · Zbl 1327.90181 |
| [47] | Zass R., Shashua A., A Unifying Approach to Hard and Probabilistic Clustering. International Conference on Computer Vision (ICCV) Beijing, China, Oct 2005. {\it Acknowledgement: }The MFO and the workshop organizers would like to thank the National Science Foundation for supporting the participation of junior researchers in the workshop by the grant DMS-1641185, “US Junior Oberwolfach Fellows”. Copositivity and Complete Positivity3077 Workshop: Copositivity and Complete Positivity Table of Contents Kurt Anstreicher (joint with Sam Burer and Peter Dickinson) {\it An Algorithm to Compute the CP-Factorization of a Completely Positive} {\it Matrix }. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3079 Abraham Berman {\it Completely Positive Matrices – Real, Rational and Integral }. . . . . . . . . . . 3081 Peter J.C. Dickinson (joint with Immanuel M. Bomze and Georg Still) {\it The structure of completely positive matrices according to their CP-rank} {\it and CP-plus-rank }. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3082 Gabriele Eichfelder (joint with Immanuel M. Bomze, Carmo Bras and Joaquim Judice) {\it Global Optimization Techniques for Copositivity Testing }. . . . . . . . . . . . . . 3084 Shaun Fallat (joint with Charles Johnson and Alan Sokal) {\it On Continuous Powers of Certain Positive Matrices }. . . . . . . . . . . . . . . . . 3087 Markus Gabl (joint with Immanuel M. Bomze) {\it A Copositive Approach to Adjustable Robust Optimization with Uncertain} {\it Recourse }. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3088 Patrick Groetzner (joint with Mirjam D¨ur) {\it Factorizations for completely positive matrices based on projection} {\it approaches }. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3089 Roland Hildebrand {\it Extremal copositive matrices: approach via zero support sets }. . . . . . . . . . 3092 Florian Jarre (joint with Felix Lieder, Ya-Feng Liu, and Cheng Lu) {\it The Max-Cut Polytope, the Unit Modulus Lifting, and their} {\it set-completely-positive representations }. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3093 Michael Kahr (joint with Immanuel M. Bomze and Markus Leitner) {\it Quadratic Optimization with Uncertainty in the Objective Function:} {\it Theory and Practice of a Robust Approach }. . . . . . . . . . . . . . . . . . . . . . . . . . 3094 Steve Kirkland (0, 1) {\it Matrices and the Analysis of Social Networks }. . . . . . . . . . . . . . . . . . 3095 Olga Kuryatnikova (joint with Juan C. Vera) {\it Approximating the cone of copositive kernels to estimate the stability} {\it number of infinite graphs }. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3097 Thomas Laffey (joint with Helena ˇSmigoc) {\it Rank Restrictions in the NIEP }. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3098 3078Oberwolfach Report 52/2017 Raphael Loewy {\it Maximal exponents of polyhedral cones }. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3101 Justo Puerto {\it An exact copositive programming formulation for the Discrete Ordered} {\it Median Problem }. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3103 Naomi Shaked-Monderer {\it SPN graphs: when copositive }= {\it SPN }. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3106 Helena ˇSmigoc (joint with Richard Ellard) {\it Constrctructive Techniques in the Symmetric Nonnegative Inverse} {\it Eigenvalue Problem }. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3106 Juan C. Vera (joint with Luis F. Zuluaga) {\it Positive polynomials on unbounded domains }. . . . . . . . . . . . . . . . . . . . . . . . 3108 E. Alper Yıldırım {\it Mixed Integer Linear Programming Formulations of Standard Quadratic} {\it Programs }. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3109 Xiao-Dong Zhang (joint with Jiong-Sheng Li) {\it CP rank of Graphs }. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3113 Luis F. Zuluaga (joint with Xiaolong Kuang, Bissan Ghaddar, and Joe Naoum-Sawaya) {\it Alternative SDP and SOCP Approximations for Polynomial} {\it Optimization }. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3114 Copositivity and Complete Positivity3079 Abstracts An Algorithm to Compute the CP-Factorization of a Completely Positive Matrix Kurt Anstreicher (joint work with Sam Burer and Peter Dickinson) Let Sndenote the set of n × n real symmetric matrices. The cone of n × n completely positive (CP) matrices is Cn= {X ∈ Sn| ∃A ≥ 0, X = AAT}. The dual of Cnis the cone of n×n copositive (CoP) matrices, Cn∗= {X ∈ Sn| yTXy ≥ 0 ∀ y ∈ Rn+}. Recent interest in CP and CoP matrices from the optimization community stems from fact that a large class of NP-Hard optimization problems can be written as linear optimization problems over these cones [4]. A fundamental problem for CP matrices is to determine if a given matrix C is CP, and if so compute a CP-factorization C = AATwhere A is a nonnegative matrix. Virtually all literature on this problem is remarkably recent. Berman and Rothblum [3] show that the question of whether or not C ∈ Cncan be resolved by a finite algorithm using quantifier elimination, with an operation complexity of nO(n5). Several subsequent papers [12, 13, 14, 8] consider more practical approaches, resulting in algorithms which are implementable but lack a complexity bound. Our goal is to create an implementable method to determine whether a given C ∈ Cn, but which also has a complexity bound in terms of n and the geometry of Cn. If C ∈ Cnthen the algorithm should compute a CP-factorization C = AAT, while if C /∈ Cnthe algorithm should produce a “certificate” X ∈ Cn∗ with hC, Xi < 0. Our approach is based on considering an optimization problem of the form CPTest :z∗=min hC, Xi 13 2≤ hS, Xi ≤2 X ∈ Cn∗ where S ∈ Int(Cn). Then C ∈ Cn⇐⇒ z∗≥ 0. We consider a cutting-plane algorithm for CPTest, using the “fat slice”12≤ hS, Xi ≤32in place of a normalization such as hS, Xi = 1 so as to have a non-empty interior for the feasible region. The cutting-plane algorithm requires a separation oracle for X ∈ Cn∗. A particularly simple oracle can be based on a result of Hadeler [11] on almost copositive matrices. A matrix X ∈ Snis called {\it almost copositive }if X is not copositive, but every principal submatrix of X is copositive. Hadeler proved that if X is almost copositive, then X is nonsingular and X−1e < 0. Note that for such a matrix, v = −X−1e > 0 and vTXv = −eTv < 0, certifying that X /∈ Cn∗. It is also easy to see that if X is not copositive, then X has a principle submatrix that is almost copositive. Enumerating all principle submatrices of X then either obtains v ≥ 0 with vTXv < 0, or proves that X is copositive. The resulting oracle for membership in Cn∗has a complexity of O(2nn3) using standard linear algebra. If X has 3080Oberwolfach Report 52/2017 rational components and X /∈ Cn∗, the size of the certificate v ≥ 0 with vTXv < 0 is also polynomially bounded in the size of X [9]. A more complex oracle that has the possibility of running faster, particularly in the case where X ∈ Cn∗, can be based on a finite branch-and-bound algorithm for nonconvex QP [5]. Let F denote feasible region of CPTest. We assume that F is contained in BR(0), a ball of radius R in Frobenius norm centered at the origin, and contains a ball of radius r. For X ∈ Sn, let svec(X) be the vector in RN, N = n(n + 1)/2 obtained by “stacking” the elements in the upper triangle of X. The cutting-plane algorithm for CPTest is based on maintaining a sequence of ellipsoids Ek, k ≥ 0 each of which must contain the solution x∗= svec(X∗) of CPTest. The goal is to obtain an ǫ-optimal solution. We will specify the algorithm to run for a fixed number of iterations K, and give a complexity result for K in terms of r, R and ǫ. There are several possibilities for obtaining Ek+1from Ek. For example, using the central-cut ellipsoid algorithm [9], an ǫ-optimal solution of CPTest is obtained in K = ⌈2N2ln(4R2kCk/(ǫr))⌉ iterations. For CPTest with S = I +√4n1we can take r =5n2and R = (32)n, and an ǫ-optimal solution is obtained in K =2ln(45n2.5kCk/ǫ)m iterations. If the algorithm returns vbest= hC, Xbesti ≥ ǫ, then we have a proof that C ∈ Cn, while if vbest< 0 then we know that C /∈ Cn(with certificate Xbest∈ Cn∗). If the algorithm returns 0 ≤ vbest< ǫ then the status of C is indeterminate. In the case that vbest≥ ε we can solve an auxiliary linear program to obtain an explicit CP-factorization of C from the cuts generated in the course of running the algorithm. This factorization has the form C =XλiviviT+Xuij(ei+ ej)(ei+ ej)T, 1≤i≤I1≤i≤j≤n where vi, i = 1, . . . , I, I ≤ K are the set of cuts returned by the copositive separation oracle and the vectors (ei+ ej) arise from a polyhedral outer approximation of Cn∗for which intersection with the “fat slice” is contained in BR(0). The variables λi, 1 ≤ i ≤ I and uij, 1 ≤ i ≤ j ≤ n are all nonnegative and at most N of these variables are strictly positive. As C approaches the boundary of Cn, the solution value z∗→ 0, so we need ε → 0 to demonstrate that C ∈ Cnand produce a CP-factorization. It is easy to relate the required ε to the interiority of C. Note that if Bδ(C) ∈ Cn, and X is in the fat slice12≤ hS, Xi ≤32, then δδ kSkS, Xi = hC, Xi −kSkhS, Xi ≥ 0 δδ2δ kSkhS, Xi ≥2kSk≥5√n, so if Bδ(C) ∈ Cnit suffices to take ε =52δ√n. Using the ellipsoid algorithm with rational arithmetic, if C is rational we can polynomially bound the size of all cuts and intermediate solutions produced by the algorithm. As a corollary, we obtain Copositivity and Complete Positivity3081 the result that if C ∈ Int(Cn) is rational then C has a rational CP factorization, as shown independently in [10]. Note that the size of this factorization will also increase polynomially in δ. This fact is closely related to the question of whether or not determining that C ∈ Cnis actually in NP [6]. Using the volumetric cutting-plane algorithm [15, 1, 2] in place of the ellipsoid algorithm reduces the number of oracle calls by a factor of O(N ), and also reduces the potential number of cut matrices viviTneeded to obtain a CP-factorization from O∗(N2) to O(N ). Alternatively one could apply the analytic center cuttingplane method [7], in which case one loses polynomiality in ε but expects good performance in practice. References |
| [48] | K. M. Anstreicher. On Vaidya’s volumetric cutting plane method for convex programming. Math. Oper. Res., 22(1):63-89, 1997. · Zbl 0871.90061 |
| [49] | K. M. Anstreicher. Towards a practical volumetric cutting plane method for convex programming. SIAM J. Optim., 9:190-206, 1999. · Zbl 1032.90525 |
| [50] | A. Berman and U. G. Rothblum. A note on the computation of the CP-rank. Linear Algebra Appl., 419:1-7, 2006. · Zbl 1105.65038 |
| [51] | S. Burer. On the copositive representation of binary and continuous nonconvex quadratic programs. Math. Prog., 120:479-495, 2009. · Zbl 1180.90234 |
| [52] | S. Burer and D. Vandenbussche. A finite branch-and-bound algorithm for nonconvex quadratic programming via semidefinite relaxations. Math. Prog., 113:259-282, 2008. · Zbl 1135.90034 |
| [53] | P. J. C. Dickinson and L. Gijben. On the computational complexity of membership problems for the completely positive cone and its dual. Computational Optim. Appl. 57:403-415, 2014. · Zbl 1330.90103 |
| [54] | J.-L. Goffin, Z.-Q. Luo, and Y. Ye. Complexity analysis of an interior cutting plane method for convex feasibility problems. SIAM J. Optim., 6(3):638-652, 1996. · Zbl 0856.90088 |
| [55] | P. Groetzner and M. D¨ur. A factorization method for completely positive matrices. Working paper, University of Trier, 2017. |
| [56] | M. Gr¨otschel, L. Lov´asz, and A. Schrijver. Geometric Algorithms and Combinatorial Optimization. Springer-Verlag (Berlin), 1988. · Zbl 0634.05001 |
| [57] | M. D. Sikiri´c, A. Sch¨urmann and F. Vallentin. Rational factroizations of completely positive matrices. Linear Algebra Appl. 523:46-51, 2017 · Zbl 1369.90121 |
| [58] | K. P. Hadeler. On copositive matrices. Linear Algebra Appl. 49:79-89, 1983. · Zbl 0506.15016 |
| [59] | K. Schmallowsky and F. Jarre. On the computation of C∗certificates. J. Global Optim. 45:281-296, 2009. · Zbl 1190.65067 |
| [60] | J. Nie. The A-truncated K-moment problem. Foundations of Computational Mathematics 14:1243-1276, 2014. · Zbl 1331.65172 |
| [61] | J. Sponsel and M. D¨ur. Factorization and cuting planes for completely positivite matrices by copositive projection. Math.Prog., 143:211-229, 2014. · Zbl 1286.90106 |
| [62] | P. Vaidya. A new algorithm for minimizing convex functions over convex sets. Math. Program., 73:291-341, 1996. Completely Positive Matrices – Real, Rational and Integral Abraham Berman A matrix A is completely positive (cp) if it can be decomposed as A = BBT, where the entries of B are nonnegative. Completely positive matrices have important applications as is evident in this workshop. The talk is a survey of results on cp matrices and two open problems. 3082Oberwolfach Report 52/2017 A necessary condition for an n × n matrix A to be completely positive is that it is doubly nonnegative (dnn), i.e. positive semidefinite and nonnegative. This condition is also sufficient if n < 5, but for every n > 4 there exists a doubly nonnegative matrix that is not completely positive. A graph G has the property that every doubly nonnegative matrix realization of G is completely positive if and only if G does not contain an odd cycle of length greater than 4. A sufficient condition for a nonnegative matrix A to be completely positive is that its comparison matrix M (mii= aii, mij= −aijif i 6= j) is positive semidefinite. This condition is, in general, not necessary, but it is also necessary if G(A), the graph of A, is triangle free. If A = BBT, where the entries of B are rational and nonnegative, we say that A has a rational cp factorization. Question 1. {\it Does every rational completely positive matrix have a rational cp} {\it factorization?} Cases when this is true include: • G(A) is triangle free, • G(A) does not contain an odd cycle of length greater than 4, • M(A) is positive semidefinite, • A is in the interior of the cone of completely positive matrices. If A = BBT, where the entries of B are integral and nonnegative, we say that A has an integral cp factorization. If G is a graph that has a vertex of degree greater than 1, then there is an integral completely positive matrix realization of G that does not have an integral cp factorization. Question 2. {\it Does every }2 × 2 {\it integral completely positive matrix have an integral} {\it cp factorization?} The structure of completely positive matrices according to their CP-rank and CP-plus-rank Peter J.C. Dickinson (joint work with Immanuel M. Bomze and Georg Still) This talk is a presentation of a joint paper by the speaker, Peter J.C. Dickinson, together with co-authors, Immanuel M. Bomze and Georg Still [3]. An important property of completely positive matrices is their cp-ranks (see e.g. [1, Chapter 3]), and here we introduce the closely related cp-plus-rank. The definitions of these for a nonzero symmetric matrix A ∈ Sn{O} are respectively cp(A) := infp ∈ N : ∃B ∈ Rp×n+s.t. A = BBT , cp+(A) := infp ∈ N : ∃B ∈ Rp×n++s.t. A = BBT , Copositivity and Complete Positivity3083 where Rp×n+denotes the set of entrywise nonnegative p × n matrices and Rp×n++ denotes the set of entrywise strictly positive p × n matrices. Due to the subtle similarities and differences between the cp-plus-rank and the cp-rank, the analysis of the cp-plus-rank is highly useful in the investigation of the cone of completely postive matrices. One result that is presented is on how cp-plus-ranks vary in a neighbourhood. For any matrix A ∈ Sn, there is an open neighbourhood of A in Snsuch that the cp-ranks of matrices in this neighbourhood are greater than or equal to the cp-rank of A [5]. For the cp-plus-rank the opposite is true: for any matrix A ∈ Sn, not on the boundary of the completely positive cone, there is an open neighbourhood of A in Snsuch that the cp-plus-ranks of matrices in this neighbourhood are less than or equal to the cp-plus-rank of A. As a result we have that, in the interior of the completely positive cone, the set of matrices whose cp-rank and cp-plus-rank both equal a fixed number is an open set. Further analysis is provided by considering Perron-Frobenius vectors and semialgebraic sets, showing that: • If A is a complete positive matrix with an entrywise strictly positive eigenvector x then for all µ > 0 the cp-plus-rank of A + µxxTis less than or equal to the cp-rank of A. • Letting pnbe the maximum finite cp-rank of matrices in Sn(bounds on which are known [1, 2, 4]), we have that the maximum finite cp-plus-rank of matrices in Snis between pnand pn+ 1. • Generically the cp-plus-rank of a matrix is equal to its cp-rank. Two open questions connected to this research are: (1) What is the maximum finite difference between the cp-plus-rank and the cp-rank of a matrix? (2) What is the maximum finite cp-plus-rank of matrices in Sn? The speaker would like to gratefully acknowledge support from the Netherlands Organisation for Scientific Research (NWO) through grant no. 613.009.021. References |
| [63] | A. Berman and N. Shaked-Monderer, Completely Positive Matrices, World Scientific (2003). · Zbl 1030.15022 |
| [64] | I.M. Bomze, W. Schachinger and R. Ullrich, New Lower Bounds and Asymptotics for the cp-Rank, SIAM Journal on Matrix Analysis and Applications, 36:1 (2015), 20-37. · Zbl 1326.15050 |
| [65] | P.J.C. Dickinson, I.M. Bomze and G. Still, The structure of completely positive matrices according to their CP-rank and CP-plus-rank, Linear Algebra and its Applications 482 (2015), 191-206. · Zbl 1321.15053 |
| [66] | N. Shaked-Monderer, A. Berman I.M. Bomze, F. Jarre and W. Schachinger, New results on the cp-rank and related properties of co(mpletely )positive matrices, Linear and Multilinear Algebra 63:2 (2015), 384-396. · Zbl 1310.15064 |
| [67] | N. Shaked-Monderer, I.M. Bomze, F. Jarre and W. Schachinger, On the cp-rank and minimal cp factorizations of a completely positive matrix, SIAM Journal on Matrix Analysis and Applications 34:2 (2013), 355-368. 3084Oberwolfach Report 52/2017 Global Optimization Techniques for Copositivity Testing Gabriele Eichfelder (joint work with Immanuel M. Bomze, Carmo Bras and Joaquim Judice) This talk intends to give an introduction to the basic techniques used in recent numerical algorithms [3, 7, 6, 1, 2] for testing a matrix on copositivity. This means that given a real symmetric matrix Q ∈ Snthese algorithms aim on deciding whether this matrix is copositive or not. Thereby we write Q ∈ COP if and only if ∀ x ∈ Rn+: x⊤Qx ≥ 0. Within this talk we are only interested in tests which are implemented, apply to general symmetric matrices without any structural assumptions or dimensional restrictions and which are not recursive, i.e., do not rely on information taken from all principal submatrices. The relation between copositivity testing and global optimization is obvious in view of the following quadratic optimization problem: min f (x) :=12x⊤Qx (QP-Q)s.t.e⊤x = 1 x ∈ Rn+ where e ∈ Rndenotes the all-one vector. If Q is not positive semidefinite then the optimization problem (QP-Q) has a nonconvex objective function and solving it numerically requires techniques from global optimization. As the feasible set is compact, (QP-Q) has always an optimal solution and the optimal value is nonnegative if and only if Q is copositive. The algorithms [3, 7, 6, 1] are all based on a branch-and-bound scheme, where the branching corresponds to a partitioning of the standard simplex ∆s:= {x ∈ Rn+| e⊤x = 1}. Assume that one partitions the standard simplex ∆sinto two subsimplices B1and B2with B1∪ B2= ∆sand with Bi= conv(vi1, . . . , vni), i = 1, 2 with vji∈ ∆sfor all i = 1, 2, j = 1, . . . , n. Then one uses that a matrix Q ∈ Snis copositive if and only if x⊤Qx ≥ 0 for all x ∈ B1and x⊤Qx ≥ 0 for all x ∈ B2, i.e. if and only if minx∈B1x⊤Qx ≥ 0 and minx∈B2x⊤Qx ≥ 0 . For the bounding within the branch-and-bound scheme efficient sufficient criteria for copositivity are required which can easily be applied also to subsimplices. To give an example from [3]: ∀ j, k ∈ {1, . . . , n} : (vj1)⊤Qvk1≥ 0 ⇒ minx⊤Qx ≥ 0. x∈B1 Thus here one tries to verify for the subsimplex B1that minx∈B1x⊤Qx ≥ 0 as this implies that the set B1does no longer need to be considered. This requires to evaluate a finite number of inequalities only. While evaluating this sufficient condition one might also find a vector v ∈ B1with v⊤Qv < 0. This implies that the matrix Q is not copositive and the algorithm can be stopped. Another criterium Copositivity and Complete Positivity3085 which we present in this talk was proposed in [1] and uses the representation of the objective function of (QP-Q) as a difference of two convex functions, called d.c. decomposition. Thereby one uses the spectral decomposition of the matrix Q, Q = Q+− Q−with Q+and Q−positive semidefinite, which we define as follows: let Q = U ΛU⊤with the matrix U := [u1, . . . , un] consisting of orthonormal eigenvectors uiof Q, Λ := diag[(λi)]ithe diagonal matrix with the real eigenvalues of Q, Λ+:= diag[(λi)+]iwith (λi)+:= max{0, λi}, i = 1, . . . , n, and Q+:= U Λ+U⊤and Q−:= Q+− Q . Then Q ∈ COP if and only if inf{x⊤Q+x | x⊤Q−x = 1, x ∈ Rn+} ≥ 1. Relaxations of the latter optimization problem which uses this d.c. decomposition lead to sufficient conditions for copositivity which can also be modified to be applicable to subsimplices. Moreover, in this talk convergence results and test sets for the numerical evaluation of these algorithms are shortly discussed. Typical random test matrixes which are used are of the form P + N for P positive semidefinite and N a nonnegative matrix. Then all these matrices are copositive. Typically, also for large random matrices as for n = 200 copositivity can be verified easily by the mentioned algorithms. Random matrices with unit diagonal and with off-diagonal entries in the interval [−1, 1] are with a high probability non-copositive and the algorithms also detect that generally within a few iterations. The smallest matrix which tends to cause numerical difficulties is the famous Horn-matrix H, see [5], which is copositive but not of the form P + N : 1−111−1 −11−111 H =1−11−11. 11−11−1 −111−11 Other hard test instances are a result of the following reformulation of the maximum clique problem: given a simple (i.e. loopless and undirected) graph a clique is a subset of the node set such that every pair of nodes in the clique is connected by an edge of the graph. A clique is said to be a maximum clique if it contains the most elements among all cliques, and its size ω(G) is called the (maximum) clique number. It holds that the matrices Q = λ(En− AG) − Enwith Enthe n × n all-ones matrix, AG= [aij]i,jthe adjacency matrix of the graph G, and λ ≥ 0 are copositive if and only if λ ≥ ω(G). To be more concrete [6]: ∈ intCOPif λ > ω(G) λ(En− AG) − En∈ bdCOPif λ = ω(G) 6∈ COPif λ < ω(G). 3086Oberwolfach Report 52/2017 where intCOP denotes the interior of the cone of copositive matrices and bdCOP its boundary. If λ(En− AG) − En6∈ COP for some λ ∈ N, then we can conclude that ω(G) ≥ λ + 1 and by that one can generate lower bounds for the maximum clique number. In general, only lower bounds are calculated as verifying copositivity tends to be more difficult than testing for non-copositivity. For the concrete test instances see [4]. Finally, we also point out a relation between copositivity testing and the following mathematical program with linear complementarity constraints: min12λ s.t.w=Qx − λe (MPLCC)x ≥ 0, w ≥ 0 x⊤w=0, e⊤x = 1 x ∈ Rn, λ ∈ R, w ∈ Rn. It holds that Q ∈ COP if and only if (MPLCC) has a (globally) minimal solution (¯x, ¯λ, ¯w) with ¯λ ≥ 0. Instead of solving (MPLCC) directly one studies instead the following linear complementarity problem: Find x ∈ Rnand w ∈ Rnsuch that w= Qx − λe (LCP) x≥ 0, w ≥ 0 x⊤w= 0. Pairs (¯x, ¯w) ∈ Rn× Rnwhich satisfy the (LCP) with ¯x 6= 0 deliver feasible points for the (MPLCC). References |
| [68] | I.M. Bomze and G. Eichfelder, Copositivity detection by difference-of-convex decomposition and ω-subdivision, Mathematical Programming Ser. A 138 (2013), 365-400. · Zbl 1267.65060 |
| [69] | C. Br´as, G. Eichfelder, and J. J´udice, Copositivity tests based on the Linear Complementarity Problem, Computational Optimization and Applications 62 (2016), 461-493. · Zbl 1360.90245 |
| [70] | S. Bundfuss and M. D¨ur, Algorithmic copositivity detection by simplicial partition, Linear Algebra Appl. 428 (2008), 1511-1523. · Zbl 1138.15007 |
| [71] | DIMACS:SecondDIMACSChallenge,Testinstancesavailableat http://dimacs.rutgers.edu/challenges, last accessed 13 Jan. 2010. |
| [72] | M. Jr. Hall and M. Newman, Copositive and completely positive quadratic forms, Proceedings of the Cambridge Philosophical Society 59 (1963) 329-339. · Zbl 0124.25302 |
| [73] | J. Sponsel, S. Bundfuss and M. D¨ur, An improved algorithm to test copositivity, Journal of Global Optimization 52 (2012), 537-551. · Zbl 1250.65061 |
| [74] | J. ˇZilinskas and M. D¨ur, Depth-first simplicial partition for copositivity detection, with an application to Maxclique, Optimization Methods and Software 26 (2011), 499-510. Copositivity and Complete Positivity3087 On Continuous Powers of Certain Positive Matrices Shaun Fallat (joint work with Charles Johnson and Alan Sokal) A matrix is called totally positive TP (resp. nonnegative TN) if all of its minors are positive (resp. nonnegative). It is known that such matrices are closed under conventional multiplication, but not necessarily closed under entry-wise or Hadamard multiplication. On the other hand, a real matrix is called positive definite (resp. semidefinite) if it is symmetric and has positive (resp. nonnegative) principal minors. In this case, such matrices need not be closed under matrix multiplication, but are closed under Hadamard multiplication. One important observation to note is that any symmetric TN or TP matrix is both completely positive and co-positive. In my talk, I began with a detailed survey of existing work on continuous Hadamard and conventional powers of both totally positive and entry-wise nonnegative positive definite matrices (along with their closures). Most of the existing work has been done on the case of doubly nonnegative matrices, whereas the analogous results in the totally positive case are rather new and still have a number of distinct differences. In the doubly nonnegative case, the most celebrated result is due to Horn and Fitzgerald [2], where it is established that the critical exponent for this class of matrices under Hadamard (or entry-wise) powers is n − 2, here n is the order of the matrix. If A = (aij) is a matrix and t > 0 is an integer, the {\it Hadamard power} (or {\it entrywise power }) A◦tis defined to be the matrix with elements (A◦t)ij= atij. For each n ≥ 1, we call m(n) the {\it critical exponent }if A◦αis in one of matrix classes (DN, TP, etc.) for all α ≥ m(n), and m(n) is the smallest such real number with this property. In [2], it is shown that the critical exponent for doubly nonnegative matrices is n − 2. Let n ≥ 2, and let A be a n-by-n doubly nonnegative matrix. Then, for all real t ≥ n − 2 (t > 0 if n = 2), the Hadamard power A◦tis positive semidefinite (resp. positive-definite). Conversely, for every α < n − 2, there exists a rank two doubly nonnegtive matrix A (which must also be completely positive), such that A◦αis not doubly nonnegative. One of our main objectives was to find a critical exponent for TP matrices. We established that for n ≤ 3, the critical exponent for TP matrices is n − 2. However, for n ≥ 4, we proved that there is no critical exponent for TP matrices under Hadamard powers. Even if symmetry is imposed as a hypothesis, then we showed that the critical exponent such matrices with n ≤ 4 is n − 2, but that no critical exponent exists for n ≥ 5 (for more detailed information, please consult [1]). In this case of Hankel matrices, we can say a bit more which offers a glimpse into the connection between the doubly nonnegative case and the TP case. Recall that an m-by-n matrix A = (aij)1≤i≤m, 1≤j≤nis said to be a {\it Hankel matrix }if aij depends only on i + j, i.e. aij= ai′j′whenever i + j = i′+ j′. Hankel matrices are characterized combinatorially by the following simple but important fact: 3088Oberwolfach Report 52/2017 For an m-by-n matrix A, the following are equivalent: (a) A is Hankel. (b) Every contiguous submatrix of A is Hankel. (c) Every contiguous submatrix of A is symmetric. (d) Every contiguous 2-by-2 submatrix of A is symmetric. We proved that the critical exponent for Hankel TP matrices was again n − 2. I closed my talk by discussing critical exponents under conventional matrix powers, where much less is known in general. However, when the critical exponent is well defined, it does seem to be n − 2 as in the Hadamard case. Unfortunately, the critical exponent need not always exist even when conventional powers are well-defined, which is not always the case, such as in the co-positive setting. References |
| [75] | S.M. Fallat, C.R. Johnson, and A.D. Sokal, Total positivity of sums, Hadamard product, and Hadamard powers: Results and counterexamples. Lin. Alg. Appl. 520, 242-259 (2017). · Zbl 1359.15027 |
| [76] | C.H. FitzGerald and R.A. Horn, On fractional Hadamard powers of positive definite matrices, J. Math. Anal. Appl. 61, 633-642 (1977). A Copositive Approach to Adjustable Robust Optimization with Uncertain Recourse Markus Gabl (joint work with Immanuel M. Bomze) Robust Optimization deals with optimization problems under uncertainty. Parts or all of the parameters that describe the instance are affected by a vector valued uncertainty parameter. The goal is to find the best solution amongst those who will be feasible in any case, i.e. for all possible realizations of the uncertainty vector (see [6]). This approach, however, leads to very conservative strategies as the feasible set might be very small compared to the case without uncertainty. But if the application allows for a two-stage design, where for parts of the variables the decision can be delayed until the uncertainty is removed, we have a significantly less conservative way of modelling the decision problem at our disposal. This is the domain of adjustable robust optimization (see [7]). Here the second stage variables are defined as functions that model the adjustment of the second stage decision to the first stage decision and the uncertainty parameter. Thus we look for the best solution amongst those who in any case will allow for a feasible adjustment of the second stage variables. This increases the feasible space for the first stage decision variables compared to the setting where all variables are treated as first stage type as is the case in the robust framework. Of course, the computational cost rises, also for problems where the constraint-coefficients of the second stage variables are affected by uncertainty as well (uncertain recourse), or if the data depends quadratically on the uncertainty vector. In both cases bilinear terms emerge, such that standard reformulation strategies can not be applied. However, Copositivity and Complete Positivity3089 recently a new methodology in quadratic optimization emerged, that seems to be fit to tackle precisely this issue and to render a broader array of modeling choices viable. The idea is to reformulate non-convex quadratic problems as linear problems in lifted variables, where the feasible set is described as the convex hull of extreme points of the lifted feasible set (some pioneering work in this field has been achieved by [1, 2, 3, 4, 5]). In many interesting cases, these sets have a characterization based on convex cones. Thus, a conic-duality argument can be employed in order to characterize sets of quadratic forms which are nonnegative over a given domain. As a consequence we can for example generalize the well known S-Lemma (see [8]) in a way such that we can characterize, by means of a linear matrix inequality, non-negativity of a quadratic function over a domain described by an arbitrary number of quadratic functions. This allows us to handle uncertainty sets which are ellipsoids with holes. Introducing more structure to the uncertainty set allows for modeling more information into the set of possible outcomes of the uncertainty, thus reducing the conservativeness of the model. References |
| [77] | Anstreicher, Kurt M and Burer, Samuel, Computable representations for convex hulls of low-dimensional quadratic forms, Mathematical Programming 124 (2010), 33-43. · Zbl 1198.90311 |
| [78] | Sturm, Jos F and Zhang, Shuzhong, On cones of nonnegative quadratic functions, Mathematics of Operations Research 28 (2003), 246-267. · Zbl 1082.90086 |
| [79] | Burer, Samuel and Anstreicher, Kurt M, Second-order-cone constraints for extended trustregion subproblems, SIAM Journal on Optimization 23 (2013), 432-451. · Zbl 1298.90062 |
| [80] | Burer, Samuel and Yang, Boshi, The trust region subproblem with non-intersecting linear constraints, Mathematical Programming 149 (2015), 253-264. · Zbl 1308.90121 |
| [81] | Yang, Boshi and Burer, Samuel, A Two-Variable Approach to the Two-Trust-Region Subproblem, SIAM Journal on Optimization 26(1) (2016), 661-680. · Zbl 1333.90087 |
| [82] | Ben-Tal, Aharon, and Arkadi Nemirovski, Robust solutions of uncertain linear programs., Operations research letters 25 (1999), 1-13. · Zbl 0941.90053 |
| [83] | Ben-Tal, Aharon and Goryashko, Alexander and Guslitzer, Elana and Nemirovski, Arkadi, Adjustable robust solutions of uncertain linear programs, Mathematical Programming 99 (2004), 351-376. · Zbl 1089.90037 |
| [84] | Yakubovich, Vladimir A, S-procedure in nonlinear control theory, Vestnik Leningrad University 1 (1971),62-77. Factorizations for completely positive matrices based on projection approaches Patrick Groetzner (joint work with Mirjam D¨ur) A matrix A is called completely positive, if there exists an entrywise nonnegative matrix B such that A = BBT. The set CPnof completely positive matrices can be described as CPn:= conv{xxT| x ∈ Rn+} = {BBT| B ∈ Rn×r+}. Therefore, CPnis a proper subset of the positive semidefinite cone. Moreover, it is a closed, pointed, convex and full dimensional matrix cone, see for example [1]. 3090Oberwolfach Report 52/2017 These matrices play a major role in combinatorial and quadratic optimization. As shown in [3], even non-convex quadratic problems can be reformulated as convex problems over the completely positive cone, where the whole complexity is moved into the cone constraint. Therefore it is not surprising that checking whether a given matrix is completely positive is NP-hard, as shown in [4]. So far it is still an open question whether checking A ∈ CPnis also in NP. For a given matrix A ∈ CPnit is nontrivial to find a cp-factorization A = BBT with B ∈ Rn×r+, since this factorization would provide a certificate for the matrix to be completely positive. But this factorization is not only important for the membership to the completely positive cone, it can also be used to recover the solution of the underlying quadratic or combinatorial problem. Moreover, it is not known a priori how many columns the matrix B in a factorization A = BBThas. The minimum possible number of columns is called the cp-rank of A and is defined as cp(A) = inf{r ∈ N | ∃B ∈ Rn×r, B ≥ 0, A = BBT}. So far it is still an open question how the cp-rank of a given matrix can be computed. But, as shown in [2], we have ( rank(A) ≤ cp(A) ≤ cp+n, where cp+n:=n1for n ∈ {2, 3, 4} 2n(n + 1) − 4 for n ≥ 5. In this talk I will propose a factorization algorithm which computes the nonnegative factorization BBTof a given completely positive matrix A. This method is based on the following lemma, which can be used to transform one factorization to another. Lemma 1. {\it Let }B, C ∈ Rn×r{\it . Then }BBT= CCT{\it if and only if there exists an} {\it orthogonal matrix }Q ∈ Rr×r{\it with }BQ = C{\it .} The basic idea of the factorization algorithm is to start from an initial factorization A = ˜B ˜BTwith ˜B ∈ Rn×nnot necessarily nonnegative, and to extend ˜B to a matrix B ∈ Rn×r, where r ≥ cp(A) and A = BBT. Then Lemma 1 provides the means to transform this factorization A = BBTinto a cp-factorization. This problem can be formulated as a nonconvex feasibility problem and solved by a method which is based on alternating projections. In this talk I will show a local convergence result for the algorithm, which is based on results from [5] for alternating projection between semialgebraic sets. For the algorithm it is necessary to solve a second order cone problem in every projection step, which is very costly. Therefore, I will provide a heuristic extension which improves the numerical performance of the algorithm. Extensive numerical tests show that the factorization method is very fast in most instances. In addition, I will show how to derive a certificate for a matrix to be in the interior of the completely positive cone. As a second application, this method can be extended to find a general nonnegative matrix factorization for a given matrix A ∈ Rm×n, see for example [6]. Copositivity and Complete Positivity3091 For the symmetric nonnegative matrix factorization it is necessary to solve the following problem: Given A ∈ Rn×n+symmetric and k ≪ n, find a solution B ∈ Rn×k+of minkA − BBTk22. B≥0 For this, it becomes necessary to add a low-rank constraint to our factorization algorithm. Here, in contrast to the cp-factorization, the number of columns in the factorization matrix B is smaller than the order of A. If we consider the general, non-symmetric case of nonnegative matrix factorization, we are looking for a solution to the following problem: Given A ∈ Rn×m+and k ≪ min{n, m}, find solutions B ∈ Rn×k+and C ∈ Rk×m+ of minkA − BCk22. B,C≥0 Here it is necessary to extend the algorithm to the non-symmetric case. Therefore I will show an adapted version of Lemma 1 such that the main ideas of the cp-factorization algorithm can be reused to generate a nonnegative matrix factorization. I will also present numerical results for the nonnegative matrix factorization, indicating that the presented algorithm can be extended to other nonnegative factorization problems. Acknowledgement: This work was partially supported by the German-Israeli Foundation for Scientific Research and Development (GIF) through grant no. G18-304.2/2011, and partially by the German Research Foundation (DFG) through the Research Training Group 2126 “Algorithmic Optimization”. References |
| [85] | A. Berman, N. Shaked-Monderer, Completely Positive Matrices, World Scientific Publishing (2003). · Zbl 1030.15022 |
| [86] | I.M. Bomze, P.J.C. Dickinson and G. Still, The structure of completely positive matrices according to their cp-rank and cp-plus-rank, Linear Algebra and its Applications 482 (2015), 191-206. · Zbl 1321.15053 |
| [87] | S. Burer, On the copositive representation of binary and continuous nonconvex quadratic programs, Mathematical Programming 120 (2009), 479-495. · Zbl 1180.90234 |
| [88] | P.J.C. Dickinson, L. Gijben, On the Computational Complexity of Membership Problems for the Completely Positive Cone and its Dual, Computational Optimization and Applications 57 (2014), 403-415. · Zbl 1330.90103 |
| [89] | D. Drusvyatskiy, A. Ioffe, and A. Lewis, Transversality and alternating projections for nonconvex sets, Foundations of Computational Mathematics 15 (2015), 1637-1651. · Zbl 1338.49057 |
| [90] | D. Kuang, C. Ding and H. Park, Symmetric nonnegative matrix factorization for graph clustering, Proceedings of the 2012 SIAM International conference on data mining (2012), 106-117. 3092Oberwolfach Report 52/2017 Extremal copositive matrices: approach via zero support sets Roland Hildebrand Since the early days of research on copositive matrices the zeros of a copositive matrix and their support sets have been an important tool for extracting information on the facial structure of the copositive cone Cn, in particular, for describing the extreme rays of this cone. The extreme rays are of use when checking exactness of inner approximations of the copositive cone. Another application is the study of the facial structure of the dual cone, the completely positive cone. In this talk we give a review on existing and new results on extreme rays of the copositive cone and on the methods which have been developed to investigate these rays. In particular, we present the concept of reduced copositive matrices, which is a weaker condition than extremality but easier to handle. A copositive matrix A is called {\it reduced }with respect to a non-zero copositive matrix B if A − εB is not copositive for all ε > 0. A {\it zero }of a copositive matrix A ∈ Cnis a non-zero vector x ∈ R+such that xTAx = 0. The {\it support }Supp x of a zero x is the index set of its positive elements. An {\it exceptional }copositive matrix is a copositive matrix which cannot be represented as a sum of a positive semi-definite matrix and an element-wise nonnegative matrix. The zeros and their support sets have been used in [1] to establish sufficient conditions for a copositive matrix to be reduced with respect to all element-wise nonnegative matrices, which in turn is necessary for the matrix to be extremal exceptional. These conditions have been weakened to necessary and sufficient conditions in [2]. In [4] a subclass of zeros has been introduced, the {\it minimal zeros}. A zero of a copositive matrix A is called minimal if its support is minimal with respect to inclusion among all supports of zeros of A. The necessary and sufficient conditions for reducedness with respect to element-wise nonnegative matrices have been reformulated in terms of the minimal zeros of the matrix and extended to the case of reducedness with respect to positive semi-definite matrices. A number of necessary combinatorial conditions on the supports of minimal zeros of an exceptional extremal copositive matrix have been established in [4] which allowed a coarse classification of the extreme rays of the copositive cone. Examples are given for the dimensions n = 5 and n = 6. In [3] extremality of a copositive matrix A and reducedness with respect to an arbitrary copositive matrix B have been described in terms of a solution set of a linear system of equations constructed from the elements of A (and B) and from its minimal zeros. In [6] the extremal exceptional copositive matrices have been classified which possess only minimal zeros with supports of cardinality two. They are closely liked to the matrices with elements from {−1, 0, +1} which have been constructed by Hoffman and Pereira in [7]. Finally, some results are presented on extremal exceptional copositive matrices in Cnwhich possess only minimal zeros with supports of cardinality n − 2, which is the maximal possible cardinality for an exceptional extremal matrix. This class can be reduced to the subset of copositive matrices whose minimal zero support set is circulant, which have been considered in [5]. A number of directions for further research have been proposed. Copositivity and Complete Positivity3093 References |
| [91] | L.D. Baumert, Extreme copositive quadratic forms II, Pacific J. Math. 20 (1967), 1-20. · Zbl 0189.32904 |
| [92] | P.J.C. Dickinson, M. D¨ur, L. Gijben, R. Hildebrand, Irreducible elements of the copositive cone, Linear Algebra and its Applications 439 (2013), 1605-1626. · Zbl 1305.15074 |
| [93] | P.J.C. Dickinson, R. Hildebrand, Considering copositivity locally, Journal of Mathematical Analysis and Applications 437 (2016), 1184-1195. · Zbl 1382.15048 |
| [94] | R. Hildebrand, Minimal zeros of copositive matrices, Linear Algebra and its Applications 459 (2014), 154-174. · Zbl 1309.15050 |
| [95] | R. Hildebrand, Copositive matrices with circulant zero support set, Linear Algebra and its Applications 514 (2017), 1-46. · Zbl 1349.15092 |
| [96] | R. Hildebrand, Extremal copositive matrices with minimal zero supports of cardinality two, Published online in: Linear and Multilinear Algebra (2017), 1-5. |
| [97] | A.J. Hoffman, F. Pereira, On copositive matrices with -1,0,1 entries, J. Comb. Theory A 14 (1973), 302-309. The Max-Cut Polytope, the Unit Modulus Lifting, and their set-completely-positive representations Florian Jarre (joint work with Felix Lieder, Ya-Feng Liu, and Cheng Lu) A generalization of the “max-cut polytope” conv{xxT| |xk| = 1 for 1 ≤ k ≤ n} in the space of real symmetric n × n-matrices with all-ones-diagonal is considered, namely a complex “unit modulus lifting” UMLC:= conv{xx∗| |xk| = 1 for 1 ≤ k ≤ n} in the space of complex Hermitian n×n-matrices with all-ones-diagonal. (Here, x∗ denotes the transpose of the complex conjugate of x.) The problem of minimizing a linear objective function over UMLCarises for example in digital communication, robust optimization and robust control. While it is possible to generalize the Goemans-Williamson approach [2] to such problems, see [4, 1], these problems are NP-hard in general, and thus, tight convex relaxations are of interest. An explicit description of UMLCby inequality constraints is not known. Setcompletely positive representations, however are possible and presented here. The notion of cp-rank is generalized to set-completely-positive sets. Set-completelypositive representations of the max-cut polytope and of UMLCare compared, and a set of matrices at the boundary of max-cut polytopes in dimension n × n is defined for which the generalized cp-rank is not monotone with n. For UMLCthe generalized cp-rank is used to bound the number of variables in a nonconvex formulation for the membership problem for UMLC. For n = 3, it is shown that UMLCcoincides with its semidefinite relaxation and for n = 4 matrices belonging to the semidefinite relaxation are defined that do not belong to UMLC. A candidate for a separating hyperplane (H, α) is discussed along with rotations of this hyperplane that also form valid inequalities for UMLC if (H, α) is valid. While the verification of the validity of (H, α) may be tractable using global optimization packages (and can then be applied to 4 × 4 submatrices 3094Oberwolfach Report 52/2017 also in higher dimensions) compact representations of these rotations remain open. Also the question of whether rotations and permutations of these hyperplanes describe UMLCfor n = 4 remains open for now. A preprint associated with this talk was posted on [3] after the workshop in Oberwolfach. References |
| [98] | A. Bandeira, Convex relaxations for certain inverse problems on graphs, Ph.D. Thesis, Princeton (2015). |
| [99] | M.X. Goemans and D.P. Williamson, Improved Approximation Algorithms for maximum cut and satisfiability problems using semidefinite programming, Journal of ACM, 42 (1995) 1115-1145. · Zbl 0885.68088 |
| [100] | F. Jarre, F. Lieder, Y.-F. Liu, and Ch. Lu, The Max-Cut Polytope, the Unit Modulus Lifting, and their set-completely-positive representations, Preprint (2017), available at http://www.optimization-online.org/DB_HTML/2017/11/6316.html · Zbl 1464.90050 |
| [101] | A. M-C. So, J.-W. Zhang, and Y.Y. Ye, On approximating complex quadratic optimization problems via semidefinite programming relaxations, Math. Program. 110, No. 1 (2007) 93– 110. Quadratic Optimization with Uncertainty in the Objective Function: Theory and Practice of a Robust Approach Michael Kahr (joint work with Immanuel M. Bomze and Markus Leitner) Numerous practically relevant optimization problems confront decision makers with uncertain input data, which naturally arises, for instance, if the true data is revealed in future but decisions need to be made now. In order to tackle that uncertainty, two strategies asserted themselves during the last decades, i.e., {\it Sto-} {\it chastic Optimization }[3] and {\it Robust Optimization }[7]. The former is typically applied if the probability distribution of the data realizations is known, whereas the latter is usually used if only bounds on the data realizations can be estimated. In this talk we focus on the framework of Robust Optimization, in which the uncertain data realizations are assumed to be bounded by {\it uncertainty sets}. Thereby, the objective is to identify optimal solutions that are robust against all data realizations therein. We consider a robust variant of the {\it Standard Quadratic Problem }(StQP) which is, despite of its simplicity, quite versatile and has numerous applications in research areas from different domains in which data uncertainty may arise, e.g., Finance (Markowitz portfolio selection), Economics (evolutionary algorithms), Graph Theory (graph clustering), Machine Learning (image analysis) and Ecology (replicator dynamics). In particular we discuss the robust counterpart of the StQP in which uncertainty affects the objective function and its corresponding copositive reformulation [1]. It turns out that for the StQP, the usual box-, spectrahedron-, or ball-shaped uncertainty sets do not add complexity to the robust counterpart. Copositivity and Complete Positivity3095 We also discuss the case of polyhedral uncertainty sets, in which case we propose a copositive relaxation which can be obtained in two ways (a) by applying Sion’s theorem to the conic formulation or (b) by relaxing the robust counterpart (resulting in a QCQP) by a copositive formulation as in [2]. The findings are then applied to a robust variant of the {\it Dominant-Set Cluster-} {\it ing Problem }(DSCP) introduced by Pavan [5] which aims to identify homogeneous clusters in a graph. Application areas include, e.g, video analysis, image segmentation, human action recognition, and community detection in social networks. Pavan showed that the DSCP has an equivalent StQP formulation, i.e., optimizing the quadratic form of the weighted adjacency matrix of the input graph, generalizing the famous Motzkin/Straus theorem [4]. For a comprehensive, recent review on the DSCP see [6]. We show that dominant sets are connected, and derive conditions under which dominant sets form cliques. Our computational experiments indicate that considering box- and spectrahedron-shaped uncertainty sets tend to underestimate the sizes of dominant sets, while the opposite is true for ball-shaped uncertainty sets. References |
| [102] | I.M. Bomze, M. D¨ur, E. Klerk, C. Roos, A.J. Quist, T. Terlaky, On Copositive Programming and Standard Quadratic Optimization Problems, Journal of Global Optimization 18(4) (2000), 301-320. · Zbl 0970.90057 |
| [103] | S. Burer, On the Copositive Representation of Binary and Continuous Nonconvex Quadratic Programs, Mathematical Programming 120(2) (2009), 479-495. · Zbl 1180.90234 |
| [104] | G.B. Dantzig, Linear Programming under Uncertainty, Management Science 1(3-4) (1955), 197-206. · Zbl 0995.90589 |
| [105] | T.S. Motzkin, E.G. Straus Maxima for Graphs and a New Proof of a Theorem of Tur´an, Canadian Journal of Mathematics 17(4) (1965), 533-540. · Zbl 0129.39902 |
| [106] | M. Pavan, A New Graph-Theoretic Approach to Clustering and Segmentation, PhD Dissertation, Universit´a Ca’ Foscari di Venezia, 2004. |
| [107] | S. Rota Bul‘o, M. Pelillo, Dominant-Set Clustering: A Review, European Journal of Operational Research 262(1) (2017), 1-13. · Zbl 1403.68174 |
| [108] | A.L. Soyster, Convex Programming with Set-Inclusive Constraints and Applications to Inexact Linear Programming. Operations Research 21(5) (1973), 1154-1157. (0,1) Matrices and the Analysis of Social Networks Steve Kirkland A two-mode network can be represented by a rectangular (0, 1) matrix, where rows represent agents and columns represent events, with a 1 in the (i, j) position if agent i participates in event j, and a 0 in that position otherwise. Sociologists analyse these matrices mathematically in order to understand the relative importance of, or relationships between, the various agents and/or events. Given an m × n (0, 1) matrix A representing a two-mode network, one approach to that analysis is to consider the related (completely positive) matrices AATand ATA. Both AATand ATA represent single-mode networks, and can be easier to work with mathematically than the original rectangular matrix A. Further, the rows 3096Oberwolfach Report 52/2017 and columns of the single-mode networks are of the same type (i.e. they all represent agents, or they all represent events), so comparisons made between those entities arise more naturally from AATand ATA, avoiding the ‘apples by oranges’ properties of two-mode networks. In [1], the authors pose the question as to whether knowledge of both AAT and ATA is sufficient to reconstruct A. In general the answer is in the negative, as there are examples where A is not specified uniquely by AATand ATA; such examples exhibit data loss, since the pair of matrices AAT, ATA does not contain enough information to specify the (0, 1) matrix A. In this work, we use tools from combinatorial matrix theory in order to construct pairs of distinct m × n (0, 1) matrices A, B such that AAT= BBTand ATA = BTB, and to illuminate the relationship between such pairs of matrices. Our approach relies on the simple observation that if we have such a pair A, B, then both matrices have the same vector of row sums and the same vector of column sums; this is because those vectors are the diagonals of AAT= BBTand ATA = BTB, respectively. Consequently, the matrix E ≡ B − A is a (0, 1, −1) matrix with all row and column sums equal to 0. This last observation informs the following strategy. Start with a given m × n matrix E that is (0, 1, −1) with all row and column sums equal to 0; now look for a (0, 1) matrix A such that i) B ≡ A + E is also (0, 1), ii) AAT= BBT, and iii) ATA = BTB. The problem of finding such an A (when E is specified in advance) is equivalent to finding a (0, 1) solution to a linear system having m +n equations, and unknowns indexed by the positions in E corresponding 22 to zero entries. It turns out that this linear system (which is, in general, non– homogeneous) is always consistent, and finding such an A is equivalent to finding a (−1, 1) solution to the associated homogeneous linear system. Using this strategy, we can produce a large infinite family of pairs of (0, 1) matrices A, B satisfying i)–iii). In order to do so, first recall that a tournament matrix T of order n is a (0, 1) matrix satisfying T + TT= J − I, where J is the n × n all ones matrix. A tournament matrix of order n is called regular if its row sums are all equal to n−1(note that necessarily n has to be odd in that case). The following result of 2 McKay [3] gives an asymptotic expression for the number of regular tournament matrices of (odd) order n. Proposition 1. {\it As }n → ∞ {\it through odd values, then for any }ǫ > 0, {\it the number} tn{\it of regular tournament matrices of order }n {\it is given by} n−1 2n+12n12 tn=1 + On−12+ǫ. πne We have the following result from [2], which uses regular tournament matrices in order to construct pairs of (0, 1) matrices satisfying i)–iii). Copositivity and Complete Positivity3097 Theorem 1. {\it Suppose that }n ∈ N {\it and denote the all ones vector in }Rn{\it by }1. {\it Consider the following }(n + 1) × 2n {\it matrix:} E =−II 1T−1T. {\it There is an }(n + 1) × 2n (0, 1) {\it matrix }A {\it such that i) }A + E {\it is also }(0, 1){\it , ii)} AAT= (A + E)(A + E)T, {\it and iii) }ATA = (A + E)T(A + E) {\it if and only if }n {\it is} {\it odd.} {\it When }n {\it is odd, each }(0, 1) A {\it satisfying i)–iii) has the form} (1)A =T + ITT 0T1T, {\it where }T {\it is a regular tournament matrix of order }n. {\it Conversely, for any regular} {\it tournament matrix }T {\it of order }n{\it , the matrix }A {\it of }(1) {\it satisfies i)–iii).} In view of Proposition 1, we see that asymptotically, the number of such pairs of matrices in Theorem 1 is quite large. Observe also that the matrices of Theorem 1 are highly structured. It remains to be seen whether there are are two-mode networks that arise in empirical settings that give rise to (0, 1) pairs A, B for which AAT= BBTand ATA = BTB. References |
| [109] | M. Everett and S. Borgatti, The dual-projection approach for two-mode networks, Social Networks 35 (2013), 204-210. |
| [110] | S. Kirkland, Two-mode networks exhibiting data loss, Journal of Complex Networks, to appear. https://doi.org/10.1093/comnet/cnx039. · Zbl 1465.91081 |
| [111] | B. McKay, The asymptotic numbers of regular tournaments, Eulerian digraphs and Eulerian oriented graphs, Combinatorica 10 (1990), 367-377. Approximating the cone of copositive kernels to estimate the stability number of infinite graphs Olga Kuryatnikova (joint work with Juan C. Vera) It has been shown by Dobre, D¨ur, Frerick and Vallentin [3] that the stable set problem in certain infinite graphs, and particularly the kissing number problem, reduces to a minimization problem over the cone of copositive kernels. Optimizing over this cone is NP-hard, so we propose two converging inner hierarchies approximating the cone and implement their first two levels to compute upper bounds on the kissing number κn. Let V ⊂ Rnbe a compact set and C{\it O}P(V ) be the cone of opositive kernels over V . Our approximations of C{\it O}P(V ) extend existing inner hierarchies for copositive matrices, Crnby De Klerk and Pasechnik [2] and Qnrby Pe˜na, Vera and Zuluaga [5]. To do the extension, we represent these hierarchies via tensors, similarly to Dong [4]. We denote the new sets by CrVand QVrand show that CrV⊆ QVr⊆ C{\it O}P(V ) for every level of the hierarchies r. 3098Oberwolfach Report 52/2017 Now let us consider the kissing number problem. Let Sn−1be the unit sphere in Rn. The kissing number κnis the optimal value of an LP over C{\it O}P(Sn−1) . Denote by γrand νrupper bounds on κnobtained by replacing C{\it O}P(Sn−1) in this problem with CrSn−1and QSrn−1respectively. Then Theorem 1. γr↓ κn, νr↓ κn{\it .} Further we concentrate on νras it provides stronger upper bounds. Using invairance of Sn−1under orthogonal group On, we characterize QSrn−1uintroducing a notion of generalized Jacobi polynomials. For r = 1, our formulation is close to the best existing upper bound formulation by Bachoc and Vallentin [1], but the bounds we obtain are a little weaker. The main goal of further research is to implement νrfor r = 2. An open question is the connection between our hierarchies and other existing approximations for the kissing number problem. References |
| [112] | C. Bachoc, F. Vallentin, New upper bounds for kissing numbers from semidefinite programming. J. Amer. Math. Soc. 21-3 (2008), 909-924. · Zbl 1223.90039 |
| [113] | E. de Klerk and D. Pasechnik, Approximation of the stability number of a graph via copositive programming. SIAM J. Optim. 12 (2002), 875-892. · Zbl 1035.90058 |
| [114] | C. Dobre, M. D¨ur, L. Frerick, F. Vallentin, A Copositive Formulation for the Stability Number of Infinite Graphs. Math. Program. 160-1 (2016), 65-83. · Zbl 1361.05091 |
| [115] | H. Dong, Symmetric Tensor Approximation Hierarchies for the Completely Positive Cone. SIAM J. Optim. 23(3) (2013), 1850-1866 · Zbl 1291.90129 |
| [116] | J. Pe˜na, J.C. Vera, L.F. Zuluaga, Computing the stability number of a graph via linear and semidefinite programming. SIAM J. Optim. 18-2 (2007), 87-105. Rank Restrictions in the NIEP Thomas Laffey (joint work with Helena ˇSmigoc) The {\it nonnegative inverse eigenvalue problem }(NIEP) asks: which lists of complex numbers can be the spectrum of some entry-wise nonnegative matrix. If a list of complex numbers σ is the spectrum of some entry-wise nonnegative matrix A, we say that σ is {\it realisable}, and that A {\it realises }σ. The NIEP is a difficult open problem, however, several partial results are known. For the source of literature on the problem we refer the reader to the following works and the citations that appear in them: [3, 13, 14, 12, 9, 8, 5]. Motivated by applications in ergodic theory, Boyle and Handelman [1] solved a related question: which lists of complex numbers can be the nonzero spectrum of a nonnegative matrix. In particular, they proved that if σ = (λ1, λ2, . . . , λn) is a list of complex numbers such that the power sums sk=Pni=1λki> 0 for all positive integers k, and λ1> |λi| for i = 2, 3, . . . , n, then there exists a nonnegative integer N such that the list obtained by appending N zeros to σ is realizable by a nonnegative (n + N ) ×(n+N) matrix. It is easy to show that the least N required Copositivity and Complete Positivity3099 here is in general not bounded as a function of n. Their proof is not constructive and does not enable one to determine the size of the minimal N required for the realizability in the general case. A constructive approach to the Boyle and Handelman result that provides a bound on the minimal such N , was found by this author in [6]. Several other variants of the NIEP are considered in the literature. The one that has attracted most attention is the symmetric nonnegative inverse eigenvalue problem (SNIEP), where we demand that the realising nonnegative matrix is symmetric. The corresponding question about the nonzero spectrum of a symmetric matrix is open. Unlike in the general case, the number of zeros needed to be added to the nonzero spectrum of a symmetric nonnegative matrix in order to obtain a nonnegative symmetric realisation is bounded by a function of the number of nonzero elements in the list. Theorem 1. [4] {\it Let }A ∈ Mn(R) {\it be a symmetric nonnegative matrix of rank }k{\it .} {\it Then, there exists a symmetric nonnegative matrix }˜A ∈ Mk(k+1)/2(R) {\it with the} {\it same nonzero spectrum as }A{\it .} This result was used in the first proof that the symmetric nonnegative inverse eigenvalue problem is different from the real nonnegative inverse eigenvalue problem, the problem of determining which lists of real numbers are realisable. The bound provided in the theorem above is believed not to be tight. In fact, examples of lists where one zero added makes the list symmetrically realisable are known, for example σ = (103,83, −2, −2, −2) is not symmetrically realizable but σ ∪ {0} is; however, there are no known examples where three or more zeros are required in symmetric realisability. Here, we consider diagonal realisability. We show that if a list is the nonzero spectrum of a diagonalisable nonnegative matrix with k nonzero eigenvalues, then it can be realised by a nonnegative diagonalisable matrix of order k + k2. Our approach depends on the study of a principal sub-matrix A11of the original matrix A that has the same rank as A. Theorem 2. {\it Let} A11A12 A21A22∈ Mn(R) {\it be a nonnegative matrix, where }A11∈ Mm(R) {\it has rank equal to the rank of }A {\it and} {\it the rank of }A21{\it is equal to }r{\it . Furthermore, we assume }n > m + mr{\it .} {\it Then there exists a nonnegative matrix }˜A ∈ Mm+mr(R) {\it whose nonzero spectrum} {\it is the same as the nonzero spectrum of }A{\it . Moreover, the Jordan canonical forms of} A {\it and }˜A{\it , denoted by }J(A) {\it and }J( ˜A) {\it respectively, satisfy: }J(A) = J( ˜A)⊕0n−m−mr{\it .} Theorem 3. {\it Let }A ∈ Mn(R) {\it be a nonnegative matrix with }l {\it nonzero eigen-} {\it values and rank }k{\it .}{\it Then there exists a nonnegative matrix }˜A {\it of order }˜n = (2k − l) + (2k − l)2{\it whose nonzero spectrum is the same as the nonzero spectrum} {\it of }A {\it and whose Jordan canonical form }J( ˜A) {\it satisifes: }J(A) = J( ˜A) ⊕ 0n−˜n{\it .} 3100Oberwolfach Report 52/2017 These results show, that in the Boyle-Handelman result, the component of the Jordan canonical form of a realizing matrix corresponding to the eigenvalue zero, may be required to have large rank. The Nonnegative Inverse Elementary Divisors Problem The nonnegative inverse elementary divisors problem (NIEDP) asks: for a given realisable spectrum σ = (λ1, λ2, . . . , λn), what are the possible Jordan forms of realising matrices. Of course, if σ has no repeated entries, this problem reduces to the NIEP for σ. It is conjectured that if σ is realisable, then it is realisable by a nonnegative nonderogatory matrix, but this appears to be still open. Minc [11] proved that if σ is diagonalisably realisable by a positive matrix A, then for every Jordan form J with spectrum σ, σ is realisable by a positive matrix similar to J. This result is conjectured to hold without requiring the positivity of A but this also seems to be open at present. We consider the classic example σ(t) = (3 + t, 3 − t, −2, −2, −2). We ask the question what is the minimal t for which σ(t) is realisable by a nonnegative matrix with a given Jordan canonical form Ji(t) associated with σ(t), where J1(t) is a diagonal matrix, J2(t) is the Jordan canonical form with its minimal polynomial of degree 4, and J3(t) is nonderogatory. We will denote the minimal t in each case by ti. It is shown by Cronin and the author in [2] that σ(t) is realisable by a diagonalisable nonnegative matrix only for t ≥ 1, i.e. t1= 1. In this case, the condition for diagonalisable realisability and symmetric realisability coincide. Also, in the same paper it is shown that σ = (3 + t, 3 − t, −2.09, −2, −2.1) is realisable for t ≥101p120√3166 − 3899 ≈ 0.435, while by the McDonaldNeumann inequality, given in [10], t ≥ 0.9 is necessary for symmetric realisability.√ p On the other hand, σ(t) is realisable for t ≥166 − 39 ≈ 0.438. This is shown√ p in [7], where a nonderogatory matrix with spectrum σ(t3), t3=166 − 39, is provided. Here we present the matrix 021200 201200 A(t) =t2+7− 32t2562+7− 32010 00t4+78t2−1501√2t2+ 30. √2(t2+7)2 00√1√2t2+ 300 (t2+7)t2+152 A(t) has eigenvalues (3 + t, 3 − t, −2, −2, −2), it is nonnegative, and it has Jordan√ p canonical form J2(t), for166 − 39 ≤ t < 1. This shows that t2= t3. Copositivity and Complete Positivity3101 References |
| [117] | Mike Boyle and David Handelman. The spectra of nonnegative matrices via symbolic dynamics. Ann. of Math. (2), 133(2):249-316, 1991. · Zbl 0735.15005 |
| [118] | A. G Cronin and T. J Laffey. The diagonalizable nonnegative inverse eigenvalue problem. ArXiv e-prints, January 2017. |
| [119] | Patricia D. Egleston, Terry D. Lenker, and Sivaram K. Narayan. The nonnegative inverse eigenvalue problem. Linear Algebra Appl., 379:475-490, 2004. 10th Conference of the International Linear Algebra Society. · Zbl 1040.15009 |
| [120] | Charles R. Johnson, Thomas J. Laffey, and Raphael Loewy. The real and the symmetric nonnegative inverse eigenvalue problems are different. Proc. Amer. Math. Soc., 124(12):3647– 3651, 1996. · Zbl 0861.15007 |
| [121] | Thomas J. Laffey. Extreme nonnegative matrices. Linear Algebra Appl., 275/276:349-357, 1998. Proceedings of the Sixth Conference of the International Linear Algebra Society (Chemnitz, 1996). · Zbl 0933.15028 |
| [122] | Thomas J. Laffey. A constructive version of the Boyle-Handelman theorem on the spectra of nonnegative matrices. Linear Algebra Appl., 436(6):1701-1709, 2012. · Zbl 1241.15007 |
| [123] | Thomas J. Laffey and Eleanor Meehan. A characterization of trace zero nonnegative 5 × 5 matrices. Linear Algebra Appl., 302/303:295-302, 1999. Special issue dedicated to Hans Schneider (Madison, WI, 1998). · Zbl 0946.15008 |
| [124] | Thomas J. Laffey and Helena ˇSmigoc. Nonnegative realization of spectra having negative real parts. Linear Algebra Appl., 416(1):148-159, 2006. · Zbl 1103.15005 |
| [125] | Thomas J. Laffey and Helena ˇSmigoc. Nonnegatively realizable spectra with two positive eigenvalues. Linear Multilinear Algebra, 58(7-8):1053-1069, 2010. · Zbl 1205.15019 |
| [126] | J. J. McDonald and M. Neumann. The Soules approach to the inverse eigenvalue problem for nonnegative symmetric matrices of order n ≤ 5. In Algebra and its applications (Athens, OH, 1999), volume 259 of Contemp. Math., pages 387-407. Amer. Math. Soc., Providence, RI, 2000. · Zbl 0965.15009 |
| [127] | Henryk Minc. Inverse elementary divisor problem for nonnegative matrices. Proc. Amer. Math. Soc., 83(4):665-669, 1981. · Zbl 0472.15006 |
| [128] | Helena ˇSmigoc. The inverse eigenvalue problem for nonnegative matrices. Linear Algebra Appl., 393:365-374, 2004. · Zbl 1075.15012 |
| [129] | Ricardo Soto, Alberto Borobia, and Julio Moro. On the comparison of some realizability criteria for the real nonnegative inverse eigenvalue problem. Linear Algebra Appl., 396:223– 241, 2005. · Zbl 1086.15010 |
| [130] | Guo Wuwen. Eigenvalues of nonnegative matrices. Linear Algebra Appl., 266:261-270, 1997. Maximal exponents of polyhedral cones Raphael Loewy The purpose of this talk is to generalize the notions of nonnegative (elementwise), primitive matrices and their exponents. Given an n × n nonnegative matrix A (denoted A ≥ 0), A is said to be {\it primitive }if there exists a positive integer l such that Alis positive (denoted Al> 0). In that case, the smallest such l is called the {\it exponent }of A, denoted γ(A). A primitive matrix A can be recognized combinatorially, namely from the directed graph D(A) associated with A. Its vertex set is v = {1, 2, . . . , n}, and given two vertices i and j there is a directed edge from i to j if and only if aij> 0. The graph D(A) is called {\it primitive }if it is strongly connected and the greatest common 3102Oberwolfach Report 52/2017 divisor of the lengths of its cycles is equal to 1. It is known that A is primitive if and only if D(A) is a primitive graph. There has been great interest in exponents of primitive matrices, in particular establishing upper bounds using combinatorial and linear algebraic parameters. The following result is due to Wielandt [Wi], although a proof appeared later. In order to state his result we define, for any positive integer n, the graph Wn as follows: Its vertex set is {1, 2, . . . , n}, and the edge set is {(i, i + 1)for i = 1, 2, . . . , n − 1, (n, 1), (n, 2)}. Theorem 1. {\it Let }A {\it be an }n × n {\it nonnegative, primitive matrix. Then }γ(A) ≤ (n − 1)2+ 1 = n2− 2n + 2{\it , and inequality holds if and only if }D(A) {\it is isomorphic} {\it to }Wn{\it .} An n × n nonnegative matrix can be considered as a linear operator mapping the nonnegative orthant Rn+= {x = (xi) ∈ Rn: xi≥ 0, i = 1, 2, . . . , n} into itself. A natural generalization is the following. Suppose that K is a proper cone in Rn, that is, a cone which is convex, pointed, closed, and with non-empty interior. Given an n × n matrix A, we say that it is K-{\it nonnegative }if AK ⊂ K; it is K-{\it positive }if Ax ∈ intK for every nonzero x, x ∈ K; A is K-{\it primitive }if A is K-nonnegative and there exists a positive integer l such that Alis K-positive, and in that case the smallest such l is called the {\it exponent }of A, denoted by γK(A). Following a question by S. Kirkland in 1999 we are interested to establish upper bounds for exponents of K- primitive matrices. The results appear in [LT1, LT2, LPT]. Our main results obtain appropriate generalizations of Theorem 1. We restrict our attention to {\it polyhedral }cones, that is proper cones which have finitely many extreme rays. More precisely, we fix positive integers m,n such that m ≥ n, and consider cones in Rnwith m extreme rays. Theorem 2. {\it Let }K {\it be a proper cone in }Rn{\it with }m {\it extreme rays, and let }A {\it be} K{\it -primitive. Then,} γK(A) ≤ (n − 1)(m − 1) +12(1 + (−1)(n−1)m){\it .} Note that the case m = n in Theorem 2 reduces to the Wielandt bound. Theorem 3. {\it The inequality in Theorem 2 }{\it is best possible in the sense that there} {\it exist }K {\it in }Rn{\it with }m {\it extreme rays and }A {\it which is }K{\it -primitive such that equality} {\it holds in this inequality.} A key tool in the proof of Theorem 2 and Theorem 3 is the use of a graph introduced by Barker and Tam [BP1, BP2], which generalizes the graph D(A) in the nonnegative case. Now suppose that K is a proper polyhedral cone in Rn and A is K-nonnegative. We define the graph DK(A) as follows: Its vertices correspond to the extreme rays of K. Given extreme rays R1= {αx : α ≥ 0} and R2= {αy : α ≥ 0}, for x, y ∈ K, both nonzero, there is a directed edge from R1 to R2if and only if y belongs to the face of K generated by Ax. It should be pointed out that a significant problem in our work is when is a directed graph on m vertices realizable as DK(A) for suitable K and A. Copositivity and Complete Positivity3103 References [BP1] G. P. Barker and B. S. Tam, Graphs for cone preserving maps, Linear Algebra and Appl. 37 (1981), 199-204. [BP2] B. S. Tam and G. P. Barker , Graphs and irreducible cone preserving maps, Linear and Multilinear Algebra 31 (1992), 19-25. [LT1] R. Loewy and B. S. Tam, Maximal exponents of polyhedral cones (I), J. Math. Anal. Appl. 365 (2010), 570-583. [LT2] R. Loewy and B. S. Tam, Maximal exponents of polyhedral cones (II), Linear Algebra and Appl. 432 (2010), 2861-2878. [LPT] R. Loewy, M. A. Perles and B. S. Tam, Maximal exponents of polyhedral cones (III), Trans. of the AMS 365 (2013), 3535-3573. [Wi]H. Wielandt, Unzerlegbare, nicht negative Matrizen, Math. Z. 52 (1950), 642-645. An exact copositive programming formulation for the Discrete Ordered Median Problem Justo Puerto The discrete ordered median problem (DOMP) represents a generalization of several well-known discrete location problems, such as p-median, p-center or (k1+ k2)−trimmed mean, among many others. The problem was introduced in [10] and later studied by [11], [2], and [13], [9] and [1] among many other papers. DOMP is an NP-hard problem as an extension of the p-median problem. In 2001, Nickel [10] first presented a quadratic integer programming formulation for DOMP. However, no further attempt to deal directly with this formulation was ever considered. Furthermore, that approach was never exploited in trying to find alternative reformulations or bounds; instead several linearizations in different spaces of variables have been proposed to solve DOMP some of them being rather promising, [9] and [8]. Motivated by the recent advances in conic optimization and the new tools that this branch of mathematical programming has provided for developing bounds and approximation algorithms for NP-hard problems, as for instance max-cut, QAP, and other hard combinatorial problems [6], we present in this talk an exact alternative reformulation of DOMP as a continuous, linear conic problem. Our interest is mainly theoretical and tries to borrow tools from continuous optimization to be applied in some discrete problems in the field L.A. To the best of our knowledge reformulations of that kind have never been studied before for DOMP nor even in the wider field of L.A. The goal of our presentation was to prove that the natural binary, quadratically constrained, quadratic formulation for DOMP admits a compact, exact reformulation as a continuous, linear problem over the cone of completely positive matrices. The talk was organized as follows. The first part formally defined the ordered median problem and set its elements. The next part was devoted to describe a folk result that formulates the problem of sorting numbers as a feasibility binary linear program. This is used later as a building block to present the binary quadratic, 3104Oberwolfach Report 52/2017 quadratically constrained formulation of DOMP. The following section contained the main result: DOMP is equivalent to a continuous, linear conic problem. Obviously, there are no shortcuts and the problem remains N P -hard but it allows to shed some lights onto the combinatorics of this difficult discrete location problem. Moreover, it permits to borrow also the tools from continuous optimization to the area of L.A. Finally, we addressed some conclusions and pointers to future research. 1. Definition and formulation of the problem 1.1. Problem definition. Let S = {1, ..., n} denote the set of n sites. Let C = (cjℓ)j,ℓ=1,...,nbe a given nonnegative n × n cost matrix, where cjℓdenotes the cost of satisfying demand point (client) j from a facility located at site ℓ. We also assume the so called, {\it free self-service }situation, namely cjj= 0 for all j = 1, . . . , n. Let p < n be the desired number of facilities to be located at the candidate sites. A solution to the facility location problem is given by a set X ⊆ S of p sites. We assume, that each new facility has unlimited capacity. Therefore, each client j will be allocated to a facility located at site ℓ of X with lowest cost, i.e. cj= cj(X ) := mincjℓ. ℓ∈X The costs for supplying clients, c1(X ), ..., cn(X ), are sorted in nondecreasing order. We define σXto be a permutation on {1, ..., n} for which the inequalities cσX(1)(X ) ≤ · · · ≤ cσX(n)(X ) hold. Now, for any nonnegative vector λ ∈ Rn+, the Discrete Ordered Median Problem (DOMP) consists of finding X∗⊂ S with |X∗| = p such that: nn λkcσ(k)(X∗) =minXλkcσX(k)(X ). k=1X ⊂S,|X |=pk=1 2. Main result In this talk we prove that DOMP admits a reformulation as a mixed-binary quadratic objective, quadratically constrained problem. This problem can be always relaxed using the corresponding matrix variables that replace the original quadratic terms. Our main result is that this second reformulation, using matrix variables, is indeed exact and therefore, DOMP is a new hard combinatorial optimization problems that falls into the class of completely positive conic linear programs. See [3, 4, 5, 7, 12] and the references therein for a detailed literature review of this topic. Theorem 1. DOMP {\it belongs to the class of continuous, convex, conic problems.} {\it Moreover, an explicit formulation of }DOMP {\it as a completely positive convex prob-} {\it lem is given as CP-DOMP. Problem CP-DOMP is equivalent to the quadratic} {\it reformulation of }DOMP{\it : (i) they share the same objective value, (ii) if }Φ∗{\it is} Copositivity and Complete Positivity3105 {\it an optimal solution for Problem CP-DOMP then a suitable linear transformation} {\it of }Φ∗{\it is in the convex hull of optimal solutions of the quadratic reformulation of} DOMP{\it .} 3. Concluding remarks The result in this talk states, for the first time, the equivalence of a difficult N P -hard discrete location problem, namely DOMP, with a continuous, convex problem. This new approach can be used to start new avenues of research by applying tools in continuous optimization to approximate or numerically solve some hard discrete location problems. References |
| [131] | V. Blanco, S. El Haj Ben Ali, and J. Puerto. Revisiting several problems and algorithms in continuous location wih lτ−norm. Computational Optimization and Applications, 58(3): 563-595, 2014. · Zbl 1297.90073 |
| [132] | N. Boland, P. Dom´ınguez-Mar´ın, S. Nickel, and J. Puerto. Exact procedures for solving the discrete ordered median problem. Computers & Operations Research, 33(11):3270-3300, 2006. ISSN 0305-0548. · Zbl 1113.90099 |
| [133] | I. M. Bomze. Copositive optimization - recent developments and applications. European Journal of Operational Research, 216(3):509-520, 2012. · Zbl 1262.90129 |
| [134] | S. Burer. On the copositive representation of binary and continuous nonconvex quadratic programs. Math. Program., 120(2):479-495, 2009. · Zbl 1180.90234 |
| [135] | S. Burer. Copositive Programming, chapter 8, pages 201-218. Springer, 2012. ISBN 978-14614-0769-0. International Series in Operations REsearch and Management Science. · Zbl 1334.90098 |
| [136] | S. Burer. A gentle, geometric introduction to copositive optimization. Math. Program., 151 (1):89-116, 2015. · Zbl 1327.90162 |
| [137] | M. D¨ur. Copositive Programming – a Survey. In: M. Diehl, F. Glineur, E. Jarlebring, W. Michiels (Eds.), Recent Advances in Optimization and its Applications in Engineering, Springer 2010, pp. 3-20. |
| [138] | M. Labb´e, D. Ponce, and J. Puerto. A comparative study of formulations and solution methods for the discrete ordered p-median problem. Computers & Operations Research, 2016. ISSN 0305-0548. |
| [139] | A. Mar´ın, S. Nickel, J. Puerto, and S. Velten. A flexible model and efficient solution strategies for discrete location problems. Discrete Applied Mathematics, 157(5):1128-1145, 2009. ISSN 0166-218X. · Zbl 1163.90609 |
| [140] | S. Nickel. Discrete ordered weber problems. In Operations Research Proceedings 2000, pages 71-76. Springer Verlag, 2001. · Zbl 1050.90532 |
| [141] | S. Nickel and J. Puerto. Location Theory: A Unified Approach. Springer Verlag, 2005. · Zbl 1229.90001 |
| [142] | Javier Pe˜na, Juan C. Vera, and Luis F. Zuluaga. Completely positive reformulations for polynomial optimization. Mathematical Programming, 151(2):405-431, Jul 2015. · Zbl 1328.90114 |
| [143] | Z. Stanimirovic, J. Kratica, and D. Dugosija. Genetic algorithms for solving the discrete ordered median problem. European Journal of Operational Research, 182:983-1001, 2007. 3106Oberwolfach Report 52/2017 SPN graphs: when copositive = SPN Naomi Shaked-Monderer A real symmetric matrix A is {\it copositive }if xTAx ≥ 0 for every nonnegative vector x. A matrix is {\it SPN }if it is a sum of a real positive semidefinite matrix and a nonnegative one. Every SPN matrix is copositive, but the converse does not hold for matrices of order greater than 4. We define a graph G to be an {\it SPN} {\it graph }if every copositive matrix with graph G is SPN, and consider the problem of characterizing such graphs. We present sufficient conditions for a graph to be SPN (in terms of its possible blocks) and necessary conditions for a graph to be SPN (in terms of forbidden subgraphs), and make some conjectures regarding the remaining gap. References |
| [144] | N. Shaked-Monderer, SPN graphs: when copositive = SPN, Linear Algebra and its Applications 509 (2016), 82-113. · Zbl 1345.05111 |
| [145] | N. Shaked-Monderer, Corrigendum to “SPN graphs: when copositive = SPN”, submitted. Constrctructive Techniques in the Symmetric Nonnegative Inverse Eigenvalue Problem Helena ˇSmigoc (joint work with Richard Ellard) A list of real numbers is {\it symmetrically realisable }if it is the spectrum of some (entrywise) nonnegative symmetric matrix. The Symmetric Nonnegative Inverse Eigenvalue Problem (SNIEP) is the problem of characterising all symmetrically realisable lists. If we do not insist that the realising matrix be symmetric, then the resulting problem is called the {\it Real Nonnegative Inverse Eigenvalue Problem} (RNIEP). Several constructions have been developed that enable us to construct nonnegative matrices with given spectrum. We consider a construction presented in [7] that joins two smaller matrices to construct a bigger one. Let B be an l×l nonnegative symmetric matrix with Perron eigenvalue c, Perron eigenvector u, (Bu = cu and uTu = 1) and spectrum (c, ν2, ν3, . . . , νl). Let A :=1a aTc, where A1is an (k − 1) × (k − 1) nonnegative symmetric matrix and a ∈ Rk−1is nonnegative, have eigenvalues (µ1, µ2, . . . , µk). Then C :=1avT vaTB is a nonnegative symmetric matrix with eigenvalues (µ1, µ2, . . . , µk, ν2, ν3, . . . , νl). If A and B are positive semidefinite, then so is C. However, the question, if Copositivity and Complete Positivity3107 completely positive matrices A and B produce a completely positive matrix C, is open. We denote by Hnthe set of all symmetrically realisable lists, that can be obtained recursively, starting with lists of length 2 and repeatedly applying the construction given above. The realisable family obtained in this way has several interesting properties, [2]: (1) Let σ = (λ1, λ2, λ3, . . . , λn) ∈ Hnhave the Perron eigenvalue λ1, and let ǫ > 0. Then (λ1+ ǫ; λ2− ǫ, λ3, λ4, . . . , λn) ∈ Hnand (λ1+ ǫ; λ2+ ǫ, λ3, λ4, . . . , λn) ∈ Hn. (2) Let λ1≥ λ2≥ · · · ≥ λn. Then (λ1; λ2, . . . , λn) ∈ Hnif and only if there exist 0 ≤ ǫ ≤12(λ1− λ2) and a partition {3, 4, . . . , n} = {p1, p2, . . . , pl−1} ∪ {q1, q2, . . . , qn−l−1}, such that (λ1− ǫ; λp1, λp2, . . . , λpl−1) ∈ Hland(λ2+ ǫ; λq1, λq2, . . . , λqn−l−1) ∈ Hn−l. (3) If (λ1; λ2, . . . , λn, 0) ∈ Hn+1, then (λ1; λ2, . . . , λn) ∈ Hn. These properties allow us to make connections between a number of sufficient conditions in the SNIEP developed over forty years, starting with the work of Fiedler [4] in 1974. In particular, they enable us to show that a condition due to Borobia, Moro and Soto [1] called {\it C-realisability }is sufficient for the existence of a symmetric realising matrix, and that the set of C-realisable lists is the same as Hn, [2]. Soules’ approach to the SNIEP focuses on constructing the eigenvectors of the realising matrix A. Starting from a positive vector x ∈ Rn, Soules [6] showed how to construct a real orthogonal n × n matrix R with first column x such that for all λ1≥ λ2≥ · · · ≥ λn≥ 0, the matrix RΛRT—where Λ := diag(λ1, λ2, . . . , λn)—is nonnegative. This motivated Elsner, Nabben and Neumann [3] to make the following definition: Let R ∈ Rn×nbe an orthogonal matrix with columns r1, r2, . . . , rn. R is called a {\it Soules matrix }if r1is positive and for every diagonal matrix Λ := diag(λ1, λ2, . . . , λn) with λ1≥ λ2≥ · · · ≥ λn≥ 0, the matrix RΛRTis nonnegative. Let Sndenote the set of all lists of eigenvalues of symmetric nonnegative matrices of the form RΛRT, where R is a Soules matrix and Λ is a diagonal matrix. Then Sn= Hn, [2]. This result together with a result by Shaked-Monderer [5] that states, that nonnegative matrix generated by a Soules matrix is a completely positive matrix with cp-rank equal to the rank, connects the construction introduced earlier to cp-matrices. 3108Oberwolfach Report 52/2017 References |
| [146] | A. Borobia, J. Moro and R. L. Soto. A unified view on compensation criteria in the real nonnegative inverse eigenvalue problem. Linear Algebra and its Applications, 428(11-12):2574– 2584, June 2008. · Zbl 1145.15006 |
| [147] | R. Ellard, H. ˇSmigoc, Connecting sufficient conditions for the Symmetric Nonnegative Inverse Eigenvalue Problem, Linear Algebra and its Applications 498 (2016) 521-552, (Special issue: Legacy of Hans Schneider). · Zbl 1334.15028 |
| [148] | L. Elsner, R. Nabben and M. Neumann. Orthogonal bases that lead to symmetric nonnegative matrices. Linear Algebra and its Applications, 271(1-3):323-343, 1998. · Zbl 0891.15019 |
| [149] | M. Fiedler. Eigenvalues of nonnegative symmetric matrices. Linear Algebra and its Applications, 9:119-142, 1974. · Zbl 0322.15015 |
| [150] | N. Shaked-Monderer. A note on the CP-rank of matrices generated by Soules matrices. Electron. J. Linear Algebra, 12:2-5, 2004/05. · Zbl 1066.15022 |
| [151] | G. W. Soules. Constructing symmetric nonnegative matrices. Linear and Multilinear Algebra, 13:241-251, 1983. · Zbl 0516.15013 |
| [152] | H. ˇSmigoc, The inverse eigenvalue problem for nonnegative matrices, Linear Algebra and its Applications 393 (2004) 365 – 374, (Special issue on Positivity in Linear Algebra). Positive polynomials on unbounded domains Juan C. Vera (joint work with Luis F. Zuluaga) Certificates of non-negativity such as Putinar’s Positivstellensatz have been used to obtain powerful numerical techniques to solve polynomial optimization (PO) problems. Putinar’s certificate uses sum-of-squares (sos) polynomials to certify the non-negativity of a given polynomial over a domain defined by polynomial inequalities. This certificate assumes the Archimedean property of the associated quadratic module, which in particular implies compactness of the domain. We present a new certificate of non-negativity for polynomials over the possibly unbounded set obtained from the intersection of a closed domain S and h−1(0) = {x ∈ Rn: h(x) = 0}, the zero set of a given polynomial h(x). It is evident that if p(x) is non-negative on the domain S, then p(x) + h(x)q(x) is non-negative on the domain S ∩ h−1(0) for any polynomial q(x). In [7] it is shown that (modulo an appropriate closure) the converse is true when the domain S is compact, thereby establishing a certificate of non-negativity for polynomials on S ∩ h−1(0) in terms of non-negative polynomials on S. We show that under suitable conditions on h(x) and S, the non-negativity of a polynomial over the set S ∩ h−1(0) can be certified in terms of the non-negative polynomials on Seven if the set S is unbounded. Moreover, a characterization of the sets S ∩ h−1(0) for which the certificate of non-negativity exists is provided in terms of an appropriate condition on S and h. Unlike previous related results in [2, 5, 6], the proposed certificate of nonnegativity is independent of the polynomial defining the objective of an associated PO problem. Instead, the certificate is written purely in terms of the set of nonnegative polynomials over a set S and the ideal generated by h(x). Also, unlike the recent related results in [4], and as a result of the use of the non-negative Copositivity and Complete Positivity3109 polynomials on a set S, the associated quadratic module and the Archimedean property are not used to characterize the cases in which the proposed certificate of non-negativity holds. The certificate of non-negativity presented here readily allows the use of copositive polynomials to certify the non-negativity of a polynomial (as opposed to the more common use of sums-of-squares polynomials to certify non-negativity). In particular it encompasses the important results of Burer [1] and Pe˜na et al., [8]. So a natural question is the role this certificate could play to generalize this type of result to other contexts. We are interested in studying the consequences of this new type of certificate. For instance, the fact that copositive polynomials can be used in the proposed certificate of non-negativity, together with Polya’s Positivstellensatz (see, e.g., [3]), means that convergent linear programming (LP) hierarchies can be constructed to approximate the solution of general PO problems. Also, the new certificate could be used to provide an interesting bridge between the results on certificates of non-negativity in algebraic geometry (such as Schm¨udgen’s and Putinar’s Positivstellensatz) and Polya’s Positivstellensatz. References |
| [153] | S. Burer, On the copositive representation of binary and continuous nonconvex quadratic programs, Mathematical Programming. 120(2) (2009), 479-495. · Zbl 1180.90234 |
| [154] | Demmel, J., Nie, J., and Powers, V. Representations of positive polynomials on non-compact semi-algebraic sets via KKT ideals, J. Pure Appl. Algebra, 209(1) (2007), 189-200. · Zbl 1106.13028 |
| [155] | Hardy, G., Littlewood, J., and P´olya, G. Inequalities. Cambridge University Press, New York, second edition (1988). · Zbl 0634.26008 |
| [156] | Jeyakumar, V., Lasserre, J.-B., and Li, G. On polynomial optimization over non-compact semi-algebraic sets, Journal of Optimization Theory and Applications,163(3) (2014), 707-718. · Zbl 1302.90208 |
| [157] | Marshall, M. Representations of non-negative polynomials, degree bounds, and applications to optimization Can. J. Math, 61(1) (2009) 205-221. · Zbl 1163.13019 |
| [158] | Nie, J., Demmel, J., and Sturmfels, B. Minimizing polynomials via sum of squares over the gradient ideal, Mathematical Programming, 106(3) (2006), 587-606. · Zbl 1134.90032 |
| [159] | Pe˜na, J., Vera, J., and Zuluaga, L. Exploiting equalities in polynomial programming, Operations Research Letters, 36 (2008), 223-228. · Zbl 1163.90755 |
| [160] | Pe˜na, J., Vera, J., and Zuluaga, L. Completely positive reformulations for polynomial optimization, Mathematical Programming, 151(2) (2015), 405-431. Mixed Integer Linear Programming Formulations of Standard Quadratic Programs E. Alper Yıldırım Standard quadratic programs have numerous applications and play an important role in copositivity detection. We consider reformulating a standard quadratic program as a mixed integer linear programming problem. We discuss the advantages and drawbacks of such a reformulation. 3110Oberwolfach Report 52/2017 1. Introduction A standard quadratic program involves minimizing a (nonconvex) quadratic form (i.e., a homogeneous quadratic function) over the unit simplex. Formally, it can be stated in the following form: (StQP) ν(Q) = min{xTQx : x ∈ ∆n}, where ∆n⊂ Rndenotes the unit simplex given by ∆n= {x ∈ Rn: eTx = 1,x ∈ Rn+}, and Q ∈ Snand Sndenotes the space of n × n real symmetric matrices, x ∈ Rn, e ∈ Rndenotes the vector of all ones, and Rn+denotes the nonnegative orthant in Rn. Standard quadratic programs have important applications in portfolio optimization, quadratic resource allocation problem, maximum (weighted) stable set problem, and copositivity detection (see, e.g., [1]). 2. Copositivity and Optimality Conditions In this talk, we focus on solving (StQP) to global optimality. For (StQP), the necessary and sufficient global optimality conditions can be stated as follows: Let x∗∈ ∆n. Then, x∗is a global optimal solution of (StQP) (i.e., ν(Q) = (x∗)TQx∗) if and only if the matrix Q − (x∗)TQx∗ eeT is copositive (see, e.g., [1]). Since checking copositivity is a co-NP-complete problem, we aim to exploit optimality conditions from a different perspective. Using the Karush-Kuhn-Tucker optimality conditions, if x ∈ ∆nis an optimal solution of (StQP), then there exist s ∈ Rnand λ ∈ R such that (1)Qx − λe − s = 0, (2)eTx =1, (3)x∈ Rn+, (4)s∈ Rn+, (5)xjsj=0,j = 1, . . . , n. By (1), (2), and (5), if x ∈ ∆nis an optimal solution of (StQP), then ν(Q) = xTQx = λ. 3. A Mixed Integer Linear Programming Reformulation We can linearize the nonconvex complementarity constraints (5) by using binary variables and big-M constraints. Therefore, (StQP) can be reformulated as the Copositivity and Complete Positivity3111 following mixed integer linear programming problem: (MILP) minλ Qx − λe − s = 0, eTx =1, xj≤ yj,j = 1, . . . , n, sj≤ Mj(1 − yj),j = 1, . . . , n, x ≥ 0, s≥ 0, yj∈ {0, 1}, j = 1, . . . , n. In this formulation, we need to specify the values of Mj, j = 1, . . . , n. By the first constraint of (MILP), we have Qx − λe − s = 0, which implies, sj= eTjQx − λ,j = 1, . . . , n, where ej∈ Rndenotes the jth unit vector, j = 1, . . . , n. Since x ∈ ∆n, we have eTjQx = xTQej≤ maxi=1,...,nQij. Therefore, any lower bound on λ (equivalently, a lower bound on ν(Q)) can be used to obtain an upper bound on sj, j = 1, . . . , n. The first simple lower bound on ν(Q) is given by (LB1) ν(Q) ≥ ℓ0(Q) :=minQij. 1≤i≤j≤n A tighter lower bound on ν(Q) can be obtained by (LB2) ν(Q) ≥ ℓcop(Q) := max{λ : Q − λeeT∈ Cn}, where Cnis the cone of matrices that can be written as the sum of a componentwise nonnegative matrix and a positive semidefinite matrix. Note that ℓ0(Q) can be computed in O(n2) time whereas the computation of ℓcop(Q) requires solving a semidefinite program. However, ℓcop(Q) can be approximated by using an accelerated proximal gradient method. Therefore, we can substitute Mj:= maxi=1,...,nQij− ℓ in the constraint sj≤ Mj(1 − yj), j = 1, . . . , n of (MILP), where ℓ ∈ {ℓ0(Q), ℓcop(Q)}. 4. Computational Experiments We compare the performances of the MILP formulations by using the two alternative lower bounds ℓ0(Q) and ℓcop(Q) in the computation of the upper bound Mj, j = 1, . . . , n. We test our formulations on the maximum stable set problem: Let G = (V, E) be a simple, undirected graph. A set S ⊆ V is a {\it stable set }if each pair of vertices in S is mutually nonadjacent. The maximum stable set problem is concerned with finding a stable set with the largest cardinality, denoted by α(G). This problem can be formulated as an instance of (StQP) as follows [2]: 1 = minxT(I + AG)x : x ∈ ∆n , α(G) where AG∈ Snis the vertex adjacency matrix of G. We generated random graphs with a specified density d ∈ (0, 1). Each instance is denoted by (n, d, s), where s is the seed of the random number generator. Our 3112Oberwolfach Report 52/2017 implementation uses the Matlab-Cplex interface (Matlab 2017b; Cplex 12.7.1). Our results are summarized in Tables 1 and 2: Table 1.n = 100; d = 0.5 ℓ0(Q)ℓcop(Q) Instanceα(G)MILP TimeMILP TimeLower BoundTotal Time (100, 0.5, 1)1045202207 (100, 0.5, 2)955188193 (100, 0.5, 3)955186191 (100, 0.5, 4)956239245 (100, 0.5, 5)965118123 (100, 0.5, 6)977106113 (100, 0.5, 7)954156160 (100, 0.5, 8)945178183 (100, 0.5, 9)964165169 (100, 0.5, 10)95599104 Average-55164169 Table 2.n = 100; d = 0.25 ℓ0(Q)ℓcop(Q) Instanceα(G)MILP TimeMILP TimeLower BoundTotal Time (100, 0.25, 1)161040426186612 (100, 0.25, 2)16572292170462 (100, 0.25, 3)17467367117484 (100, 0.25, 4)16608373191564 (100, 0.25, 5)17812595199794 (100, 0.25, 6)18175930779386 (100, 0.25, 7)17643359214573 (100, 0.25, 8)17913392210602 (100, 0.25, 9)1735430076376 (100, 0.25, 10)16225135224359 Average-739354167521 Our preliminary computational results illustrate that, on certain instances, the MILP formulation using the improved lower bound ℓcop(Q) seems to outperform that with the simple lower bound ℓ0(Q), even when we include the computation time for the improved lower bound. Therefore, the MILP formulation can be used to solve certain instances of (StQP) to global optimality. We intend to incorporate valid inequalities in the near future. References |
| [161] | I. M. Bomze, On Standard Quadratic Optimization Problems, Journal of Global Optimization 13 (1998), 369-387. · Zbl 0916.90214 |
| [162] | T. S. Motzkin and E. G. Straus, Maxima for graphs and a new proof of a Theorem of Tur´an, Canadian J. Math. 17, 533-540. Copositivity and Complete Positivity3113 CP rank of Graphs Xiao-Dong Zhang (joint work with Jiong-Sheng Li) In this talk, we introduce some properties of CP rank of complete positive graphs and prove that the set of all factorization indices of a completely positive graph has no gaps. In other words, we give an affirmative answer to a question raised by N. Kogan and A. Berman in the case of completely positive graphs. An n × n symmetric matrix A is {\it doubly non-negative, }denoted by A ∈ DNn, if it is non-negative and positive semidefinite. An n × n symmetric matrix A is {\it completely positive, }denoted by A ∈ CPn, if there exists an n × m non-negative matrix B such that A = BBT, where BTis the transpose of B. The smallest number m of columns in any such matrix B is called the factorization index of A and is denoted by CP rankA. Let G be a simple graph with vertex set V (G) = {v1, v2, . . . , vn} and edge set E(G). An n×n doubly non-negative (resp. completely positive) matrix A = (aij) is a doubly non-negative (resp. completely positive) {\it realization }of G if aij> 0 if and only if viand vjare adjacent for any 1 ≤ i 6= j ≤ n. A graph G is {\it completely positive, }or CP for short, if every doubly non-negative realization of G is completely positive. The set of all factorization indices of CP realizations of G is denoted by I(G) and the maximum number in I(G) is denoted by CP rankG. Kogan and Berman proposed the question as follows: Question 1. {\it For any graph }G, {\it if }a, b ∈ T (G){\it , does }I(G) {\it contain all integers} {\it between }a {\it and }b{\it ?} In order to study this question, we need the following notation. An n × n CP matrix A is called {\it critical }if A − εEiiis not CP for any ε > 0 and for each i = 1, . . . , n, where Eiiis the matrix of order n with (i, i) entry 1, and 0 elsewhere. Furthermore, a CP graph G is called CP1if there exists one critical CP realization A of G such that CP rankG = CP rankA. A CP graph G is called CP2if there does not exist a singular CP realization A of G such that CP rankG = CP rankA, and for any h ∈ I(G) {CP rankG}, there exists one critical CP realization A of G such that CP rankA = h. we prove the following results. Theorem 1. {\it We have:} (1) K2{\it and }K3{\it are }CP2. (2) K4{\it is }CP1. (3) {\it If }G {\it is a connected bipartite graph of order }n, {\it then} I(G) ={n − 1, n}, {\it if }G{\it is acyclic,} {|E(G)|},{\it otherwise,} {\it where }|E(G)| {\it is the number of edges of }G. {\it Furthermore, }G {\it is }CP2{\it if }G {\it is} {\it acyclic, and }G {\it is }CP1{\it if }G {\it has a cycle.} (4) {\it If }n ≥ 4{\it , then }I(Tn−2) = {n − 2, . . . , 2n − 4} {\it and }Tn−2{\it is }CP1{\it , where} {\it where }Tn−2= (V (Tn−2), E(Tn−2)) {\it is a graph of order }n {\it consisting of} n − 2 {\it triangles with a common base.} 3114Oberwolfach Report 52/2017 Theorem 2. {\it If }G {\it is a }CP {\it graph of order }n, {\it then: (1) }I(G) {\it has no gaps; (2) }G {\it is either }CP1{\it or }CP2. Alternative SDP and SOCP Approximations for Polynomial Optimization Luis F. Zuluaga (joint work with Xiaolong Kuang, Bissan Ghaddar, and Joe Naoum-Sawaya) Many real-world problems can be modeled as a polynomial optimization problem (POP); that is, an optimization problem in which both the objective and constraints are multivariate polynomials on the decision variables. Thus devising new approaches to globally solve POPs is an active area of research. In his seminal work, Lasserre [11] showed that {\it semidefinite programming }(SDP) relaxations based on {\it sum of square }(SOS) polynomials can provide global bounds for POPs. However, the SDP constraints are computationally expensive and thus even using low-orders of the hierarchy to approximate large-scale POPs becomes computationally intractable in practice. To improve the computational performance of the SDP based hierarchies to approximate the solution of POPs, prior work has focused on exploiting the problem’s sparsity [10, 9] and symmetry [3, 6], improving the relaxation by generating and adding appropriate valid inequalities [8], using bounded SOS polynomials [13] and more recently by devising more computationally efficient hierarchies such as linear programming (LP) and second-order cone programming (SOCP) hierarchies [7, 14, 1, 4, 5]. Here, we consider alternative ways to use SOCP restrictions of the SOS condition introduced by [1]. In particular, we show that SOCP hierarchies can be effectively used to strengthen hierarchies of LP relaxations for general POPs. Such hierarchies of LP relaxations have received little attention in the POP literature (a few noteworthy exceptions are [2, 12, 15, 4, 5]). However, in this paper we show that this solution approach is substantially more effective in finding solutions of certain POPs for which the more common hierarchies of SDP relaxations are known to perform poorly (see, e.g., [7]). Furthermore, when the feasible set of the POP is compact, these SOCP hierarchies converge to the POP’s optimal value. Note that for the well-known SDP based hierarchies introduced in [11], the {\it quadratic module }(QM) associated with the feasible set of the POP is required to be {\it Archimedean}, which implies the compactness of the POP’s feasible set. 1. Hierarchies In particular, we consider for the polynomial optimization problem (1)min{f(x) : gi(x) ≥ 0, i = 1, . . . , m}. In particular we consider the Lasserre hierarchy (QM-SOSr) below applied to problem (1) in which SOS polynomials are constructed to create the hierarchy. Also below, we consider the (QM-SDOSr) hierarchy proposed in [1], in which the Copositivity and Complete Positivity3115 hierarchy (QM-SDOSr) is weakened by considering SDSOS polynomials, instead of SOS polynomials. (QM-SOSr(QM-SDOSr)) maxλ λ,si(x) m X st f (x) − λ = s0(x) +si(x)gi(x), i=1 s0(x) ∈ SOS2r(SDOS2r), si(x) ∈ SOS2⌊r−deg(gi)/2⌋(SDOS2⌊r−deg(gi)/2⌋), i = 1, . . . , m, λ ∈ R. On the other hand, we consider below two hierarchies that can be derived from the non-negative coefficient polynomial hierarchies proposed for (1) in [14]. The Po-SOSrhierarchy in which the non-negative coefficient polynomials are replaced with SOS polynomials, and the Po-SDOSrin which the non-negative coefficient polynomials are replaced with SDSOS polynomials. Thus, these two hierarchies strengthen the one proposed in [14]. (Po-SOSr(Po-SDOSr)) maxλ λ,pα,β(x) nm st (1 +xi+gj(x))r(f (x) − λ) =Xpα,β(x)xαg(x)β, i=1j=1(α,β)∈Nn+m pα,β(x) ∈ SOS2(pα,β(x) ∈ SDOS2), for all (α, β) ∈ Nn+m, λ ∈ R, 2. Numerical Results We test a POPs from [8], which are highly non-convex and require a high level of Lasserre’s hierarchy to converge to their global optimum. Example 1. {\it Consider the following quadratic POP with 5 variables:} min2x1− x2+ x3− 2x4− x5 x∈R5 st (x1− 2)2− x22− (x3− 1)2− (x5− 1)2≥ 0, x1x3− x4x5+ x21≥ 1, x3− x22− x24≥ 1, x1x5− x2x3≥ 2, x1+ x2+ x3+ x4+ x5≤ 14, xi≥ 0, i = 1, . . . , 5. As shown in Table 3, the (QM-SOSr) hierarchy converges to the global optimum when ˆd = 8 with a computational time of 49.82 seconds, while the hierarchy (Po-SOSr) converges to global optimum when ˆd = 6 with only 8.21 seconds 3116Oberwolfach Report 52/2017 Figure 1.Bound and Time Comparison of Different Hierarchies for Example 1. of computational time. Hierarchy (QM-SDOSr) fails to converge to the global optimum up to ˆd = 8. However, the hierarchy (Po-SDOSr) also converges to the global optimum when ˆd = 8 with 13.28 seconds of computational time. Although the degree ˆd provides an approximate measure of the size (variables and constraints) involved in the formulations of the hierarchies’ problems, a better comparison of the hierarchies can be done by illustrating the trade-off between the solution time and the quality of the bound obtained from each hierarchy. In Figure 1, the different line plots show the bound and solution time associated with increasing orders of each of the hierarchies. Clearly, within one second, the (Po-SDOSr) hierarchy gives the best bound; within ten seconds, the (Po-SOSr) hierarchy gives the optimal value while there is still a gap between the problem’s optimal value (illustrated by the dashed horizontal line) and the bounds obtained by other hierarchies. Clearly, the hierarchies proposed have better performance over the Lasserre-type hierarchies for this problem. QM-SOSrQM-SDOSrPo-SOSrPo-SDOSr dˆBoundTBoundTBoundTBoundT 2-25.000.35-25.000.12-6.63 0.74-7.400.03 4-6.011.22-6.350.15-2.35 1.53-2.960.19 6-2.406.75-4.461.85∗-1.57 8.21-1.720.71 8∗-1.57 49.82-2.81 15.00∗-1.57 13.28 ∗: Optimal value is obtained. Table 3.Bound and Time Comparison of Different Hierarchies for Example 1. Copositivity and Complete Positivity3117 References |
| [163] | Ahmadi, A. A. and Majumdar, A. (2014). DSOS and SDSOS optimization: LP and SOCPbased alternatives to sum of squares optimization. In Information Sciences and Systems (CISS), 2014 48th Annual Conference on, pages 1-5. IEEE. |
| [164] | de Klerk, E. and Pasechnik, D. (2002). Approximation of the stability number of a graph via copositive programming. SIAM Journal on Optimimization, 12(4):875-892. · Zbl 1035.90058 |
| [165] | de Klerk, E. and Sotirov, R. (2010). Exploiting group symmetry in semidefinite programming relaxations of the quadratic assignment problem. Mathematical Programming, 122(2):225– 246. · Zbl 1184.90120 |
| [166] | Dickinson, P. J. and Povh, J. (2013). New linear and positive semidefinite programming based approximation hierarchies for polynomial optimisation. Preprint, submitted. Available at http://www.optimization-online.org/DB_HTML/2013/06/3925.html. |
| [167] | Dickinson, P. J. and Povh, J. (2015). On an extension of p´olya?s positivstellensatz. Journal of global optimization, 61(4):615-625. · Zbl 1379.11037 |
| [168] | Gatermann, K. and Parrilo, P. (2004). Symmetry groups, semidefinite programs, and sums of squares. Journal of Pure and Applied Algebra, 192(1-3):95-128. · Zbl 1108.13021 |
| [169] | Ghaddar, B., Vera, J. C., and Anjos, M. F. (2011). Second-order cone relaxations for binary quadratic polynomial programs. SIAM Journal on Optimization, 21(1):391-414. · Zbl 1242.90153 |
| [170] | Ghaddar, B., Vera, J. C., and Anjos, M. F. (2016b). A dynamic inequality generation scheme for polynomial programming. Mathematical Programming, 156(1-2):21-57. · Zbl 1342.90143 |
| [171] | Josz, C., Molzahn, D. K. (2015). Moment/sum-of-squares hierarchy for complex polynomial optimization. arXiv preprint arXiv:1508.02068. · Zbl 1395.90196 |
| [172] | Kojima, M., Kim, S., and Waki, H. (2003). Sparsity in sums of squares of polynomials. Mathematical Programming, 103(1):45-62. · Zbl 1079.90092 |
| [173] | Lasserre, J. B. (2001). Global optimization with polynomials and the problem of moments. SIAM Journal on Optimization, 11(3):796-817. · Zbl 1010.90061 |
| [174] | Lasserre, J. B. (2002). Semidefinite programming vs. LP relaxations for polynomial programming. Mathematics of Operations Research, 27(2):347-360. · Zbl 1082.90554 |
| [175] | Lasserre, J. B., Toh, K.-C., and Yang, S. (2015). A bounded degree SOS hierarchy for polynomial optimization. EURO Journal on Computational Optimization, pages 1-31. |
| [176] | Pe˜na, J., Vera, J. C., and Zuluaga, L. F. (2017). Positive polynomials on unbounded domains. arXiv preprint arXiv:1709.03435. |
| [177] | Zuluaga, L., Vera, J., and Pe˜na, J. (2006). LMI approximations for cones of positive semidefinite forms. SIAM · Zbl 1131.90040 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
