 |
|
sponsored by
Title : Semidefinite Programming Relaxation Model for Graph Realization and Sensor Network Localization
Date : Nov 12, 2007
Speaker : Yinyu Ye, Professor
Affiliation : Department of Management Science and Engineering and Institute for Computational and Mathematical Engineering, Stanford University
Abstract
We present semidefinite programming (SDP) based approaches for the position estimation problem in Euclidean distance geometry such as graph realization and sensor network localization. We develop an SDP relaxation model and use the duality theory to derive necessary and/or sufficient conditions for whether a network is "realizable or localizable" or not, when the distance measures are accurate. We also present error analyses of the SDP solution when the distance measures are noisy. Furthermore, we develop a further relaxation such that large-scale problems can be solved efficiently, and demonstrate computational effectiveness of the SDP relaxation model.
Biosketch
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 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 Decisions, Computational Game Theory and Graph Localization. He has served as a consultant to a variety of industries
