Michael J. Todd
School of Operations Research and Information Engineering
Michael J. Todd: Selected Publications

Some technical reports can be found at Todd1, Todd2, Todd3, and Todd4.

M.J. Todd, ``Abstract complementary pivot theory,'' Ph.D. dissertation, Yale University, 1972.

M.J. Todd, ``A generalized complementary pivoting algorithm,'' Mathematical Programming 6 (1974), 243--263. pdf file.

M.J. Todd, The Computation of Fixed Points and Applications, Lecture Notes in Economics and Mathematical Systems 124, Springer, 1976. ebook.

M.J. Todd, ``A note on computing equilibria in economies with activity analysis models of production,'' Journal of Mathematical Economics, 6 (1979), 135--144.

419. M.J. Todd , ``Some remarks on the relaxation method for linear inequalities,'' Technical Report, April 1979. pdf.

452. M.J. Todd, ``PLALGO: A FORTRAN implementation of a piecewise-linear homotopy algorithm for solving systems of nonlinear equations'' (April 1980, revised Nov. 1981 and July 1985). Available in rather poor-quality scanned form in pdf file 1 and pdf file 2.

R.G. Bland, D. Goldfarb, and M.J. Todd, ``The ellipsoid method: a survey,'' Operations Research 29 (1981) 1039--1091. pdf.

M.J. Todd and B.P. Burrell,``An extension of Karmarkar's algorithm for linear programming using dual variables,'' Algorithmica 1 (1986) 409--424. pdf

834. M.J. Todd,`` The Affine-Scaling Direction for Linear Programming is a Limit of Projective-Scaling Directions'' (Dec. 88). Linear Algebra and its Applications 152 (1991) 93-105. pdf.

836. M.J. Todd, ``Probabilistic Models for Linear Programming'' (Feb. 89). Mathematics of Operations Research 16 (1991) 671-693. Erratum.

857. M.J. Todd, ``The Effects of Degeneracy and Null and Unbounded Variables on Variants of Karmarkar's Linear Programming Algorithm'' (Aug. 89). In Large-Scale Numerical Optimization (T.F. Coleman and Y. Li, eds.), SIAM, Philadelphia, 1990, 81-91. pdf.

862. C.C. Gonzaga and M.J. Todd, ``An $O( \sqrt{n}L)$-Iteration Large-Step Primal-Dual Affine Algorithm for Linear Programming'' (Sept. 89). SIAM Journal on Optimization 2 (1992) 349-359.

877. M.J. Todd and Yufei Wang, ``On Combined Phase 1 - Phase 2 Projective Methods for Linear Programming'' (Dec. 89). Algorithmica 9 (1993) 64-83. pdf.

878. S. Mizuno, M.J. Todd, and Y. Ye, ``Anticipated Behavior of Path-Following Algorithms for Linear Programming'' (Dec. 89). pdf.

879. M.J. Todd, ``Anticipated Behavior of Karmarkar's Algorithm'' (Dec. 89). pdf.

882. S. Mizuno, M.J. Todd, and Y. Ye, ``Anticipated Behavior of Long-Step Algorithms for Linear Programming.`` (Jan. 90). pdf.

893. L.G. Khachiyan and M.J. Todd, ``On the complexity of approximating the maximal inscribed ellipsoid for a polytope'' (Feb. 90). Mathematical Programming 61 (1993) 137-159.

903. M.J. Todd, ``A low-complexity interior-point algorithm for linear programming'' (May 90). SIAM Journal on Optimization 2 (1992) 198-209.

907. M.J. Todd, ``Combining phase I and phase II in a potential reduction algorithm for linear programming'' (July 90). Mathematical Programming 59 (1993) 133-150.

944. S. Mizuno, M.J. Todd, and Y. Ye, ``On adaptive-step primal-dual interior-point algorithms for linear programming'' (Oct. 90). Mathematics of Operations Research 18 (1993) 964-981.

946. M.J. Todd and L. Tunçel, ``A new triangulation for simplicial algorithms'' (Dec. 90). SIAM Journal on Discrete Mathematics 6 (1993) 167-180.

950. M.J. Todd, ``Projected scaled steepest descent in Kojima-Mizuno-Yoshise's potential reduction algorithm for the linear complementarity problem'' (Dec. 90). pdf.

952. M.J. Todd and J.-P. Vial, ``Todd's low-complexity algorithm is a predictor-corrector path-following method'' (Dec. 90). Operations Research Letters 11 (1992) 199-207.

958. M.J. Todd, ``Playing with interior points'' (Feb. 91). COAL Newsletter of the Mathematical Programming Society 19 (1991) 17-25. pdf.

964. M.J. Todd, ``Another variational derivation of a self-scaling Quasi-Newton update formula'' (4/91). pdf.

