Management Science & Engineering and, by courtesy, Electrical Engineering

Huang Engineering Center 308

475 Via Ortega

School of Engineering

Stanford University, CA 94305-4121

Fax: 650 723-1614

Computational Optimization Laboratory

Technical paper Near-Optimal Time and Sample Complexities for for Solving Discounted Markov Decision Process with a Generative Model. (Posted June, 2018.)

Technical paper Exact Semidefinite Formulations for a Class of (Random and Non-Random) Nonconvex Quadratic Programs. (Posted Janurary 7, 2018.)

My talk at "Optimization, Statistics and Uncertainty" of Berkeley Distributionally Robust Stochastic and Online Optimization -- Models/Algorithms for Data-Driven Optimization. (November 29, 2017.)

Working paper Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processes. (Posted October 30, 2017.)

Working paper Extended ADMM and BCD for nonseparable convex minimization models with quadratic coupling terms: convergence analysis and insights. (Posted October 30, 2017.)

Teaching Note Second-Order Optimization Algorithm: Trust-Region $\epsilon^{-1.5}$ method for general nonlinear optimization (slides 13-16) and linearly convergent path-following method for unconstrained convex optimization (slides 18-21) (Originally Posted as 2016-2017 Teaching Mote), and a supplement note. (Posted May 2017.)

Working paper Sample Average Approximation with Sparsity- Inducing Penalty for High-Dimensional Stochastic Programming. (Posted February 5, 2017.)

Working paper Assessing the System Value of Optimal Load Shifting. (Posted September 14, 2016; to appear in IEEE Transactions on Smart Grid; Supported by the Chinese Electrical Power Research Institute and the Stanford Precourt Energy Efficiency Center)

Working paper A Mathematical Formulation for Optimal Load Shifting of Electricity Demand. (to appear in IEEE Transactions on Big Data; Posted 12/10, 2015, updated 11/9, 2016; research supported in part by Chinese EPRI and Precourt Energy Efficiency Center of Stanford.)

Teaching note On First-Order Potential Reduction Algorithms for Linear Programming. (Posted May 20, 2016; research supported in part by Chinese EPRI and by AFOSR Grant FA9550-12-1-0396.) And its early version On a First-Order Potential Reduction Algorithm for Linear Programming. (Posted July 30, 2015; research supported in part by Chinese EPRI and by AFOSR Grant FA9550-12-1-0396.)

Also see two Matlab codes for solving: LP Dual Feasibility (given A and c) and LP Primal Feasibility (given A and b) in standard forms, respectively. (Posted May 31, 2016.)

Working paper Worst-case Complexity of Cyclic Coordinate Descent: O(n^2) Gap with Randomized Version. (Posted April 27, 2016; research supported in part by Chinese EPRI and by AFOSR Grant FA9550-12-1-0396.)

Working paper Folded Concave Penalized Sparse Linear Regression: Sparsity, Statistical Performance, and Algorithmic Theory for Local Solutions. (Posted March 11, 2016; research supported in part by AFOSR Grant FA9550-12-1-0396; appeared online in Math Programming.)

My talk at ICIAM2015 and MIT 2015 Convergence of the Multi-Block ADMM: are there alternative algorithms for linear programming?. (Posted September 18.)

The Fourth Edition of BOOK

Working paper On the Expected Convergence of Randomly Permuted ADMM. (Posted March 23, 2015; research supported in part by Chinese EPRI and by AFOSR Grant FA9550-12-1-0396.)

Working paper The Direct Extension of ADMM for Multi-block Convex Minimization Problems is Not Necessarily Convergent. (Posted October 30, 2013, appeared in Math Programming; research supported by AFOSR Grant FA9550-12-1-0396.)

Working paper Online Allocation Rules in Display Advertising is available. (Posted July 24, research supported by AFOSR Grant FA9550-12-1-0396.)

My talk on Data-Driven Optimization. (Posted May 28, 2014; removed "pause option" June 14.)

Working paper Sparse Portfolio Selection via Quasi-Norm Regularization. (Posted December 24, 2013, Revised October 2014, research supported by AFOSR Grant FA9550-12-1-0396.)

My talk at the ICCOPT 2013, Lisbon Complexity Analysis beyond Convex Optimization. (Posted August 2, 2013.)

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.)

Working paper On Sensor Network Localization Using SDP Relaxation. (Posted January 8, 2012; appeared 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).

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 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, appeared in JCM 2018)

My Tutte Seminar Talk at Waterloo: A Unified Theorem on SDP Rank Reduction and its Applications . (Posted March 7, 2009.)

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 BOOK

M.S. Engineering Economic Systems , Stanford University , 1983.

B.S. Systems and Control, Huazhong University of Science and Technology , Wuhan, China, 1982.

Optimization Algorithm Design and Analysis

Computational Complexity

Operations Research and Its Applications

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