# Dr Sergey Sergeev MSc PhD

School of Mathematics

Associate Professor in Mathematical Optimisation

## Contact details

- Address
- School of Mathematics

Watson Building

University of Birmingham

Edgbaston

Birmingham

B15 2TT

UK

Sergey is Associate Professor of Mathematical Optimisation, who previously worked as a Research Fellow on max-linear systems, specialising in max algebra and tropical convexity. He has published more than 50 papers on these and other topics and received a grant award from EPSRC (active in 2017-2019). One of his current research ambitions is to develop the area of Tropical Optimisation (i.e., optimisation in tropical mathematics) and its applications, and he also has recent publications in public key cryptography based on tropical algebra. Sergey's current research interests also include Perron-Frobenius theory, bi-level optimisation and its applications, and game theory.

## Qualifications

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

## Biography

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 convex sets). 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 Optimisation for Railways" (joint with Professor Clive Roberts).

## Teaching

### Semester 1

LH/LM Game Theory and Multicriteria Decision Making

### Semester 2

LH/LM Integer Programming and Combinatorial Optimisation

## Research

### 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.

## Publications

### Recent publications

#### Article

Alhussaini, S, Collett, C & Sergeev, S 2024, 'On the tropical two-sided discrete logarithm and a key exchange protocol based on the tropical algebra of pairs', *Communications in Algebra*. https://doi.org/

Engel, G & Sergeev, S 2023, 'Bounding the row sum arithmetic mean by Perron roots of row-permuted matrices', *Linear Algebra and its Applications*, vol. 673, pp. 220-232. https://doi.org/

Sergeev, S & Kennedy-Cochran-Patrick, A 2023, 'Extending CSR decomposition to tropical inhomogenous matrix products', *Electronic Journal of Linear Algebra*, vol. 38, pp. 820-851. <https://journals.uwyo.edu/

Sergeev, S & Krivulin, N 2023, 'Minimizing maximum lateness in two-stage projects by tropical optimization', *Kybernetika*, vol. 58, no. 5, pp. 816-841. <https://www.kybernetika.cz/

Mufid, MS, Patel, E & Sergeev, S 2023, 'Solving linear equations over maxmin-ω systems', *Linear Algebra and its Applications*. https://doi.org/

Sergeev, S & Wang, H 2022, 'Extremality criteria for the supereigenvector space in max-plus algebra', *Linear Algebra and its Applications*, vol. 653, pp. 116-134. https://doi.org/

Muanalifah, A & Sergeev, S 2022, 'On the tropical discrete logarithm problem and security of a protocol based on tropical semidirect product', *Communications in Algebra*, vol. 50, no. 2, pp. 861-879. https://doi.org/

Parsons, J, Sergeev, S & Wang, H 2022, 'Tropical pseudolinear and pseudoquadratic optimization as parametric mean-payoff games', *Optimization*. https://doi.org/

Gavalec, M, Němcová, Z & Sergeev, S 2021, '(K,L) eigenvectors in max-min algebra', *Fuzzy Sets and Systems*, vol. 410, pp. 75-89. https://doi.org/

Kennedy-Cochran-Patrick, A, Merlet, G, Nowak, T & Sergeev, S 2021, 'New bounds on the periodicity transient of the powers of a tropical matrix: using cyclicity and factor rank', *Linear Algebra and its Applications*, vol. 611, pp. 279-309. https://doi.org/

Merlet, G, Nowak, T & Sergeev, S 2021, 'On the tightness of bounds for transients of weak CSR expansions and periodicity transients of critical rows and columns of tropical matrix powers', *Linear and Multilinear Algebra*. https://doi.org/

Muanalifah, A & Sergeev, S 2020, 'Modifying the tropical version of Stickel's key exchange protocol', *Applications of Mathematics*, vol. 65, no. 6, pp. 727-753. https://doi.org/

Niv, A, Maccaig, M & Sergeev, S 2020, 'Optimal assignments with supervisions', *Linear Algebra and its Applications*, vol. 595, pp. 72-100. https://doi.org/

Kennedy-Cochran-Patrick, A, Sergeev, S & Berezny, S 2019, 'A bound for the rank-one transient of inhomogeneous matrix products in special case', *Kybernetika*, vol. 55, no. 1, pp. 12-23. https://doi.org/

#### Chapter (peer-reviewed)

Sergeev, S & Liu, Z 2019, Tropical analogues of a Dempe-Franke bilevel optimization problem. in HA Le Thi, HM Le & TP Dinh (eds), *Optimization of Complex Systems: Theory, Models, Algorithms: Proceedings of the World Congress on global Optimization 2019.* Advances in intelligent systems and computing, vol. 991, Springer, pp. 691-701. https://doi.org/