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.
Tropical linear algebra
In collaboration with Professors P. Butkovic and H. Schneider, Sergey generalised 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 a non-negative 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.
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.