Dr Sergey Sergeev MSc PhD

• PhD in Mathematics, Moscow State University
• MSc in Physics, Moscow State University

Sergey Sergeev defended a PhD in Mathematics at the Faculty of Mechanics and Mathematics of M.V. Lomonosov Moscow State University. The tropical mathematics has been his research area from the very beginning. In the Physics Department of MSU, Sergey studied under the guidance of A.N. Sobolevskii, G.L. Litvinov and academician V.P. Maslov, his official supervisor. His main area of interest was tropical convexity (from tropical segments to tropical cones and the Hahn-Banach separation of several tropically convexsets). Sergey also has MSc in Physics, obtained from the Physics Department of the same University.

At the next stage of his career, Sergey went to Birmingham to work with Peter Butkovic on an EPSRC funded project "Feasibility and Reachability in Max-linear Systems" with P. Butkovic, the Principal Investigator for the project, and Visiting Researcher, H. Schneider. His next postdoc was in France (Ecole Polytechnique), where he worked in the Max-plus team of S. Gaubert, on the tropical analogue of linear-fractional programming. The third postdoc was again in Birmingham, where Sergey worked as a Research Fellow on another EPSRC funded project.

Since March 2014 Sergey has been permanently employed as a Lecturer in Mathematical Optimisation, and he was further promoted to Senior Lecturer/Associate Professor in 2020.

In 2016 he was awarded an EPSRC funded grant EP/P019676/1 "Tropical Optimisation", on which he worked in 2017-2019, focused on various forms of tropical optimisation such as tropical pseudoquadratic and bi-level optimisation.

Sergey has been active as organiser of one-day minisymposia in Tropical Mathematics such as a minisymposium on Tropical Mathematics and its Applications in the framework of ILAS-2016 conference in Leuven, Belgium and LMS Workshop on Tropical Mathematics held in Birmingham, November 2017. In June 2018, Sergey co-organized a one-day conference "Tropical Mathematics and Optimization for Railways" (joint with Professor Clive Roberts).

Semester 1

LH/LM Integer Programming and Combinatorial Optimisation

Semester 2

LH/LM Game Theory and Multicriteria Decision Making

Research Themes

• Linear algebra, convexity and optimisation over tropical (max-plus) semiring and other semirings (in particular, max-min)
• Bi-level/multilevel optimisation
• Nonnegative matrices and Perron-Frobenius theory
• Public key cryptography (based on tropical linear algebra and more general)

 Research Activity

Sergey's main research activity has been in the areas of tropical linear algebra, tropical convexity and tropical optimisation. More generally, tropical mathematics encompasses various mathematical areas developed over the max-plus semiring: the set of real numbers with adjoined negative infinity element, equipped with the addition “a+ b”:= max(a, b) and the multiplication “ab” = a + b. Tropical mathematics has applications in such diverse areas as algebraic geometry, discrete event systems, scheduling, optimal control and Hamilton-Jacobi PDE, string comparison algorithms, static analysis of computer programs.

More recently, Sergey has become more interested in more applied topics, related to optimisation and operations research, as well as public key cryptography.

Some of Sergey’s research (both more recent and less recent) is summarised below.

Work on EPSRC project "Tropical Optimisation"

Much of Sergey’s most recent research can be linked to the work on EPSRC grant "Tropical Optimisation", see Tropical Optimisation (ukri.org) The main results of this work include

• Development of a new tropical implementation of the AHP decision method (joint work with N. Krivulin)
• Solving problems of tropical pseudoquadratic optimisation using mean-payoff games (in a joint work with J. Parsons and H. Wang)
• Development of tropical bi-level optimisation (in a joint work with Z. Liu),
• New bounds on the rank transient of tropical inhomogeneous matrix products (joint works with A. Kennedy-Cochran-Patrick and S. Berezny)
• Application of tropical Jacobi identity to analysing optimal assignments with supervisions (joint work with A. Niv and M. Maccaig)

 Recent joint research with PhD and MSci students

Sergey has supervised two PhD students, both of them successfully graduated: Arthur Kennedy-Cochran-Patrick and Any Muanalifah, and a number of MSci students, whose projects also aimed at obtaining new research results.  

• Joint research with Arthur was focused on tropical non-homogeneous matrix products and transients of periodicity of tropical matrix powers. In the joint work with Arthur, ultimate regime of inhomogeneous tropical matrix products was studied using the CSR decomposition concept and some new bounds on the factor rank transient of such products were obtained, in some important special cases. In collaboration with Arthur my long-term coauthors G. Merlet and T. Nowak, we also continued some of my previous research aiming to improve the transience bounds for ultimate periodicity of tropical matrix powers.
• Joint research with Any has been on applications of tropical algebra in cryptography. In particular, new modifications of the tropical version of Stickel’s protocol were suggested and some attacks on them were described. We also suggested an attack on one of the protocols constructed earlier by Grigoriev and Shpilrain (based on the tropical semidirect product). The attack essentially used some of Sergey’s previous works on ultimate periodicity of tropical matrix powers.
• Recent supervision of MSci students also resulted in new research. One of the most recent papers is based on the MSci project of J. Parsons (supervised in 2018-19) and developed during the visit of H. Wang in 2020.  This work developed the application of mean-payoff game solvers to tropical pseudolinear and tropical pseudoquadratic optimisation.

Earlier work on tropical linear algebra and tropical convexity

Sergey’s earlier research was mainly on tropical linear algebra and tropical convexity, and some of the main contributions are described below.

1. Tropical linear algebra. In collaboration with Prof. P. Butkovic and Prof. H. Schneider, Sergey generalized  the cyclicity theorem on tropical matrix powers to the reducible case in the form of CSR expansions and described attraction cones (sets of vectors converging to an eigenvector) as solution sets of tropical linear systems of equations.  They also worked on generators, extremals and weak bases of tropical linear spaces and Minkowski’s theorem, on diagonal similarity scaling (coining the term “visualisation” and “visualisation scaling”), on the tropical analogue of the theory of Z-matrix equations (of the form x=Ax+b), on tropical commuting matrices (also with R.D. Katz) and on the core of nonnegative matrix, among some other topics. Teaming up with G.Merlet and T. Nowak, Sergey later applied the CSR expansion idea to obtain a number of new efficient bounds on the periodicity of tropical matrix powers. Sergey later also worked on describing eigenvectors in max-min and max-Lukasiewicz linear algebra, in joint works with M. Gavalec and Z. Nemcova.
2. Tropical convexity. In collaboration with S. Gaubert, Sergey introduced the max-plus analogue of cyclic projections method, obtaining separation theorem for several max-plus convex sets, and deducing the max-plus analogue of Helly’s theorem. Using equivalence between tropical polyhedra and mean-payoff games, Gaubert and Sergeev also proposed the first known method for computing the whole spectrum of tropical two-matrix eigenproblem, and worked (also with R.D. Katz) on new algorithms of tropical linear programming. Later, a number of new results on tropical convexity over max-min semiring were obtained in joint works with V. Nitica, in particular on colourful versions of Helly and Caratheodory theorems.