# Dr Sergey Sergeev

School of Mathematics

Senior Lecturer in Mathematical Optimisation

## Contact details

- Address
- School of Mathematics

Watson Building

University of Birmingham

Edgbaston

Birmingham

B15 2TT

UK

Sergey is a Senior Lecturer in Mathematical Optimisation who previously worked as a Research Fellow on max-linear systems, specializing in max algebra and tropical convexity. His current ambition is to develop the area of Tropical Optimisation (i.e., optimisation in tropical mathematics) and its applications.

Sergey's current research interests also include Perron-Frobenius theory, bi-level optimisation, combinatorial games and public key cryptography.

## Qualifications

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

## Biography

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

## Teaching

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

## Research

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.

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

## Publications

- P. Butkovic, H. Schneider and S. Sergeev.
*Generators, bases and extremals of max cones*. Linear Algebra and its Applications 421 (2007), 394-406. - S. Sergeev.
*Max-plus definite matrix closures and their eigenspaces*. Linear Algebra and its Applications 421 (2007), 182-201. - S. Gaubert and S. Sergeev.
*Cyclic projections and separation theorems in idempotent convex geometry*. Fundamental’naya i Prikladnaya Matematika 13, no 4 (2007), 31-52 (in Russian). English version: Journal of Mathematical Sciences 155, no. 4 (2008). - S. Sergeev.
*Max-algebraic powers of irreducible matrices in the periodic regime: An application of cyclic classes*. Linear Algebra and Its Applications 431 (2009), 1325-1339. - S. Sergeev,
*Multiorder, Kleene Stars and Cyclic Projectors in the Geometry of Max Cones (PDF)*. In: G.L. Litvinov and S.N. Sergeev (Eds.) Tropical and Idempotent Mathematics , volume 495 of Contemporary Mathematics, 2009, pages 317-342. - S. Sergeev, H. Schneider and P. Butkovic,
*On visualization scaling, subeigenvectors and Kleene stars in max algebra*. Linear Algebra and its Applications 431, 2009, pp. 2395 – 2406. - S. Sergeev,
*Max-algebraic attraction cones of nonnegative irreducible matrices*. Linear Algebra Appl., 435 (2011), 1736-1757. - R.D. Katz, H. Schneider and S. Sergeev.
*On commuting matrices in max algebra and in nonnegative linear algebra*. Linear Algebra Appl., 436 (2012), 276-292. - S. Gaubert, R.D. Katz and S. Sergeev.
*Tropical linear-fractional programming and parametric mean payoff games*. Journal of Symbolic Computation, 47 no. 12, 2012, 1447-1478. - S. Sergeev and H. Schneider.
*CSR expansions of matrix powers in max algebra (PDF)*. Trans. Amer. Math.Soc., 364, 2012, 5969-5994 - P. Butkovic, H. Schneider and S. Sergeev,
*Z-matrix equations in max algebra, nonnegative linear algebra and other semirings*. Linear and Multilinear Algebra, 60 no.10, 2012, 1191-1210. - P. Butkovic, H. Schneider and S. Sergeev.
*Recognizing weakly stable matrices*. SIAM J. Control Optim., 50 no. 5, 2012, 3029-3051. - S. Gaubert and S. Sergeev.
*The level set method for the max-plus two-sided eigenproblem*. Discrete Event Dynamical Systems, 23 (2), 2013, 105-134. - P. Butkovic, H. Schneider, S. Sergeev and B.-S. Tam,
*Two cores of a nonnegative matrix*. Linear Algebra and Applications 439 (2013), pp. 1929-1954. - G.L. Litvinov, A.Ya. Rodionov, S.N. Sergeev and A.N. Sobolevskii,
*Universal algorithms for solving the matrix Bellman equations over semirings (PDF)*. Soft Computing 17 (10), 2013, pp. 1767-1785. - V. Nitica and S. Sergeev,
*Tropical convexity over max-min semiring (PDF)*. In: Tropical and Idempotent Mathematics and Applications (G.L. Litvinov and S.N. Sergeev, eds.), vol.616 of Contrmporary Mathematics, AMS, 2014, pp. 241-260. - R.D. Katz, V. Nitica and S. Sergeev.
*Characterization of tropical hemispaces by (P.R)-decompositions*. Linear Algebra and its Applications, 440, 2014, pp. 131-163. - G. Merlet, T. Nowak, H. Schneider and S. Sergeev,
*Generalizations of bounds on the index of convergence to weighted digraph*s. Discrete Applied Mathematics, 178, 2014, pp. 121-134. - G. Merlet, T. Nowak and S. Sergeev,
*Weak CSR expansions and transience bounds in max-plus algebra*. Linear Algebra and its Applications, 461, 2014, pp. 163-199. - B. Benek Gursoy, S. Kirkland, O. Mason and S. Sergeev,
*The Markov chain tree theorem in commutative semirings and the state reduction algorithm in commutative semifields*. Linear Algebra and its Applications, 468, 2015, 184-196. - G.M.Engel, H. Schneider and S. Sergeev.
*On sets of eigenvalues of matrices with prescribed row sums and prescribed graph*. Linear Algebra and its Applications, 455, 2014, pp. 187-209. -
S. Sergeev.

*Extremals of the subeigenvector cone in max algebra: A combinatorial description*. Linear Algebra and its Applications, 479, 2015, pp. 106-117. -
M. Gavalec, Z. Nemcova, S. Sergeev.

*Tropical linear algebra with the Lukasiewicz T-norm*. Fuzzy Sets and Systems, 276, 2015, pp. 131-148. -
J. Plavka, S. Sergeev.

*X-simple image eigencones of tropical matrices*. Linear Algebra and its Applications, 507, 2016, pp. 169-190. - J. Plavka, S. Sergeev.
*Reachability of eigenspaces for interval circulant matrices in max-algebra*. Linear algebra and its Applications, 550, 2016, pp.59-86.