978. M.J. Todd, ``Interior-point algorithms for semi-infinite programming'' (8/91). Mathematical Programming 65 (1994) 217-245.

995. M.J. Todd, ``Another derivation of the Karmarkar direction for linear programming'' (12/91). Revista Investigacion Operacional 26 (2005) 124-134. pdf.

997. A. Liao and M.J. Todd, ``The ellipsoid algorithm using parallel cuts'' (1/92). Computational Optimization and Applications 2 (1993) 299-316. pdf

1007. Y. Ye, M.J. Todd, and S. Mizuno, ``An $O(\sqrt{n}L$)-Iteration Homogeneous and Self-dual Linear Programming Algorithm'' (6/92). Mathematics of Operations Research 19 (1994) 53-67.

1014. S. Mizuno, M.J. Todd, and L. Tunçel, ``Monotonicity of Primal and Dual Objective Values in Primal-dual Interior Point Algorithms'' (7/92). SIAM Journal on Optimization 4 (1994) 613-625.

1016. R.M. Freund and M.J. Todd, ``Barrier Functions and Interior-Point Algorithms for Linear Programming with Zero-, One-, or Two-sided Bounds on the Variables'' (7/92). Condensed version in Mathematics of Operations Research 20 (1995) 415-440.

1023. S. Mizuno, M. Kojima, and M.J. Todd, ``Infeasible-Interior-Point Primal-Dual Potential-Reduction Algorithms for Linear Programming'' (8/92). SIAM Journal on Optimization 5 (1995) 52-67.

1031. L. Tunçel and M.J. Todd, ``Asymptotic Behavior of Interior-Point Methods: A View from Semi-Infinite Programming'' (9/92). Mathematics of Operations Research 21 (1996) 354-381.

1037. S. Mizuno, M.J. Todd and Y. Ye, ``A Surface of Analytic Centers and Infeasible- Interior-Point Algorithms for Linear Programming'' (1/93). Mathematics of Operations Research 20 (1995) 135-162.

1044. M.J. Todd, ``Analysis of Interior-Point Methods for Linear Programming Problems with Variable Upper Bounds'' (2/93). Advances in Optimization and Numerical Analysis, edited by Susana Gomez and Jean-Pierre Hennart, Mathematics and its Applications 275, Kluwer Academic Publishers, 1994, pp. 1-23. pdf

1050. M.J. Todd, ``A Lower Bound on the Number of Iterations of Primal-Dual Interior-Point Methods for Linear Programming'' (3/93). In the proceedings of the 15th Biennial Conference on Numerical Analysis at Dundee, Numerical Analysis 1993 (G.A. Watson and D.F. Griffiths, eds.), Pitman Research Notes in Mathematics 303, Longman Press, 1994, pp. 237-259. pdf

1064. A. Liao and M.J. Todd, ``Solving LP Problems Via Weighted Centers'' (8/93). SIAM Journal on Optimization 6 (1996) 933-960.

1067. M.J. Todd, ``Scaling, Shifting and Weighting in Interior-Point Methods'' (9/93). Computational Optimization and Applications 3 (1994) 305-315.

1071. R.H. Tütüncü and M.J. Todd, ``Reducing Horizontal Linear Complementarity Problems'' (10/93). Linear Algebra and its Applications 223/224 (1995) 717-729.

1082. M.J. Todd and Y. Ye, ``A Lower Bound on the Number of Iterations of Long-Step and Polynomial Interior-Point Linear Programming Algorithms'' (1/94). Annals of Operations Research 62 (1996) 233-252.

1091. Yu.E. Nesterov and M.J. Todd, ``Self-Scaled Barriers and Interior-Point Methods for Convex Programming'' (4/94). Mathematics of Operations Research 22 (1997) 1-42.

1097. S. Herzel and M.J. Todd, ``Two Interior-Point Algorithms for a Class of Convex Programming Problems'' (6/94). Optimization Methods and Software 5 (1995) 27-55. pdf.

1109. M.J. Todd and Y. Ye, ``Approximate Farkas Lemmas and Stopping Rules for Iterative Infeasible-Point Algorithms for Linear Programming'' (11/94). Mathematical Programming 81 (1998) 1-21.

1112. M.J. Todd, ``Potential-Reduction Methods in Mathematical Programming'' (1/95). Mathematical Programming 76 (1996) 3-45.

1125. Yu.E. Nesterov and M.J. Todd, ``Primal-Dual Interior-Point Methods for Self-Scaled Cones'' (5/95). SIAM Journal on Optimization 8 (1998) 324-364.

1135. L. Tunçel and M.J. Todd, ``On the Interplay Among Entropy, Variable Metrics and Potential Functions in Interior-Point Algorithms'' (9/95). Computational Optimization and Applications 8 (1997) 5-19. pdf

