University of Birmingham > Talks@bham > Optimisation and Numerical Analysis Seminars > On special cases of the generalised max-plus eigenproblem

On special cases of the generalised max-plus eigenproblem

Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact Sergey Sergeev.

We study the generalised eigenproblem (GEP) Ax = \lambda Bx, where A and B are real, m x n matrices in the max-plus algebra. Efforts are usually concentrated on finding the spectrum – that is, the set of \lambda for which there exists a solution x. In general, there is no known polynomial method for finding the spectrum. It is known that if A and B are symmetric, then there is at most one generalised eigenvalue – but no description of this unique candidate is known in general.

We find solutions in polynomial time for three special cases of GEP . First, we prove that if C = A – B (in the conventional linear sense) is symmetric, then the common value of all saddle points of C (if any) is the unique candidate for \lambda. Next, we explicitly describe the whole spectrum in the case when B is an outer product. It follows that when A is symmetric and B is constant, then the smallest column maximum of A is the unique candidate for \lambda. We present an idea for a real world application (in car manufacturing) when the outer product case may be used. Finally, we provide a complete description of the spectrum when n = 2.

This talk is part of the Optimisation and Numerical Analysis Seminars series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

 

Talks@bham, University of Birmingham. Contact Us | Help and Documentation | Privacy and Publicity.
talks@bham is based on talks.cam from the University of Cambridge.