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

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

Working paper A Mathematical Formulation for Optimal Load Shifting of Electricity Demand. (Posted December 10, 2015; research supported in part by Chinese EPRI.)

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

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

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 A Dynamic Near-Optimal Algorithm for Online Linear Programming is available. (Posted Nov 16, updated Nov 20, 2009; appeared in Operations Research.)

Working paper The Value of Stochastic Modeling in Two-Stage Stochastic Programs with Cost Uncertainty is available. (Posted 8/21, 2014; appeared in Operations Research.)

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

Working paper Analytical results and efficient algorithm for optimal portfolio deleveraging with market impact. (Posted October 30, 2013; research supported by AFOSR Grant FA9550-12-1-0396; appeared in Operations Research.)

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; appeared in Operations Research.)

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

The new working paper Beyond Convex Relaxation: A Polynomial–Time Non-Convex Optimization Approach to Network Localization . (Posted November 18, 2012; appeared in INFOCOM 2013.)

The new working paper A Homogeneous Interior-Point Algorithm for Nonsymmetric Convex Conic Optimization. (Posted November 16, 2012, appeared in Math Programming.)

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 Math of Operations Research.)

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

My tutorial at INFORMS Beijing 20012 Recent Linear Programming Developments. (Posted June 25, 2012.)

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

Working paper Computational Models and Complexities of Tarski's Fixed Points is available. (Posted September 27, 2011)

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

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

Research note "A Note on the Complexity of $L_p$ Minimization" 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.)

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