1154. M.J. Todd, K.C. Toh, and R.H. Tütüncü, ``On the Nesterov-Todd Direction in Semidefinite Programming'' (3/96). SIAM Journal on Optimization 8 (1998) 769-796.

1156. Yu.E. Nesterov, M.J. Todd, and Y. Ye, ``Infeasible-Start Primal-Dual Dethods and Infeasibility Detectors for Nonlinear Programming Problems'' (4/96). Mathematical Programming 84 (1999) 227-267.

1170. M.J. Todd, ``On Adjusting Parameters in Homotopy Methods for Linear Programming'' (7/96). In: Approximation Theory and Optimization, edited by M. Buhmann and A. Iserles, Cambridge University Press, 1997, pp. 201--220. pdf

1177. K.C. Toh, M.J. Todd, and R.H. Tütüncü, ``SDPT3 --- a Matlab Software Package for Semidefinite Programming'' (12/96). pdf, old version pdf. Matlab files in compressed tar format can be obtained from here or for earlier versions here. An earlier version of the guide appeared in Optimization Methods and Software 11 (1999) 545-581.

1205. M.J. Todd, ``A Study of Search Directions in Primal-Dual Interior-Point Methods for Semidefinite Programming'' (10/97). Optimization Methods and Software 11 (1999) 1-46. pdf

