[BANANA] Special LA/Opt and OR seminar Fri Oct 30 (Henry Wolkowicz)

[Michael A. Saunders]

    SPECIAL JOINT OPTIMIZATION SEMINAR

    CME 510 Fall 2009 Linear Algebra and Optimization Seminar
    iCME, Stanford University
    http://icme.stanford.edu/seminars/seminars.php

    Operations Research @ Stanford
    http://or.stanford.edu/oras_seminars.html

    4:15pm Fri Oct 30, 2009
    Terman 453

    Prof Henry Wolkowicz
    Dept of Comb and Opt, University of Waterloo
    http://orion.math.uwaterloo.ca/~hwolkowi
    hwolkowicz at uwaterloo.ca

Explicit Sensor Network Localization using Semidefinite Programming
and Clique Reductions

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, SDPc completion 
problem, by using the linear mapping between Euclidean distance 
matrices, EDMc 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. The degeneracy in the 
SDP arises from cliques in the graph of the SNL problem. 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. We are able to efficiently solve 
this NP-HARD problem with high probability, 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.