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
My talk at the Montreal CMS 2013 ( Also Tseng Lecture at the Tuesday plenary session of ISMP, Berlin 20012 ) Recent Progresses on Linear Programming and the Simplex Method. (Posted May 3, 2013.)
My talk at the Michigan Ross School A Dynamic Linear Programming Algorithm for Facilitated Charging and Discharging of Plug-In Electric Vehicles. (Posted May 3, 2013.)
The new working paper Beyond Convex Relaxation: A Polynomial–Time Non-Convex Optimization Approach to Network Localization
. (Posted November 18, 2012; to appear in INFOCOM 2013.)
The new working paper A Homogeneous Interior-Point Algorithm for Nonsymmetric Convex Conic Optimization. (Posted November 16, 2012.)
The new working paper
The simplex method is strongly polynomial for deterministic Markov decision processes. (Posted August 27, 2012; research supported by AFOSR Grant FA9550-12-1-0396; to appear in SODA 2013.)
The new working paper
Complexity Analysis of Interior Point Algorithms for Non-Lipschitz and Nonconvex Minimization. (Posted August 27, 2012; research supported by AFOSR Grant FA9550-12-1-0396.)
My tutorial at INFORMS Beijing 20012 Recent Linear Programming Developments. (Posted Julne 25, 2012.)
The new working paper
On Sensor Network Localization Using SDP Relaxation. (Posted January 8, 2012; to appear in The Fields Institute Communications Series on Discrete Geometry and Optimization 2013.)
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; to appear in IEEE Transactions on Smart Grid.)
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; revised March 29, 2012, to appear in Math Programming Computation.)
Working paper
Computational Models and Complexities of Tarski's Fixed Points is available. (Posted September 27, 2011)
Working paper
Complexity of Unconstrained L_2-L_p Minimization. (Posted May 3, 2011; research supported by NSF Grant GOALI 0800151; appeared in Math Programming Online)
The working paper:
Newsvendor Optimization with Limited Distribution Information is available. Click PDF file . (Posted November 18, 2006; research sypported by the Boeing company; to appear in Optimization Methods and Software.)
``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 AFOSR Grant FA9550-09-1-0306.)
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.)
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.)
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; updated January 20, 2013.)
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).
Working paper
On affine motions and bar frameworks in general position. (Posted September 29, 2010; research supported by NSF Grant GOALI 0800151; to appear in LAA.)
Working paper
On Doubly Positive Semidefinite Programming Relaxations is available. (Posted August 19, 2010; research supported in part
by NSF Grant GOALI 0800151 and AFOSR Grant FA9550-09-1-0306.)
My seminar talk on
A Dynamic Near-Optimal Algorithm for Online Linear Programming. (Posted May 15, 2010.)
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.)
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, appeared in Math Programming)
Also see interior-point algorithm Matlab codes
comparing $L_{1/2}$ and $L_1$ minimization models for recovering a sparse solution.
My Tutte Seminar Talk at Waterloo:
A Unified Theorem on SDP Rank Reduction and its Applications
. (Posted March 7, 2009.)
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.)
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.)
Unpublished working paper
Convex Parimutuel Formulation for Contingent Claim Markets. (Posted 2005; this work was supported by the Boeing company.)
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
K.T. Li Professor of Engineering
Department of Management Science and Engineering
School of Engineering
Stanford University
Stanford, CA 94305
email: yinyu-ye@stanford.edu