-
作者：Laurent, Monique
摘要：We give a hierarchy of semidefinite upper bounds for the maximum size A(n,d) of a binary code of word length n and minimum distance at least d. At any fixed stage in the hierarchy, the bound can be computed (to an arbitrary precision) in time polynomial in n; this is based on a result of de Klerk et al. (Math Program, 2006) about the regular *-representation for matrix *-algebras. The Delsarte bound for A(n,d) is the first bound in the hierarchy, and the new bound of Schrijver (IEEE Trans. Inf...
-
作者：Freund, Robert M.; Ordonez, Fernando; Toh, Kim-Chuan
作者单位：University of Southern California; Massachusetts Institute of Technology (MIT); National University of Singapore; Singapore-MIT Alliance for Research & Technology Centre (SMART); Massachusetts Institute of Technology (MIT); Nanyang Technological University
摘要：We study four measures of problem instance behavior that might account for the observed differences in interior-point method (IPM) iterations when these methods are used to solve semidefinite programming (SDP) problem instances: (i) an aggregate geometry measure related to the primal and dual feasible regions (aspect ratios) and norms of the optimal solutions, (ii) the (Renegar-) condition measure C(d) of the data instance, (iii) a measure of the near-absence of strict complementarity of the o...
-
作者：So, Anthony Man-Cho; Ye, Yinyu
作者单位：Stanford University; Stanford University
摘要：We analyze the semidefinite programming (SDP) based model and method for the position estimation problem in sensor network localization and other Euclidean distance geometry applications. We use SDP duality and interior-point algorithm theories to prove that the SDP localizes any network or graph that has unique sensor positions to fit given distance measures. Therefore, we show, for the first time, that these networks can be localized in polynomial time. We also give a simple and efficient cr...
-
作者：Krokhmal, Pavlo A.; Grundel, Don A.; Pardalos, Panos M.
作者单位：University of Iowa; United States Department of Defense; United States Air Force; State University System of Florida; University of Florida
摘要：The Multidimensional Assignment Problem (MAP) is a higher-dimensional version of the Linear Assignment Problem that arises in the areas of data association, target tracking, resource allocation, etc. This paper elucidates the question of asymptotical behavior of the expected optimal value of the large-scale MAP whose assignment costs are independent identically distributed random variables with a prescribed probability distribution. We demonstrate that for a broad class of continuous distribut...
-
作者：Kocvara, Michal; Stingl, Michael
作者单位：Czech Academy of Sciences; Institute of Information Theory & Automation of the Czech Academy of Sciences; Czech Technical University Prague; University of Erlangen Nuremberg
摘要：The limiting factors of second-order methods for large-scale semidefinite optimization are the storage and factorization of the Newton matrix. For a particular algorithm based on the modified barrier method, we propose to use iterative solvers instead of the routinely used direct factorization techniques. The preconditioned conjugate gradient method proves to be a viable alternative for problems with a large number of variables and modest size of the constrained matrix. We further propose to a...
-
作者：Dukanovic, Igor; Rendl, Franz
作者单位：University of Klagenfurt; University of Maribor
摘要：The semidefinite programming formulation of the Lovasz theta number does not only give one of the best polynomial simultaneous bounds on the chromatic number chi(G) or the clique number omega(G) of a graph, but also leads to heuristics for graph coloring and extracting large cliques. This semidefinite programming formulation can be tightened toward either chi(G) or omega(G) by adding several types of cutting planes. We explore several such strengthenings, and show that some of them can be comp...
-
作者：Lu, Zhaosong; Nemirovski, Arkadi; Monteiro, Renato D. C.
作者单位：Simon Fraser University; University System of Georgia; Georgia Institute of Technology
摘要：In this paper, we first demonstrate that positive semidefiniteness of a large well-structured sparse symmetric matrix can be represented via positive semidefiniteness of a bunch of smaller matrices linked, in a linear fashion, to the matrix. We derive also the dual counterpart of the outlined representation, which expresses the possibility of positive semidefinite completion of a well-structured partially defined symmetric matrix in terms of positive semidefiniteness of a specific bunch of ful...
-
作者：Nemirovski, Arkadi
作者单位：University System of Georgia; Georgia Institute of Technology
摘要：Let B-i be deterministic real symmetric m x m matrices, and xi (i) be independent random scalars with zero mean and of order of one (e.g., xi(i) similar to N(o,1)). We are interested to know under what conditions typical norm of the random matrix S-N = Sigma(N)(i=1) xi B-i(i) is of order of 1. An evident necessary condition is E{S-N(2)} less than or similar to O(1)I, which, essentially, translates to Sigma(N)(i=1) B-i(2) less than or similar to I; a natural conjecture is that the latter condit...
-
作者：Rendl, Franz; Sotirov, Renata
作者单位：University of Klagenfurt; University of Melbourne
摘要：Semidefinite programming (SDP) has recently turned out to be a very powerful tool for approximating some NP-hard problems. The nature of the quadratic assignment problem (QAP) suggests SDP as a way to derive tractable relaxations. We recall some SDP relaxations of QAP and solve them approximately using a dynamic version of the bundle method. The computational results demonstrate the efficiency of the approach. Our bounds are currently among the strongest ones available for QAP. We investigate ...
-
作者：de Klerk, Etienne; Pasechnik, Dmitrii V.; Schrijver, Alexander
作者单位：Centrum Wiskunde & Informatica (CWI); University of Amsterdam; Tilburg University
摘要：We consider semidefinite programming problems on which a permutation group is acting. We describe a general technique to reduce the size of such problems, exploiting the symmetry. The technique is based on a low-order matrix *-representation of the commutant (centralizer ring) of the matrix algebra generated by the permutation matrices. We apply it to extending a method of de Klerk et al. that gives a semidefinite programming lower bound to the crossing number of complete bipartite graphs. It ...
