-
作者：van Dam, Edwin R.; Sotirov, Renata
作者单位：Tilburg University
摘要：The graph partition problem is the problem of partitioning the vertex set of a graph into a fixed number of sets of given sizes such that the sum of weights of edges joining different sets is optimized. In this paper we simplify a known matrix-lifting semidefinite programming relaxation of the graph partition problem for several classes of graphs and also show how to aggregate additional triangle and independent set constraints for graphs with symmetry. We present an eigenvalue bound for the g...
-
作者：Jiang, Bo; Ma, Shiqian; Zhang, Shuzhong
作者单位：Shanghai University of Finance & Economics; Chinese University of Hong Kong; University of Minnesota System; University of Minnesota Twin Cities
摘要：This paper is concerned with the computation of the principal components for a general tensor, known as the tensor principal component analysis (PCA) problem. We show that the general tensor PCA problem is reducible to its special case where the tensor in question is super-symmetric with an even degree. In that case, the tensor can be embedded into a symmetric matrix. We prove that if the tensor is rank-one, then the embedded matrix must be rank-one too, and vice versa. The tensor PCA problem ...
-
作者：Jiang, Bo; Dai, Yu-Hong
作者单位：Chinese Academy of Sciences; Academy of Mathematics & System Sciences, CAS
摘要：This paper considers optimization problems on the Stiefel manifold (XX)-X-T = I-p, where X is an element of R-nxp is the variable and I-p is the p-by-p identity matrix. A framework of constraint preserving update schemes is proposed by decomposing each feasible point into the range space of X and the null space of X-T. While this general framework can unify many existing schemes, a new update scheme with low complexity cost is also discovered. Then we study a feasible Barzilai-Borwein-like met...
-
作者：Nie, Jiawang
作者单位：University of California System; University of California San Diego
摘要：This paper studies the hierarchy of local minimums of a polynomial in the vector space . For this purpose, we first compute -minimums, for which the first and second order necessary optimality conditions are satisfied. To compute each -minimum, we construct a sequence of semidefinite relaxations, based on optimality conditions. We prove that each constructed sequence has finite convergence, under some generic conditions. A procedure for computing all local minimums is given. When there are equ...
-
作者：Pena, Javier; Vera, Juan C.; Zuluaga, Luis F.
作者单位：Carnegie Mellon University; Tilburg University; Lehigh University
摘要：Polynomial optimization encompasses a very rich class of problems in which both the objective and constraints can be written in terms of polynomials on the decision variables. There is a well established body of research on quadratic polynomial optimization problems based on reformulations of the original problem as a conic program over the cone of completely positive matrices, or its conic dual, the cone of copositive matrices. As a result of this reformulation approach, novel solution scheme...
-
作者：Letchford, Adam N.; Lasserre, Jean B.; Parrilo, Pablo A.; Steurer, David
作者单位：Lancaster University; Centre National de la Recherche Scientifique (CNRS); Massachusetts Institute of Technology (MIT); Cornell University
-
作者：Drusvyatskiy, D.; Ioffe, A. D.
作者单位：University of Washington; University of Washington Seattle; Technion Israel Institute of Technology
摘要：We show that quadratic growth of a semi-algebraic function is equivalent to strong metric subregularity of the subdifferential-a kind of stability of generalized critical points. In contrast, this equivalence can easily fail outside of the semi-algebraic setting. As a consequence, we derive necessary conditions and sufficient conditions for optimality in subdifferential terms.
-
作者：Dyer, Martin; Stougie, Leen
作者单位：University of Leeds; Eindhoven University of Technology; Centrum Wiskunde & Informatica (CWI)
-
作者：Morris, Walter D., Jr.
作者单位：George Mason University
摘要：We use recent results on algorithms for Markov decision problems to show that a canonical form for a matrix with the generalized P-property can be computed, in some important cases, by a strongly polynomial algorithm.
-
作者：Gouveia, Joo; Parrilo, Pablo A.; Thomas, Rekha R.
作者单位：Universidade de Coimbra; Massachusetts Institute of Technology (MIT); University of Washington; University of Washington Seattle
摘要：In this paper we show how to construct inner and outer convex approximations of a polytope from an approximate cone factorization of its slack matrix. This provides a robust generalization of the famous result of Yannakakis that polyhedral lifts of a polytope are controlled by (exact) nonnegative factorizations of its slack matrix. Our approximations behave well under polarity and have efficient representations using second order cones. We establish a direct relationship between the quality of...
