title
Detecting infeasibility in interior-point methods for optimization.

Michael Todd, School of Operations Research, Cornell University

 abstract:
Interior-point methods are both theoretically and practically
efficient algorithms for solving linear programming problems and
certain convex extensions. However, they seem to be less flexible
than the well-known simplex method: in particular, they do not deal
as gracefully with infeasible or unbounded (dual infeasible) problems.
One elegant way to produce either an optimal solution or a certificate
of infeasibility is to embed the original problem in
a larger homogeneous self-dual problem, but this seems less efficient
computationally. Most implementations use so-called
infeasible-interior-point methods, which focus exclusively on
attaining feasibility and optimality. However, such methods are
surprisingly successful in detecting infeasibility. We show that,
on infeasible problems, they can be viewed as implicitly searching
for an infeasibility certificate.


(Or ???

Do people optimize?

Michael J. Todd

Optimization talks are usually concerned with the questions:
what do people optimize (modelling), how do people optimize
(algorithms), and even can people optimize (complexity). We are
concerned with a perhaps more fundamental question: do
people optimize? Neoclassical demand theory holds that an
economic agent, given a set of prices and an income level,
chooses her demand vector to maximize some nontrivial utility
function over her budget set. Since utilities can't be observed,
this is a hypothesis that cannot directly be tested. But suppose
we observe a sequence of price vectors and associated demand
vectors. We can ask whether this data is consistent with
utility maximization. A fundamental theorem of S.N. Afriat gives
necessary and sufficient conditions for this consistency. We
provide a simple inductive proof of this theorem, which also
gives an O(n^3 + n^2 l) algorithm (n is the number of data points,
l the number of goods) to either construct a utility function that
rationalizes the data or show that this is impossible.

Joint work with Ana Fostel and Herb Scarf (Economics, Yale).

)