Michael J. Todd
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Michael J. Todd has a total of 12 co-authors. Here are the top co-authors by number of shared publications:
- Robert M. Freund
MIT Sloan School of Management 77 Massachusetts Avenue 02139 Cambridge MA USA
2 shared publications - Arkadi Nemirovski
School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, USA
1 shared publication - Charles M. Perou
University of North Carolina at Chapel Hill 1 Lineberger Comprehensive Cancer Center Chapel Hill, North Carolina
1 shared publication - David Neil Hayes
University of Tennessee Health Science Center UTHSC Center for Cancer Research Memphis, TN
1 shared publication Hanwen Huang
Department of Statistics and Operations Research , University of North Carolina at Chapel Hill , Chapel Hill , NC , 27599 ; Center for Clinical and Translational Sciences , University of Texas Health Science Center , Houston , TX , 77030
1 shared publication- James Stephen Marron
University of North Carolina at Chapel Hill
1 shared publication
Latest Publications
- 1 February 2024
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 49 (1) , 204-231
An Oblivious Ellipsoid Algorithm for Solving a System of (In)Feasible Linear Inequalities
- 1 February 2024
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 49 (1) , 204-231
An Oblivious Ellipsoid Algorithm for Solving a System of (In)Feasible Linear Inequalities
- Open Access
The ellipsoid method redux
We reconsider the ellipsoid method for linear inequalities. Using the ellipsoid representation of Burrell and Todd, we show the method can be viewed as coordinate descent on the volume of an enclosing ellipsoid, or on a potential function, or on both. The method can be enhanced by improving the lower bounds generated and by allowing the weights on inequalities to be decreased as well as increased, while still guaranteeing a decrease in volume. Three different initialization schemes are described, and preliminary computational results given. Despite the improvements discussed, these are not encouraging.
Open AccessThe ellipsoid method redux
We reconsider the ellipsoid method for linear inequalities. Using the ellipsoid representation of Burrell and Todd, we show the method can be viewed as coordinate descent on the volume of an enclosing ellipsoid, or on a potential function, or on both. The method can be enhanced by improving the lower bounds generated and by allowing the weights on inequalities to be decreased as well as increased, while still guaranteeing a decrease in volume. Three different initialization schemes are described, and preliminary computational results given. Despite the improvements discussed, these are not encouraging.
- Open Access
An Oblivious Ellipsoid Algorithm for Solving a System of (In)Feasible Linear Inequalities
The ellipsoid algorithm is a fundamental algorithm for computing a solution to the system of $m$ linear inequalities in $n$ variables $(P): A^{\top}x \le u$ when its set of solutions has positive volume. However, when $(P)$ is infeasible, the ellipsoid algorithm has no mechanism for proving that $(P)$ is infeasible. This is in contrast to the other two fundamental algorithms for tackling $(P)$, namely the simplex method and interior-point methods, each of which can be easily implemented in a way that either produces a solution of $(P)$ or proves that $(P)$ is infeasible by producing a solution to the alternative system $\mathrm{({\it Alt})}: A\lambda= 0$, $u^{\top}\lambda < 0$, $\lambda \ge 0$. This paper develops an Oblivious Ellipsoid Algorithm (OEA) that either produces a solution of $(P)$ or produces a solution of $\mathrm{({\it Alt})}$. Depending on the dimensions and on other natural condition measures, the computational complexity of the basic OEA may be worse than, the same as, or better than that of the standard ellipsoid algorithm. We also present two modified versions of OEA, whose computational complexity is superior to that of OEA when $n \ll m$. This is achieved in the first modified version by proving infeasibility without actually producing a solution of $\mathrm{({\it Alt})}$, and in the second modified version by using more memory.Open AccessAn Oblivious Ellipsoid Algorithm for Solving a System of (In)Feasible Linear Inequalities
The ellipsoid algorithm is a fundamental algorithm for computing a solution to the system of $m$ linear inequalities in $n$ variables $(P): A^{\top}x \le u$ when its set of solutions has positive volume. However, when $(P)$ is infeasible, the ellipsoid algorithm has no mechanism for proving that $(P)$ is infeasible. This is in contrast to the other two fundamental algorithms for tackling $(P)$, namely the simplex method and interior-point methods, each of which can be easily implemented in a way that either produces a solution of $(P)$ or proves that $(P)$ is infeasible by producing a solution to the alternative system $\mathrm{({\it Alt})}: A\lambda= 0$, $u^{\top}\lambda < 0$, $\lambda \ge 0$. This paper develops an Oblivious Ellipsoid Algorithm (OEA) that either produces a solution of $(P)$ or produces a solution of $\mathrm{({\it Alt})}$. Depending on the dimensions and on other natural condition measures, the computational complexity of the basic OEA may be worse than, the same as, or better than that of the standard ellipsoid algorithm. We also present two modified versions of OEA, whose computational complexity is superior to that of OEA when $n \ll m$. This is achieved in the first modified version by proving infeasibility without actually producing a solution of $\mathrm{({\it Alt})}$, and in the second modified version by using more memory. - Open AccessCan $n^d + 1$ unit right $d$-simplices cover a right $d$-simplex with shortest side $n + ε$?In a famous short paper, Conway and Soifer show that $n^2 + 2$ equilateral triangles with edge length 1 can cover one with side $n + \epsilon$. We provide a generalization to $d$ dimensions.Open AccessCan $n^d + 1$ unit right $d$-simplices cover a right $d$-simplex with shortest side $n + ε$?In a famous short paper, Conway and Soifer show that $n^2 + 2$ equilateral triangles with edge length 1 can cover one with side $n + \epsilon$. We provide a generalization to $d$ dimensions.
- 26 October 2017
- Published by Springer Nature in Mathematical Programming
- Vol. 171 (1-2) , 489-517
On max-k-sums
- 26 October 2017
- Published by Springer Nature in Mathematical Programming
- Vol. 171 (1-2) , 489-517
On max-k-sums
- Open Access
An improved Kalai-Kleitman bound for the diameter of a polyhedron
Kalai and Kleitman established the bound $n^{\log(d) + 2}$ for the diameter of a $d$-dimensional polyhedron with $n$ facets. Here we improve the bound slightly to $(n-d)^{\log(d)}$.Open AccessAn improved Kalai-Kleitman bound for the diameter of a polyhedron
Kalai and Kleitman established the bound $n^{\log(d) + 2}$ for the diameter of a $d$-dimensional polyhedron with $n$ facets. Here we improve the bound slightly to $(n-d)^{\log(d)}$. - 1 October 2013
- Published by Taylor & Francis in Journal of Computational and Graphical Statistics
- Vol. 22 (4) , 953-969
Multiclass Distance-Weighted Discrimination
In this article, we extend the binary distance-weighted discrimination (DWD) to the multiclass case. In addition to the usual extensions that combine several binary DWD classifiers, we propose a global multiclass DWD (MDWD) that finds a single classifier that considers all classes at once. Our theoretical results show that MDWD is Fisher consistent, even in the particularly challenging case when there is no dominating class, that is, a class with probability bigger than 0.5. The performance of different multiclass DWD methods is assessed through simulation studies and application to real microarray datasets. Comparison with the support vector machines is also provided. MATLAB implementation of the proposed methods is given in the online supplementary materials.
- 1 October 2013
- Published by Taylor & Francis in Journal of Computational and Graphical Statistics
- Vol. 22 (4) , 953-969
Multiclass Distance-Weighted Discrimination
In this article, we extend the binary distance-weighted discrimination (DWD) to the multiclass case. In addition to the usual extensions that combine several binary DWD classifiers, we propose a global multiclass DWD (MDWD) that finds a single classifier that considers all classes at once. Our theoretical results show that MDWD is Fisher consistent, even in the particularly challenging case when there is no dominating class, that is, a class with probability bigger than 0.5. The performance of different multiclass DWD methods is assessed through simulation studies and application to real microarray datasets. Comparison with the support vector machines is also provided. MATLAB implementation of the proposed methods is given in the online supplementary materials.
- Open Access
- 1 January 2011
- Published by American Mathematical Society (AMS) in Bulletin of the American Mathematical Society
- Vol. 48 (1) , 123
Book Review: The basic George B. Dantzig
- 1 January 2011
- Published by American Mathematical Society (AMS) in Bulletin of the American Mathematical Society
- Vol. 48 (1) , 123
Open AccessBook Review: The basic George B. Dantzig
- 25 April 2008
- Published by Cambridge University Press (CUP) in Acta Numerica
- Vol. 17, 191-234
Interior-point methods for optimization
This article describes the current state of the art of interior-point methods (IPMs) for convex, conic, and general nonlinear optimization. We discuss the theory, outline the algorithms, and comment on the applicability of this class of methods, which have revolutionized the field over the last twenty years.
- 25 April 2008
- Published by Cambridge University Press (CUP) in Acta Numerica
- Vol. 17, 191-234
Interior-point methods for optimization
This article describes the current state of the art of interior-point methods (IPMs) for convex, conic, and general nonlinear optimization. We discuss the theory, outline the algorithms, and comment on the applicability of this class of methods, which have revolutionized the field over the last twenty years.
- 1 February 2008
- Published by Taylor & Francis in Optimization Methods and Software
- Vol. 23 (1) , 5-19
Linear convergence of a modified Frank–Wolfe algorithm for computing minimum-volume enclosing ellipsoids
We show the linear convergence of a simple first-order algorithm for the minimum-volume enclosing ellipsoid problem and its dual, the D-optimal design problem of statistics. Using similar techniques, we show the linear convergence of the Frank–Wolfe algorithm with away steps applied to the simplex, under conditions different from those of Guélat and Marcotte. Computational tests confirm the attractive features of this method.
- 1 February 2008
- Published by Taylor & Francis in Optimization Methods and Software
- Vol. 23 (1) , 5-19
Linear convergence of a modified Frank–Wolfe algorithm for computing minimum-volume enclosing ellipsoids
We show the linear convergence of a simple first-order algorithm for the minimum-volume enclosing ellipsoid problem and its dual, the D-optimal design problem of statistics. Using similar techniques, we show the linear convergence of the Frank–Wolfe algorithm with away steps applied to the simplex, under conditions different from those of Guélat and Marcotte. Computational tests confirm the attractive features of this method.