1213. S. Mizuno and M.J. Todd, ``On two homogeneous self-dual approaches to linear programming and its extensions'' (7/98) (Mathematical Programming 89 (2001), 517--534.

1219. M.J. Todd, L. Tunçel, and Y. Ye, ``Characterizations, bounds, and probabilistic analysis of two complexity measures for linear programming problems'' (9/98) (Mathematical Programming 90 (2001), 59--69.

1238. M. Wagner and M.J. Todd, ``Least-change quasi-Newton updates for equality-constrained optimization'' (5/99) (Mathematical Programming, 87 (2000), 317--350.

1253. E.A. Yildirim and M.J. Todd, ``Sensitivity analysis in linear programming and semidefinite programming using interior-point methods'' (11/99) (Mathematical Programming, 90 (2001), 229--261.

R.D.C. Monteiro and M.J. Todd, ``Path-following methods,'' in Handbook on Semidefinite Programming, H. Wolkowicz, R. Saigal, and L. Vandenberghe (eds.), Kluwer Academic Publishers, Boston-Dordrecht-London, 2000, pp. 267--306.

M.J. Todd,``The many facets of linear programming'' (7/00), (Mathematical Programming, 91 (2002), 417--436. pdf file.

1268. E.A. Yildirim and M.J. Todd, ``An interior-point approach to sensitivity analysis in degenerate linear programs'' (12/00) SIAM Journal on Optimization 12, pp. 692--714, 2002.

M.J. Todd,``Semidefinite optimization'' (2/01) (in Acta Numerica 10 (2001), pp. 515--560), pdf file.

R.H. Tütüncü, K.C. Toh, and M.J. Todd, ``Solving semidefinite-quadratic-linear programs using SDPT3'' (3/01) (Mathematical Programming, 95 (2003), 189--217. ps file, pdf file.

1290. Yu.E. Nesterov and M.J. Todd, ``On the Riemannian geometry defined by self-concordant barriers and interior-point methods'' (7/01)
( Foundations of Computational Mathematics, 2 (2002), 333--361, pdf.

R.H. Tütüncü, K.C. Toh, and M.J. Todd, ``SDPT3 --- A MATLAB software package for semidefinite-quadratic-linear programming, Version 3.0'' (8/01), pdf file. Matlab files in compressed tar format can be obtained from here or here.

1339. J.S. Marron, M.J. Todd, and J. Ahn, ``Distance Weighted Discrimination'' (7/02, revised 10/04), Journal of the American Statistical Association 102 (2007), 1267--1271. pdf file.

1363. M.J. Todd, ``Detecting Infeasibility in Infeasible-Interior-Point Methods for Optimization'' (1/03) (in: Foundations of Computational Mathematics, Minneapolis 2002, edited by Felipe Cucker, Ron DeVore, Peter Olver, Endre Suli, Cambridge University Press, 2004, pp. 157--192). pdf

1381. A. Fostel, H.E. Scarf, and M.J. Todd, ``Two New Proofs of Afriat's Theorem'' (6/03). pdf Shorter version in Cowles discussion paper series: pdf file. Economic Theory 24 (2004), 211--219

1388. B.K. Rangarajan and M.J. Todd, ``Convergence of infeasible-interior-point methods for self-scaled conic programming'' (10/03). pdf

K.C. Toh, R.H. Tütüncü, and M.J. Todd, ``On the implementation of SDPT3 (Version 3.1) --- A MATLAB software package for semidefinite-quadratic-linear programming'' (4/04), pdf file.

1410. M.J. Todd, ``Dual versus primal-dual interior-point methods for linear and conic programming'' (8/04). (Mathematical Programming 111 (2008), 301--313.

1421. K.C. Toh, R.H. Tütüncü, and M.J. Todd, ``Inexact primal-dual path-following algorithms for a special class of convex quadratic SDP and related problems'' (3/05). Pacific Journal of Optimization 3 (2007), 136--164. pdf

1426. M.J. Todd, ``Largest dual ellipsoids inscribed in dual cones'' (6/05). Mathematical Programming 117 (2009), 425--434.

1435. M.J. Todd and E.A. Yildirim, ``On Khachiyan's algorithm for the computation of minimum volume enclosing ellipsoids'' (9/05). Discrete Applied Mathematics 155 (2007), 1731--1744, online here. pdf.

1452. S.D. Ahipasaoglu, P. Sun, and M.J. Todd, ``Linear convergence of a modified Frank-Wolfe algorithm for computing minimum volume enclosing ellipsoids'' (10/06). Optimization Methods and Software 23 (2008), 5--19. TR1452.pdf. Abstract.

1468. A.S. Nemirovski and M.J. Todd, ``Interior-point methods for optimization'' (1/08). Acta Numerica 17 (2008), 191--234. Preliminary version: TR1468.pdf. Abstract.

X. Qiao, H. Zhang, Y. Liu, M.J. Todd, and J.S. Marron, ``Weighted distance weighted discrimination and its asymptotic properties,'' Journal of the American Statistical Association 105 (2010), 489, 401-414. pdf file.

1472. S.D. Ahipasaoglu and M.J. Todd, ``A Modified Frank-Wolfe Algorithm for Computing Minimum-Area Enclosing Ellipsoidal Cylinders: Theory and Algorithms'' (4/09), Computational Geometry, 46 (2013), 494--519. pdf.

K.C. Toh, M.J. Todd, and R.H. Tütüncü, ``On the implementation and usage of SDPT3 -- a Matlab software package for semidefinite-quadratic-linear programming, version 4.0,'' in the Handbook on Semidefinite, Conic and Polynomial Optimization, edited by Miguel F. Anjos and Jean B. Lasserre, Springer, 715--754. Preliminary version: pdf file.

M.J. Todd, ``Proportional response as iterated Cobb-Douglas,'' in Edith Elkind, Nimrod Megiddo, Peter Bro Miltersen, Vijay V. Vazirani, and Bernhard von Stengel, editors, Equilibrium Computation, Dagstuhl Seminar Proceedings, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany, 2010. pdf file.

H. Huang, Y. Liu, Y. Du, C.M. Perou, D.N. Hayes, M.J. Todd, and J.S. Marron, ``Multiclass distance-weighted discrimination'' (11/10), Journal of Computational and Graphical Statistics, 22 (2013) 953--969. early pdf file.

M. Gancarova and M.J. Todd, ``A robust robust optimization result'' (4/11), Operations Research Letters 40 (2012), 2--5. Longer version: TR1479.

G. Zakeri, D. Craigie, A. Philpott, and M.J. Todd, ``Optimization of demand response through peak shaving'' (10/13), Operations Research Letters 47 (2014), 97--101. pdf file.

M.J. Todd, ``An improved Kalai-Kleitman bound for the diameter of a polyhedron'' (3/14), SIAM Journal on Discrete Mathematics 28 (2014), 1944--1947. pdf file.

M.J. Todd, ``Computation, multiplicity, and comparative statics of Cournot equilibria in integers'' (9/14), Mathematics of Operations Research 41 (2016), 1125--1134. pdf file.

M.J. Todd, Minimum-Volume Ellipsoids, MOS/SIAM Series on Optimization , Vol. 23, SIAM, Philadelphia, 2016.

M.J. Todd, ``On max-k-sums'' (8/16), pdf file. Mathematical Programming 171 (2018), 489--517. The full final article can be read online here.

M.J. Todd, ``Can n^d+1 unit right d-simplices cover a right d-simplex with shortest side n+\epsilon?'' (11/17, revised 7/23), pdf file. To appear in Geombinatorics.

J. Lamperski, R.M. Freund, and M.J. Todd, ``An oblivious ellipsoid algorithm for solving a system if (in)feasible linear inequalities,'' (12/20), to appear in Mathematics of Operations Research, pdf file.

M.J. Todd, ``The ellipsoid method redux'' (1/23, revised 9/23), Communications in Optimization Theory 2024 (2024) 17. pdf file.

Short Vita

Courses

Lectures

Research

Selected Publications

Students & Co-Authors

Other Links

Todd Home

Back to Cornell ORIE