Yinyu Ye
Professor of Management Science and Engineering
and, by courtesy, Electrical Engineering
Department of Management Science and Engineering
Huang Engineering Center 308
475 Via Ortega
School of Engineering
Stanford University, CA 94305-4121
Phone: 650 723-7262
Fax: 650 723-1614
The new working paper
On Sensor Network Localization Using SDP Relaxation. (Posted January 8, 2012.)
Also see Matlab codes to (approximately) test if a framework can be uniquely realized by adding an SDP objective function:
TriangulationGsedumi.m and
TriangulationGdsdp.m (You need SDP solver Sedumi 1.1 or DSDP 5.8 to run it).
The new working paper
A Dynamic Algorithm for Facilitated Charging of Plug-In Electric Vehicles. (Posted December 24, 2011; research supported by EPRI and AFOSR Grant FA9550-09-1-0306.)
The new working paper
Warmstarting the Homogeneous and Self-Dual Interior Point Method for Linear and Conic Quadratic Problems is available. (Posted November 19, 2011)
The new working paper
Computational Models and Complexities of Tarski's Fixed Points is available. (Posted September 27, 2011)
The new working paper
``The Simplex and Policy-Iteration Methods are Strongly Polynomial for the Markov Decision Problem with a Fixed Discount Rate'' appeared in Math of OR (Posted April 22, 2010; last revised August 15, 2011; research supported in part by NSF Grant GOALI 0800151, DOE Grant DE-SC0002009, and AFOSR Grant FA9550-09-1-0306.)
A new working paper
Hidden-City Ticketing: the Cause and Impact.
(Posted May 18, 2011; research supported by AFOSR Grant FA9550-09-1-0306 and NSF Grant GOALI 0800151.)
The new working paper
Existence of Positive Steady States for Mass Conserving and Mass-Action Chemical Reaction Networks with a Single Terminal-Linkage Class. (Posted May 12, 2011; research supported by DOE Grant DE-SC0002009 and NSF Grant GOALI 0800151.)
The new working paper
Complexity of Unconstrained L_2-L_p Minimization. (Posted May 3, 2011;
research supported by NSF Grant GOALI 0800151 and DOE Grant DE-SC0002009.)
The new working paper
Close the Gaps: A Learning-while-Doing Algorithm for a Class of Single-Product Revenue Management Problems. (Posted February 15, 2011;
research supported by NSF Grant GOALI 0800151 and AFOSR Grant FA9550-09-1-0306.)
My talk on
Semidefinite Programming and Universal Rigidity.
(Posted February 5, 2011.) Also see a Matlab code to (approximately) test if a bar-framework is universal rigit or not:
URFrameworkTest.m (You need SDP solver Sedumi to run it).
My seminar talk on
The Simplex and Policy Iteration Methods are Strongly Polynomial for the Markov Decision
Problem with Fixed Discount. (Posted October 11, 2010.)
The new working paper
On affine motions and bar frameworks in general position. (Posted September 29, 2010; research supported by NSF Grant GOALI 0800151 and DOE Grant DE-SC0002009.)
The new working paper
Toward the Universal Rigidity of General Frameworks. (Posted September 15, 2010;
research supported by NSF Grant GOALI 0800151 and DOE Grant DE-SC0002009.)
The new working paper
On Doubly Positive Semidefinite Programming Relaxations is available. (Posted August 19, 2010; research supported in part
by NSF Grant GOALI 0800151, DOE Grant DE-SC0002009, and AFOSR Grant FA9550-09-1-0306.)
My seminar talk on
A Dynamic Near-Optimal Algorithm for Online Linear Programming. (Posted May 15, 2010.)
The new working paper
Statistical ranking and combinatorial
Hodge theory is available. (Posted May 13, 2010; to appear in Math Programming B; research supported in part
by AFOSR Grant FA9550-09-1-0306 and DOE Grant DE-SC0002009.)
The new working paper
Price of Correlations in Stochastic Optimization is available. (Posted Feb 26, 2010; to appear in Operations Research; research supported in part by Boeing.)
The new working paper
Competitive Communication Spectrum Economy and Equilibrium is available. (Posted October 22, 2007, Revised March 17, 2010;
research supported by NSF DMS-0604513, NSF GOALI 0800151, and AFOSR Grant FA9550-09-1-0306.)
The new working paper
NP-Hardness Results Related to PPAD is available.
(Posted January 14, 2010, research supported in part by NSF GOALI 0800151.)
The new working paper
A Dynamic Near-Optimal Algorithm for Online Linear Programming is available. (Posted Nov 16, updated Nov 20, 2009; research supported in part by the Boeing Company, NSF DMS-0604513,
NSF GOALI 0800151, and AFOSR Grant FA9550-09-1-0306.)
A new research note A Note on the Complexity of $L_p$ Minimization. (Posted September 3, 2009, revised October 22, 2010; research supported in part by NSF GOALI 0800151, to appear in Math Programming)
Also see interior-point algorithm Matlab codes
comparing $L_{1/2}$ and $L_1$ minimization models for recovering a sparse solution.
The paper Universal Rigidity: Towards Accurate and Efficient
Localization of Wireless Networks is posted July 29, 2009, updated Dec 1, 2009;
extended abstract appeared in INFOCOM 2010; journal version to appear in SIAM J. Optimization; research supported in part by NSF GOALI 0800151.)
My seminar talk on
A Unified Framework for Dynamic Pari-mutuel Information Market. (Posted May 14, 2009.)
The working paper Fast and Near--Optimal Matrix Completion via Randomized Basis Pursuit . (Posted May 10, updated June 4, 2009.)
My Tutte Seminar Talk at Waterloo:
A Unified Theorem on SDP Rank Reduction and its Applications
. (Posted March 7, 2009.)
The paper "Lower Bound Theory of Nonzero Entries in Solutions of L2-Lp Minimization" appeared in SIAM J. Scientific Computing.
The paper Unified Framework for Dynamic Prediction Market Design . (Posted February 9, 2009, revised July 6, 2010, journal version to
appear in Operations Research, extended abstract appeared in EC2009; research supported by NSF DMS-0604513 and AFOSR Grant FA9550-09-1-0306.)
The paper:
A FPTAS for Computing a Symmetric Leontief Competitive Economy Equilibrium is available.
Click
PDF file . (Posted February 18, 2008; Updated March 2, 2010; research supported in part by NSF DMS-0604513;
extended abstract appeared in WINE2008 and journal version to appear in Math Programming)
The paper: Optimality principles in nonequilibrium biochemical networks is available.
Click PDF file . (Posted February 9, revised August 12, 2009; research supported by NSF DMS-0604513.)
The paper: Dynamic Spectrum Management with the Competitive Market Model is available.
Click
PDF file . (Posted February 2, Updated August 22, 2009; research supported by NSF DMS-0604513, AFOSR Grant FA9550-09-1-0306, and Boeing; to appear in
IEEE Transactions on Signal Processing.)
My two talks at WINE2008:
Computational Economy Equilibrium and its Application: Progresses on
computing Arrow-Debreu-Leontief Competitive Equilibria
and
Dynamic Spectrum Management: Optimization, game and equilibrium
. (Posted December 20, 2008.)
The paper:
Distributionally Robust Optimization under Moment Uncertainty with Application to Data-Driven Problems is appeared in
OR.
(Posted February 20, 2008; Revised September 17, 2008; research supported by NSF GOALI 0800151 and Boeing.)
The paper: Bi-Quadratic Optimization over Unit Spheres
and Semidefinite Programming Relaxations is available.
Click
PDF file . (Posted July 15, 2008; to appear in Math Programming.)
The working paper: Geometric Rounding: A Dependent Rounding Scheme for Allocation Problems is available.
Click for a on-line copy.
(Posted April 18, 2008; to appear in in Journal of Combinatorial Optimization; research supported by Boeing and NSF GOALI 0800151.)
The working paper:
Parimutuel Betting on Permutations is available.
Click for a on-line copy. (Posted April 15, 2008; research supported by NSF DMS-0604513;
extended abstract appeared in WINE2008.)
The paper:
An interior-point path-following algorithm for computing a Leontief
economy equilibrium is available.
Click
PDF file . (Posted March 11, 2008; research supported by NSF DMS-0604513; to appear in Computational Optimization and Applications)
The paper:
A Note on Equilibrium Pricing as Convex Optimization is available.
Click a
journal version . (Appeared in WINE'07; research supported by NSF DMS-0604513; to appear in Journal of Computational Mathematics.)
The working paper:
The Fixed-Hub Single Allocation Problem: A Geometric Rounding Approach is available.
Click
PDF file . (Posted October 22, 2007; research supported by Boeing and NSF GOALI 0800151.)
The working paper:
Newsvendor Optimization with Limited Distribution Information is available.
Click
PDF file . (Posted November 18, 2006; research sypported by the Boeing company.)
My talk at the Plenary Memorial Session of George Dantzig of ISMP 2006, Rio de Janeiro:
Recent Applications of Linear Programming--in Memory of George Dantzig
. (Posted August 7, 2006.)
My talk at the HPOPT 2006, Delft and MOPTA 2006, Waterloo:
A Semidefinite Programming Approach to Tensegrity Theory and Graph Realization
. (Posted August 11, 2006.)
Unpublished working paper
Solving Sparse Semidefinite Programs Using the Dual Scaling
Algorithm with an Iterative Solver
. (Posted 2000; this work was supported by NSF grants DMI-9908077 and DMS-9703490.)
Unpublished working note
Convergence behavior of the central path for homogeneous and
self-dual cones . (Department of Management Sciences, The University of
Iowa, December 1995.)
Unpublished working paper
Further development of the interior algorithm for convex
quadratic programming. (Stanford University and Integrated Systems Inc., Stanford, CA 1987.)
The third Edition of BOOK Linear and Nonlinear Programming by David G. Luenberger and Yinyu Ye has been published.
Click here for information .
The BOOK Interior-Point Algorithms: Theory and Analysis has been published.
Click here for information and related software .
Education
Ph.D. Engineering Economic Systems and Operations Research , Stanford University
, 1988.
M.S. Engineering Economic Systems , Stanford University
, 1983.
B.S. Systems and Control,
Huazhong University of Science and Technology , Wuhan, China, 1982.
Research Interest
Mathematical Programming
Optimization Algorithm Design and Analysis
Computational Complexity
Operations Research and Its Applications
Click here for my NSF Reports
Here are Courses I am teaching
Photo collection of my Family
Yinyu Ye
Department of Management Science and Engineering
School of Engineering
Stanford University
Stanford, CA 94305
email: yinyu-ye@stanford.edu