** A Fresh Look at the Complexity of Pivoting in Linear Complementarity**
(May 2009-October 2012, financed by the Swiss National Science Foundation.)

We propose to study both linear and convex quadratic programming in a more general setting: by examining the linear complementarity problem with sufficient matrices. Besides providing a unifying framework for the two problems, linear complementarity also has many direct applications, e.g. in control theory, finance, algorithmic game theory.

The tools we will use in our research can generally be described as combinatorial abstract models of optimisation problems. We concentrate on two of them: oriented matroids and unique-sink orientations.

Several algorithms have been suggested by previous research in this area. For most of them there are both positive and negative results: they are known to be polynomial on some subclasses of the problems, but super-polynomial on other, larger classes. For many classes, however, such analysis is missing (among them are the two we consider the most important, that is, LCP with P-matrices and with sufficient matrices). At present randomised algorithms appear promising, and hence we plan to concentrate on their analysis.

We plan to attack the problem from two sides. We aim to find new classes of problems for which some algorithm runs in polynomial (or expected polynomial) time; and we will search for new examples of abstract optimisation problems for which known algorithms are slow. This will in turn reduce the gap between positive and negative results for these algorithms. We believe that this approach will eventually lead to a strongly polynomial algorithm for the linear complementarity problem with sufficient matrices.

(Jointly with: Jan Foniok, ETHZ)

** Polytopes, Matroids and Polynomial Systems
-- Studies through the fusion of geometric, combinatorial and algebraic algorithms**
(October 2004-September 2007, financed by the Swiss National Science Foundation.)

This project concerns research themes that interlink four
domains in mathematics: *combinatorics*, *algebra*, *geometry* and
*optimization*. We address fundamental questions and applications that
rely crucially on this fusion.
Our strong drive for this fusion of the established research domains
comes from the observation that several fundamental
problems spreading over these domains are closely interlinked:
a solution to one of the problems
often leads to a solution for another one in a different domain.
More precisely, we propose to study the following four specific research themes (with its
principal domain).

- I. Classifications of Oriented Matroids (Combinatorics)
- II. State Polytopes of Polynomial Ideals (Algebra)
- III. Minkowski Addition of Polytopes and Convex Hull (Geometric Computation)
- IV. Solving Polynomial Systems and SDPs via Structure Information (Optimization)

Each of the four themes has a long history of earlier investigations in its
principal domain. With these themes studied extensively for many years,
it is becoming increasing evident that these four themes are closely related
and inseparable.
In fact, there are underlying mathematical structures, *convex polytopes*, *matroids* and
*polynomials* common to all these themes.
Our belief is that it makes much more sense to investigate them
together. Our research team consists of active researchers, each with
at least two domains of competence and strong interests in
making this nontrivial fusion.

(Jointly with: E. Feichtner, ETHZ,
P. Parrilo, MIT, and
R. Thomas, University of Washington)

Written by Komei Fukuda (ETH Zurich, Switzerland) return

Last updated: May 14, 2012