# Yinyu Ye

### Operations Research @ StanfordComputational Optimization Laboratory

Technical paper Online Linear Programming: Dual Convergence, New Algorithms, and Regret Bounds. (Posted Sept. 17, 2019.)

Technical paper Solving Discounted Stochastic Two-Player Games with Near-Optimal Time and Sample Complexity. (Posted Sept. 2, 2019.)

My talk in "Mostly OM" at CUHK-ShenZhen The Sample Complexity in Data(Sample)-Driven Optimization. (May 31, 2019.)

Technical paper Interior-point Methods Strike Back: Solving the Wasserstein Barycenter Problem. (Posted May 31, 2019.)

Technical paper Managing Randomization in the Multi-Block Alternating Direction Method of Multipliers for Quadratic Optimization. (Posted March, 2019.)

Technical paper High-Dimensional Learning under Approximate Sparsity: A Unifying Framework for Nonsmooth Learning and Regularized Neural Networks. (Posted March, 2019.)

Paper Sample Average Approximation with Sparsity- Inducing Penalty for High-Dimensional Stochastic Programming. (Posted February 5, 2017; updated Januray 2019; appeared in online Math Programming.)

Manuscript On the Efficiency of Random Permutation for ADMM and Coordinate Descent. (Posted March 23, 2015; revised Dedember 2018, to appear in Math of OR; research supported in part by Chinese EPRI and by AFOSR Grant FA9550-12-1-0396.)

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; appeared in Math. Programming.)

My talk at "Optimization, Statistics and Uncertainty" of Berkeley Distributionally Robust Stochastic and Online Optimization -- Models/Algorithms for Data-Driven Optimization. (November 29, 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 the 2016-2017 Teaching Mote), and a supplement note. (Posted May 2017.)

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; to appear in Math Programming; 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 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 Linear and Nonlinear Programming by David G. Luenberger and Yinyu Ye has been published. Highlights to this edition include a special Chapter 6 devoted to Conic Linear Programming (CLP), a powerful generalization of Linear Programming. Another important topic is an Accelerated Steepest Descent Method that exhibits superior convergence properties, and the proof of the convergence property for both standard and accelerated Steepest Descent Methods (SDM). The third is the anslysis of (Block) Coordinate Descent (BCD) and Alternating Direction Method of Multipliers (ADMM). Click for detailed information , check for most recent ERRATA , and Instructor Solution Manual is available upon request.

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 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. Click here for the Ph.D. Thesis: Interior Algorithms for Linear, Quadratic and Linearly Constrained Convex Programming.

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