We study semidefinite programming, SDP, relaxations for Sensor Network Localization, SNL, with anchors and with noisy distance information. The main point of the paper is to view SNL as a (nearest) Euclidean Distance ...
详细信息
We study semidefinite programming, SDP, relaxations for Sensor Network Localization, SNL, with anchors and with noisy distance information. The main point of the paper is to view SNL as a (nearest) Euclidean Distance Matrix, EDM, completion problem that does not distinguish between the anchors and the sensors. We show that there are advantages for using the well studied EDM model. In fact, the set of anchors simply corresponds to a given fixed clique for the graph of the EDM problem. We next propose a method of projection when large cliques or dense subgraphs are identified. This projection reduces the size, and improves the stability, of the relaxation. In addition, by viewing the problem as an EDM completion problem, we are able to derive a new approximation scheme for the sensors from the SDP approximation. This yields, on average, better low rank approximations for the low dimensional realizations. This further emphasizes the theme that SNL is in fact just an EDM problem. We solve the SDP relaxations using a primal-dual interior/exterior-point algorithm based on the Gauss-Newton search direction. By not restricting iterations to the interior, we usually get lower rank optimal solutions and thus, better approximations for the SNL problem. We discuss the relative stability and strength of two formulations and the corresponding algorithms that are used. In particular, we show that the quadratic formulation arising from the SDP relaxation is better conditioned than the linearized form that is used in the literature.
Let C be the convex hull of points {(1 x) ((1) x)(T) [x is an element of F subset of R-n}. Representing or approximating C is a fundamental problem for global optimization algorithms based on convex relaxations of pro...
详细信息
Let C be the convex hull of points {(1 x) ((1) x)(T) [x is an element of F subset of R-n}. Representing or approximating C is a fundamental problem for global optimization algorithms based on convex relaxations of products of variables. We show that if 17 <= 4 and F is a simplex, then C has a computable representation in terms of matrices X that are doubly nonnegative (positive semidefinite and componentwise nonnegative). We also prove that if n = 2 and F is a box, then C has a representation that combines semidefiniteness with constraints on product terms obtained from the reformulation-linearization technique (RLT). The simplex result generalizes known representations for the convex hull of {(x(1), x(2), x(1)x(2)) vertical bar x is an element of F} when F subset of R-2 is a triangle, while the result for box constraints generalizes the well-known fact that in this case the RLT constraints generate the convex hull of ((x(1), x(2), x(1)x(2)) vertical bar x is an element of F}. When n = 3 and F is a box, we show that a representation for C can be obtained by utilizing the simplex result for n = 4 in conjunction with a triangulation of the 3-cube.
A linear matrix inequality (LMI) is a condition stating that a symmetric matrix whose entries are affine-linear combinations of variables is positive semidefinite. Motivated by the fact that diagonal LMIs define polyh...
详细信息
A linear matrix inequality (LMI) is a condition stating that a symmetric matrix whose entries are affine-linear combinations of variables is positive semidefinite. Motivated by the fact that diagonal LMIs define polyhedra, the solution set of an LMI is called a spectrahedron. Linear images of spectrahedra are called semidefinitely representable sets. Part of the interest in spectrahedra and semidefinitely representable sets arises from the fact that one can efficiently optimize linear functions on them by semidefinite programming, such as one can do on polyhedra by linear programming. It is known that every face of a spectrahedron is exposed. This is also true in the general context of rigidly convex sets. We study the same question for semidefinitely representable sets. Lasserre proposed a moment matrix method to construct semidefinite representations for certain sets. Our main result is that this method can work only if all faces of the considered set are exposed. This necessary condition complements sufficient conditions recently proved by Lasserre, Helton, and Nie.
In this paper we present a convex relaxation method that globally solves for the camera position and orientation given a set of image pixel measurements associated with a scene of reference points of known three-dimen...
详细信息
In this paper we present a convex relaxation method that globally solves for the camera position and orientation given a set of image pixel measurements associated with a scene of reference points of known three-dimensional positions. The approach formulates the pose optimization problem as a semidefinite positive relaxation (SDR) program. A comprehensive comparative performance analysis, carried out in the computer simulations section, demonstrates the superior performance of the relaxation method over existing approaches. The computational complexity of the method is O(n), where n is the number of reference points, and is applicable to both coplanar and non-coplanar reference point configurations. The average run-time recorded is 50 ms for an average point count of 100. Crown Copyright (C) 2010 Published by Elsevier B.V. All rights reserved.
The goal of semisupervised kernel matrix learning (SS-KML) is to learn a kernel matrix on all the given samples on which just a little supervised information, such as class label or pairwise constraint, is provided. D...
详细信息
The goal of semisupervised kernel matrix learning (SS-KML) is to learn a kernel matrix on all the given samples on which just a little supervised information, such as class label or pairwise constraint, is provided. Despite extensive research, the performance of SS-KML still leaves some space for improvement in terms of effectiveness and efficiency. For example, a recent pairwise constraints propagation (PCP) algorithm has formulated SS-KML into a semidefinite programming (SDP) problem, but its computation is very expensive, which undoubtedly restricts PCPs scalability in practice. In this paper, a novel algorithm, called kernel propagation (KP), is proposed to improve the comprehensive performance in SS-KML. The main idea of KP is first to learn a small-sized sub-kernel matrix (named seed-kernel matrix) and then propagate it into a larger-sized full-kernel matrix. Specifically, the implementation of KP consists of three stages: 1) separate the supervised sample (sub) set X-l from the full sample set X;2) learn a seed-kernel matrix on X-l through solving a small-scale SDP problem;and 3) propagate the learnt seed-kernel matrix into a full-kernel matrix on X. Furthermore, following the idea in KP, we naturally develop two conveniently realizable out-of-sample extensions for KML: one is batch-style extension, and the other is online-style extension. The experiments demonstrate that KP is encouraging in both effectiveness and efficiency compared with three state-of-the-art algorithms and its related out-of-sample extensions are promising too.
The sensor network localization (SNL) problem in embedding dimension r consists of locating the positions of wireless sensors, given only the distances between sensors that are within radio range and the positions of ...
详细信息
The sensor network localization (SNL) problem in embedding dimension r consists of locating the positions of wireless sensors, given only the distances between sensors that are within radio range and the positions of a subset of the sensors (called anchors). Current solution techniques relax this problem to a weighted, nearest, (positive) semidefinite programming (SDP) completion problem by using the linear mapping between Euclidean distance matrices (EDM) and semidefinite matrices. The resulting SDP is solved using primal-dual interior point solvers, yielding an expensive and inexact solution. This relaxation is highly degenerate in the sense that the feasible set is restricted to a low dimensional face of the SDP cone, implying that the Slater constraint qualification fails. Cliques in the graph of the SNL problem give rise to this degeneracy in the SDP relaxation. In this paper, we take advantage of the absence of the Slater constraint qualification and derive a technique for the SNL problem, with exact data, that explicitly solves the corresponding rank restricted SDP problem. No SDP solvers are used. For randomly generated instances, we are able to efficiently solve many huge instances of this NP-hard problem to high accuracy by finding a representation of the minimal face of the SDP cone that contains the SDP matrix representation of the EDM. The main work of our algorithm consists in repeatedly finding the intersection of subspaces that represent the faces of the SDP cone that correspond to cliques of the SNL problem.
Adding cuts based on copositive matrices, we propose to improve Lovasz' bound theta on the clique number and its tightening theta' introduced by McEliece, Rodemich, Rumsey, and Schrijver. Candidates for cheap ...
详细信息
Adding cuts based on copositive matrices, we propose to improve Lovasz' bound theta on the clique number and its tightening theta' introduced by McEliece, Rodemich, Rumsey, and Schrijver. Candidates for cheap and efficient copositivity cuts of this type are obtained from graphs with known clique number. The cost of previously established semidefinite programming bound hierarchies starting with theta' rapidly increases with the order (and quality requirements). By contrast, the bounds proposed here are relatively cheap in the sense that computational effort is comparable to that required for theta'.
Let P = {h(1), ... , h(s)} subset of Z[Y-1, ... , Y-k], D >= deg(h(i)) for 1 <= i <= s, sigma bounding the bit length of the coefficients of the h(i)'s, and let Phi be a quantifier-free P-formula defining...
详细信息
Let P = {h(1), ... , h(s)} subset of Z[Y-1, ... , Y-k], D >= deg(h(i)) for 1 <= i <= s, sigma bounding the bit length of the coefficients of the h(i)'s, and let Phi be a quantifier-free P-formula defining a convex semialgebraic set. We design an algorithm returning a rational point in S if and only if S boolean AND Q not equal empty set. It requires sigma(O)(1) D-O(k(3)) bit operations. If a rational point is outputted, its coordinates have bit length dominated by sigma D-O(k(3)). Using this result, we obtain a procedure for deciding whether a polynomial f is an element of Z[X-1, ... , X-n] is a sum of squares of polynomials in Q[X-1, ... , X-n]. Denote by d the degree of f, tau the maximum bit length of the coefficients in f, D = ((n+d) (n)), and k <= D(D + 1) - ((n+2d) (n)). This procedure requires tau(O)(1) D-O(k(3)) bit operations, and the coefficients of the outputted polynomials have bit length dominated by tau D-O(k(3)).
作者：
Hu, XiaolinTsinghua Univ
State Key Lab Intelligent Technol & Syst Tsinghua Natl Lab Informat Sci & Technol Dept Comp Sci & Technol Beijing 100084 Peoples R China
A novel idea is proposed for solving a system of mixed linear matrix inequalities and linear vector inequalities and equalities. First, the problem is converted into an unconstrained minimization problem with a contin...
详细信息
A novel idea is proposed for solving a system of mixed linear matrix inequalities and linear vector inequalities and equalities. First, the problem is converted into an unconstrained minimization problem with a continuously differentiable convex objective function. Then, a continuous-time dynamic system and a discrete-time dynamic system are proposed for solving it. Under some mild conditions, the proposed dynamic systems are shown to be globally convergent to a solution of the problem. The merits of the methods refer to their simple numerical implementations and capability for handling nonstrict LMIs easily. In addition, the methods are promising in neural circuits realization, and therefore have potential applications in many online control problems. Several numerical examples are presented to illustrate the performance of the methods and substantiate the theoretical results. (C) 2010 Elsevier Inc. All rights reserved.
We present a mathematical framework for the so-called multidisciplinary free material optimization (MDFMO) problems, a branch of structural optimization in which the full material tensor is considered as a design vari...
详细信息
We present a mathematical framework for the so-called multidisciplinary free material optimization (MDFMO) problems, a branch of structural optimization in which the full material tensor is considered as a design variable. We extend the original problem statement by a class of generic constraints depending either on the design or on the state variables. Among the examples are local stress or displacement constraints. We show the existence of optimal solutions for this generalized free material optimization (FMO) problem and discuss convergent approximation schemes based on the finite element method.
暂无评论