The matching problem between two adjacency matrices can be formulated as the NP-hard quadratic assignment problem (QAP). Previous work on semidefinite programming (SDP) relaxations to the QAP have produced solutions t...
详细信息
The matching problem between two adjacency matrices can be formulated as the NP-hard quadratic assignment problem (QAP). Previous work on semidefinite programming (SDP) relaxations to the QAP have produced solutions that are often tight in practice, but such SDPs typically scale badly, involving matrix variables of dimension where n is the number of nodes. To achieve a speed up, we propose a further relaxation of the SDP involving a number of positive semidefinite matrices of dimension no greater than the number of edges in one of the graphs. The relaxation can be further strengthened by considering cliques in the graph, instead of edges. The dual problem of this novel relaxation has a natural three-block structure that can be solved via a convergent Alternating Direction Method of Multipliers in a distributed manner, where the most expensive step per iteration is computing the eigendecomposition of matrices of dimension . The new SDP relaxation produces strong bounds on quadratic assignment problems where one of the graphs is sparse with reduced computational complexity and running times, and can be used in the context of nuclear magnetic resonance spectroscopy to tackle the assignment problem.
We consider relaxations for nonconvex quadratically constrained quadratic programming (QCQP) based on semidefinite programming (SDP) and the reformulation-linearization technique (RLT). From a theoretical standpoint w...
详细信息
We consider relaxations for nonconvex quadratically constrained quadratic programming (QCQP) based on semidefinite programming (SDP) and the reformulation-linearization technique (RLT). From a theoretical standpoint we show that the addition of a semidefiniteness condition removes a substantial portion of the feasible region corresponding to product terms in the RLT relaxation. On test problems we show that the use of SDP and RLT constraints together can produce bounds that are substantially better than either technique used alone. For highly symmetric problems we also consider the effect of symmetry-breaking based on tightened bounds on variables and/or order constraints.
This paper considers the break minimization problem in sports timetabling. The problem is to find, under a given timetable of a round-robin tournament, a home-away assignment that minimizes the number of breaks, i.e.,...
详细信息
This paper considers the break minimization problem in sports timetabling. The problem is to find, under a given timetable of a round-robin tournament, a home-away assignment that minimizes the number of breaks, i.e., the number of occurrences of consecutive matches held either both at away or both at home for a team. We formulate the break minimization problem as MAX RES CUT and MAX 2SAT, and apply Goemans and Williamson's approximation algorithm using semidefinite programming. Computational experiments show that our approach quickly generates solutions of good approximation ratios. (c) 2004 Elsevier Ltd. All rights reserved.
We explore the power of semidefinite programming (SDP) for finding additive epsilon-approximate Nash equilibria in bimatrix games. We introduce an SDP relaxation for a quadratic programming formulation of the Nash equ...
详细信息
We explore the power of semidefinite programming (SDP) for finding additive epsilon-approximate Nash equilibria in bimatrix games. We introduce an SDP relaxation for a quadratic programming formulation of the Nash equilibrium problem and provide a number of valid inequalities to improve the quality of the relaxation. If a rank-1 solution to this SDP is found, then an exact Nash equilibrium can be recovered. We show that, for a strictly competitive game, our SDP is guaranteed to return a rank-1 solution. We propose two algorithms based on the iterative linearization of smooth nonconvex objective functions whose global minima by design coincide with rank-1 solutions. Empirically, we demonstrate that these algorithms often recover solutions of rank at most 2 and epsilon close to zero. Furthermore, we prove that if a rank-2 solution to our SDP is found, then a 5/11-Nash equilibrium can be recovered for any game, or a 1/3-Nash equilibrium for a symmetric game. We then show how our SDP approach can address two (NP-hard) problems of economic interest: finding the maximum welfare achievable under any Nash equilibrium, and testing whether there exists a Nash equilibrium where a particular set of strategies is not played. Finally, we show the connection between our SDP and the first level of the Lasserre/sum of squares hierarchy.
A sensor network localization problem is to determine the positions of the sensor nodes in a network given incomplete and inaccurate pairwise distance measurements. Such distance data may be acquired by a sensor node ...
详细信息
A sensor network localization problem is to determine the positions of the sensor nodes in a network given incomplete and inaccurate pairwise distance measurements. Such distance data may be acquired by a sensor node by communicating with its neighbors. We describe a general semidefinite programming (SDP)-based approach for solving the graph realization problem, of which the sensor network localization problems is a special case. We investigate the performance of this method on problems with noisy distance data. Error bounds are derived from the SDP formulation. The sources of estimation error in the SDP formulation are identified. The SDP solution usually has a rank higher than the underlying physical space which, when projected onto the lower dimensional space, generally results in high estimation error. We describe two improvements to ameliorate such a difficulty. First, we propose a regularization term in the objective function that can help to reduce the rank of the SDP solution. Second, we use the points estimated from the SDP solution as, the initial iterate for a gradient-descent method to further refine the estimated points. A lower bound obtained from the optimal SDP objective value can be used to check the solution quality. Experimental results are presented to, validate our methods and show that they outperform existing SDP methods.
Non-orthogonal time-frequency division multiplexing （NTFDM） transmission scheme has been proposed to further improve the bandwidth efficiency and overcome the drawbacks of the conventional orthogonal frequency divis...
详细信息
Non-orthogonal time-frequency division multiplexing （NTFDM） transmission scheme has been proposed to further improve the bandwidth efficiency and overcome the drawbacks of the conventional orthogonal frequency division multiplexing （OFDM） method. Based on such approach, the fast signal detection algorithm, semidefinite programming （SDP） detection, has been studied. As the coefficient matrix tends to be ill conditioned, the modified SDP algorithm combined with successive interference cancellation （SIC） has been developed. The improved algorithm is a good tradeoff between performance and detection complexity. Simulation results show that the proposed algorithm can achieve better performance than cutting plane aided SDP method.
Community detection is an effective exploration technique for analyzing networks. Most of the network data not only describes the connections of network nodes but also describes the properties of the nodes. In this pa...
详细信息
Community detection is an effective exploration technique for analyzing networks. Most of the network data not only describes the connections of network nodes but also describes the properties of the nodes. In this paper, we propose a community detection method collects relevant evidences from the information of node attributes and the information of network structure to assist the community detection task on node-attributed networks. We find communities in the framework of the semidefinite programming (SDP) method. In practical applications, the distribution of some node attributes may be uncorrelated with the network structure or the network itself may contain no communities as in a random graph. A sparse attribute self-adjustment mechanism is introduced to determine the relative importance of each source of information. As a by product, our method is also effective for community detection of multilayer networks that allow for multiple kinds of relations over the same set of nodes. Experimental results demonstrate the effectiveness of the proposed method.
We construct a class of path-following algorithms for solving semidefinite problems with linear-quadratic functionals. Complexity estimates similar to the best known for the case of the standard convex quadratic progr...
详细信息
We construct a class of path-following algorithms for solving semidefinite problems with linear-quadratic functionals. Complexity estimates similar to the best known for the case of the standard convex quadratic programming problem are obtained. Complete proofs of all results are included.
By assuming signal propagation speed to be unknown, a convex rank unconstrained semidefinite programming (RUSDP) algorithm is designed to obtain the unified solution for near-field and far-field TDOA-based localizatio...
详细信息
By assuming signal propagation speed to be unknown, a convex rank unconstrained semidefinite programming (RUSDP) algorithm is designed to obtain the unified solution for near-field and far-field TDOA-based localization. Then the rank constrained semidefinite programming (RCSDP) is further proposed by availing of the rank constraint. The simulations show the validity of the RUSDP and RCSDP algorithms whether the source is in the near-field or in the far-field. The RCSDP performs significantly better than the RUSDP due to the tighter relaxation.
We consider the problem of evaluating the probability of error of binary communication systems in the presence of additive noise and intersymbol interferences whose statistics are inexactly known due to the estimation...
详细信息
We consider the problem of evaluating the probability of error of binary communication systems in the presence of additive noise and intersymbol interferences whose statistics are inexactly known due to the estimation errors of the channel coefficients. We present a new method using semidefinite programming to evaluate tight bounds on the error probability based on the upper and lower bounds on the moments of those interferences. Numerical results are provided and compared with a previously published technique.
暂无评论