On motivating the Mitchell-Todd modification of Karmarkar's algorithm for LP problems with free variables

In this note, we first observe that the Morshedi-Tapia interpretation of the Karmarkar algorithm naturally offers an extension of the Karmarkar subproblem scaling to problems with free variables. We then note that this extended scaling is precisely the scaling suggested by Mitchell and Todd for problems with free variables. Mitchell and Todd gave no motivation for or justification of this extended scaling.This research was sponsored by NSF Cooperative Agreement No. CCR-88-09615, AFOSR Grant 89-0363, DOE Grant DEFG05-86-ER25017, ARO Grant 9DAAL03-90-G-0093, and COLCIENCIAS CO: 1106-05-307-93.     

An analogue of the Novikov Conjecture in complex algebraic geometry

We introduce an analogue of the Novikov Conjecture on higher signatures in the context of the algebraic geometry of (nonsingular) complex projective varieties. This conjecture asserts that certain ``higher Todd genera' are birational invariants. This implies birational invariance of certain extra combinations of Chern classes (beyond just the classical Todd genus) in the case of varieties with large fundamental group (in the topological sense). We prove the conjecture under the assumption of the ``strong Novikov Conjecture' for the fundamental group, which is known to be correct for many groups of geometric interest. We also show that, in a certain sense, our conjecture is best possible.

     

The Search for the Ultimate Baseball Statistic

Abstract

The Lady Tasting Tea: How Statistics Revolutionized Science in the Twentieth Century by David Salsburg. New York: W. H. Freeman and Co., 2001, pp. xi + 340, $23.95. Reviewed by Todd E. Bodner

Statisticians of the Centuries by C. C. Heyde and E. Seneta (Eds.). New York: Springer-Verlag, 2001, pp. xii + 500, $45.95. Reviewed by Todd E. Bodner     

Some Problems with the Russellian Open Future

In a recently published paper, Todd (Mind, 125(499), pp. 775–798, 2016a) advocates a novel treatment of future contingents. On his view, all statements concerning the contingent future are false. He motivates his semantic postulates by considerations in philosophy of time and modality, in particular by the claim that there is no actual future. I present a number of highly controversial consequences of Todd’s theory. Inadequacy of his semantics might indirectly serve as an argument against the philosophical view underpinning his proposal.     

The Nesterov–Todd Direction and Its Relation to Weighted Analytic Centers

The subject of this paper concerns differential-geometric properties of the Nesterov–Todd search direction for linear optimization over symmetric cones. In particular, we investigate the rescaled asymptotics of the associated flow near the central path. Our results imply that the Nesterov–Todd direction arises as the solution of a Newton system defined in terms of a certain transformation of the primal-dual feasible domain. This transformation has especially appealing properties which generalize the notion of weighted analytic centers for linear programming.     

A full step infeasible interior-point method for Cartesian $$P_{*}(\kappa )$$-SCLCP

In this paper, a new full Nesterov–Todd step infeasible interior-point method for Cartesian \(P_*(\kappa )\) linear complementarity problem over symmetric cone is considered. Our algorithm starts from a strictly feasible point of a perturbed problem, after a full Nesterov–Todd step for the new perturbed problem the obtained strictly feasible iterate is close to the central path of it, where closeness is measured by some merit function. Furthermore, the complexity bound of the algorithm is the best available for infeasible interior-point methods.     

Some variants of the todd low-complexity algorithm

Todd (Ref. 1) describes an interior-point algorithm for linear programming that is almost as simple as the affine-scaling method and yet achieves the currently best complexity of iterations to attain precisiont based on the primal-only potential function (x). In this paper, we propose some variants of the Todd algorithm by considering two local models: the -model, trying to reduce the potential function (x) as much as possible; and thec-model, trying to reduce the objective functionc ^T x as much as possible, with polynomiality retained. Some preliminary numerical results are presented to illustrate the behavior of these algorithms.The author would like to thank Professor Michael J. Todd and Dr. Zhijun Wu for studying an early version of this paper and for helpful suggestions and corrections.     

On two homogeneous self-dual approaches to linear programming and its extensions

We investigate the relation between interior-point algorithms applied to two homogeneous self-dual approaches to linear programming, one of which was proposed by Ye, Todd, and Mizuno and the other by Nesterov, Todd, and Ye. We obtain only a partial equivalence of path-following methods (the centering parameter for the first approach needs to be equal to zero or larger than one half), whereas complete equivalence of potential-reduction methods can be shown. The results extend to self-scaled conic programming and to semidefinite programming using the usual search directions. Received: July 1998 / Accepted: September 2000?Published online November 17, 2000     

The Todd character and cohomology operations

In “On the Conflict of Bordism of Finite Complexes” [J. Differential Geometry], Conner and Smith introduced a homomorphism called the Todd character, relating complex bordism theory to rational homology. Specifically the Todd character consists of a family of homomorphisms

