Dr Sergey Sergeev

• PhD in Mathematics (Moscow State University, 18 April 2008)
• MSc in Physics (Moscow State University, 31 January 2004)

Sergey Sergeev was born in Moscow in 1981 and lived there until 2008, when he defended a PhD in Mathematics at the Faculty of Mechanics and Mathematics of M.V. Lomonosov Moscow State University and went to Birmingham to work with Peter Butkovic on a research project.  Sergey also has MSc in Physics, obtained from the Physics Department of the same University in 2004.

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 convex sets).

In 2008 Sergey became a Research Fellow in Birmingham and worked 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. Together they wrote several works on tropical linear algebra (on the tropical matrix powers, visualisation scaling and, later, on Z-matrix equations). Sergey also did some research in tropical convexity and the connection between tropical algebra and mean-payoff games, with S. Gaubert.  In 2010 Sergey went to France (Ecole Polytechnique), where he worked in the Max-plus team of S. Gaubert, on the tropical analogue of linear-fractional programming. In 2012 he returned to Birmingham to work 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 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).

In 2015-2019 Sergey was the module lead for Non-Linear Programming II. The module was aimed for a small cohort of 4th year students and Ph.D students, with the syllabus based on Dynamic Programming and Optimal Control.

Since 2019, Sergey has been the module lead of Combinatorial Optimisation (part of the 3IPCO module) and Game Theory (part of the 3GTMDM module).

Sergey’s other teaching duties include:

• Supervising PhD students (see below in the research part)
• Supervising MSci projects in Tropical Optimisation and Financial Engineering
• Supervising Research Skills and Summer Projects (MSc) in Financial Engineering
• Year 1 and Year 2 tutorials

Sergey’s main research activity has been in the area of tropical linear algebra and tropical convexity. These are the linear algebra and convex geometry 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. These areas can be viewed in a more general framework of idempotent/tropical mathematics, which has applications in such diverse areas as algebraic geometry, discrete event systems, scheduling, optimal control and Hamilton-Jacobi PDE’s, string comparison algorithms, static analysis of computer programs.

His main achievements in tropical linear algebra and tropical convexity can be briefly described as follows. Citations refer to the list of selected papers given below.

1. In collaboration with P. Butkovic and 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 [6,7,10]. In the same collaboration they developed the tropical analogue of the theory of Z-matrix equations (of the form x=Ax+b)[11], commuting matrices (with R.D. Katz [8] ) and the core of nonnegative matrix [14]. With G.Merlet and T. Nowak, Sergey applied the CSR expansion idea to obtain new more efficient bounds on the periodicity of tropical matrix powers [18,19].
2. In collaboration with S. Gaubert [3] 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, the group proposed the first known method for computing the whole spectrum of tropical two-matrix eigenproblem[13], and worked (with R.D. Katz) on new algorithms of tropical linear programming and their possible application to static analysis of computer programs [9]. A number of results on tropical convexity were also obtained in an individual paper [5] and in collaboration with V. Nitica [16,17]. Notably, they also developed an analogue of tropical convexity over max-min semiring. Based on the same geometric intuition, Sergey also described eigenvectors in max-min and max-Lukasiewicz linear algebra, in joint works with M. Gavalec and Z. Nemcova [23, 30]
3. The main outcomes of the EPSRC grant “Tropical Optimisation” are: 1) the development of a new tropical implementation of the AHP decision method (joint work with N. Krivulin [28]), 2) solution of some problems of tropical bi-level optimisation (joint work with Z. Liu [27]), 3) new bounds on the rank-one transient of tropical inhomogeneous matrix products in a special case (with A. Kennedy-Cochran-Patrick and S. Berezny [26]), 4) application of tropical Jacobi identity to analysing optimal assignments with supervisions (joint with A. Niv and M. Maccaig [29])

Apart from the tropical linearity, his interests also include nonlinear optimisation, combinatorial games, nonnegative matrices, theory of partially ordered sets, linear algebra over fuzzy semirings, abstract convexity, Perron-Frobenius theory and diagonal similarity matrix scaling.

Currently, Sergey has two PhD students: Arthur Kennedy-Cochran-Patrick and Any Muanalifah. Both of them started in 2017.

Arthur’s work is focused on tropical non-homogeneous matrix products [P1] and transients of periodicity of tropical matrix powers [P2]. Particularly, preprint [P1] is generalising the approach and the results of [26]. In this preprint, new CSR decompositions of inhomogeneous matrix products are defined and new bounds on the factor rank transient of such products are obtained, in an important special case.

Any has been working on applications of tropical algebra in cryptography. In particular, new modifications of the tropical version of Stickel’s protocol have been suggested and some attacks on them have been described in [P3] (accepted for publication in Applications of Mathematics). The ongoing work is concerned with developing some new attacks on the protocols proposed in the works of Grigoriev and Shpilrain.  

Recent supervision of MSci students also resulted in new research: see in particular [P4] based on the MSci project of J. Parsons (supervised in 2018-19) and developed during the visit of H. Wang in 2020.  This work is developing the application of mean-payoff game solvers to tropical pseudolinear and tropical pseudoquadratic optimisation.