Scientific Computing Seminar

Date:
Friday, January 14, 2005
Time:
1:00pm-2:00pm
Location:
50A-5132
Seminar Speaker:
Yinyu Ye
Department of Management Science and Engineering
Stanford University
http://www.stanford.edu/~yyye/
Title:
Theory and Computation of Semidefinite Programming for Sensor Network Localization and other Distance Geometry Problems
Abstract:
We describe a semidefinite programming (SDP) based model and method for the position estimation problem in Euclidean distance geometry such as wireless sensor network localization and molecular confirmation. The optimization problem is set up so as to minimize the error in sensor positions to fit incomplete and noisy distance measures. We develop an SDP relaxation model and use the duality theory to derive necessary and/or sufficient conditions for whether a network is "localizable" or not, when the distance measures are accurate; and present a polynomial-time algorithm to locate it if it is ``localizable.'' We also present probabilistic analyses of the SDP solution when the distance measures are noisy. In all cases, observable gauges are developed to certify the quality of the position estimation of every sensor and to detect possible erroneous sensors. Furthermore, we develop a gradient-based local search method to round and improve the SDP solution. Computational solvers will be demonstrated to show the effectiveness of the method.

Yinyu Ye is Professor of Management Science and Engineering and, by courtesy, Electrical Engineering and the Director of the MS&E Industrial Affiliates Program at Stanford's School of Engineering. He holds a Ph.D. in Engineering Economic Systems and Operations Research from Stanford University. Prior to coming to Stanford in 2002, Ye served for fourteen years in the Management Science Department of the University of Iowa as the Henry Tippie Research Professor. He has been or was on the editorial board of Management Science, Operations Research, Mathematics of Operations Research, SIAM J Optimization; and the area editor of Optimization & Engineering. He was the recipient numerous international and national awards, fellowships and research grants, a semi-plenary speaker and member of the International Advisory Committee of the International Symposium on Mathematical Programming, the Section Officer (Linear Programming) of the Institute for Operations Research and the Management Sciences, the co-organizer of the 1999 DIMACS Princeton workshop on discrete optimization, and the Distinguished Speaker in High Performance Computation for Engineered Systems of MIT. He was also selected as a highly cited mathematical researcher on http://www.ISIhighlycited.com. Ye teaches courses on Optimization, Network and Integer Programming, Semidefinite Programming, etc. He has written extensively on Interior-Point Methods, Approximation Algorithms, Conic Optimization, and their applications. Ye is currently working on Markov Decision Algorithm, Computational Game Theory and Graph Localization. He has served as a consultant to a variety of industries.

Sponsor of Seminar:
Chris Ding
Scientific Computing

Contact Esmond G. Ng EGNg@lbl.gov