$\text{th}{}_{\mathrm{r}}\text{: MU}{}_{\mathrm{s}}\text{(X) → H}{}_{\mathrm{s\to r}}\text{(X;}\text{Q}\text{)}$

.In L. Smith, The Todd character and the integrality theorem for the Chern character, Ill. J. Math. it was shown (note that the indexing of the Todd character is somewhat different here) that there was an integrality theorem for th analogous to the Adams integrality theorem for the Chern character J. F. Adams, On the Chern character and the structure of the unitary group, Proc. Cambridge Philos. Soc.57 (1961), 189–199; On the Chern character revisted, Ill. J. Math. Now Adams' first paper contains a wealth of information about the Chern character in addition to the integrality theorem already mentioned. Our objective in the present note is to derive analogous results for the Todd character. As in Smith these may then be used to deduce the results of Adams for the Chern character.     

Improved Criteria for Identifying Optimal Basic and Nonbasic Variables in LP

We derive new criteria for identifying whether a variable is basic or nonbasic at each optimal solution of a LP. Our criteria, stronger than those derived recently by Ye and Todd, can be combined with the central path-following algorithm.     

A Class of Polynomial Interior Point Algorithms for the Cartesian P-Matrix Linear Complementarity Problem over Symmetric Cones

In this paper, we present a new class of polynomial interior point algorithms for the Cartesian P-matrix linear complementarity problem over symmetric cones based on a parametric kernel function, which determines both search directions and the proximity measure between the iterate and the center path. The symmetrization of the search directions used in this paper is based on the Nesterov and Todd scaling scheme. By using Euclidean Jordan algebras, we derive the iteration bounds that match the currently best known iteration bounds for large- and small-update methods.     

On the computation of weighted analytic centers and dual ellipsoids with the projective algorithm

The primal projective algorithm for linear programs with unknown optimal objective function value is extended to the case where one uses a weighted Karmarkar potential function. This potential is defined with respect to a strict lower bound to the optimum. The minimization of this potential when the lower bound is kept fixed, yields a primal and a dual feasible solution. The dual solution is the weighted analytic center of a certain dual polytope. Finally one exhibits a pair of homothetic dual ellipsoids that extends results obtained by Sonnevend, Todd, Ye, Freund and Anstreicher.This research has been supported by NSERC-Canada, FCAR-Quebec and FNRS-Switzerland.     

The life and work of André Cholesky

Cholesky’s method for solving a system of linear equations with a symmetric positive definite matrix is well known. In this paper, I will give an account of the life of Cholesky, analyze an unknown and unpublished paper of him where he explains his method, and review his other scientific works. I dedicated this work to John (Jack) Todd with esteem and respect at the occasion of his 95th anniversary.     

A new interior-point algorithm based on modified Nesterov–Todd direction for symmetric cone linear complementarity problem

We present a new primal-dual path-following interior-point algorithm for linear complementarity problem over symmetric cones. The algorithm is based on a reformulation of the central path for finding the search directions. For a full Nesterov–Todd step feasible interior-point algorithm based on the search directions, the complexity bound of the algorithm with the small update approach is the best available.     

Approximate counting: A detailed analysis

Approximate counting is an algorithm proposed by R. Morris which makes it possible to keep approximate counts of large numbers in small counters. The algorithm is useful for gathering statistics of a large number of events as well as for applications related to data compression (Todd et al.). We provide here a complete analysis of approximate counting which establishes good convergence properties of the algorithm and allows to quantify precisely complexity-accuracy tradeoffs.     

New Complexity Analysis of the Primal–Dual Method for Semidefinite Optimization Based on the Nesterov–Todd Direction

Interior-point methods for semidefinite optimization have been studied intensively in recent times, due to their polynomial complexity and practical efficiency. In this paper, first we present some technical results about symmetric matrices. Then, we apply these results to give a unified analysis for both large update and small update interior-point methods for SDP based on the Nesterov–Todd (NT) direction.     

On Rank 2 Complex Reflection Groups

We describe a class of groups with the property that the finite ones among them are precisely the complex reflection groups of rank 2. This situation is reminiscent of Coxeter groups, among which the finite ones are precisely the real reflection groups. We also study braid relations between complex reflections and indicate connections to an axiomatic study of root systems and to the Shephard–Todd “collineation groups.”     

On discrete inequalities of Wirtinger's type

Discrete inequalities of Wirtinger's type are considered. Constants in the obtained inequalities are the best ones. In the special case the inequalities (1) and (2) are obtained. They are proved by K. Fan, O. Taussky, and J. Todd: Discrete analogs of inequalities of Wirtinger, Montash. Math.59 (1955), 73–79.     

Integral Grothendieck–Riemann–Roch theorem

We show that, in characteristic zero, the obvious integral version of the Grothendieck–Riemann–Roch formula obtained by clearing the denominators of the Todd and Chern characters is true (without having to divide the Chow groups by their torsion subgroups). The proof introduces an alternative to Grothendieck’s strategy: we use resolution of singularities and the weak factorization theorem for birational maps.