# Dr Sergey Sergeev

School of Mathematics

Lecturer in Mathematical Optimisation

## Contact details

- Address
- School of Mathematics

Watson Building

University of Birmingham

Edgbaston

Birmingham

B15 2TT

UK

Sergey is Lecturer in Mathematical Optimisation who previously worked as 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, living there until 2008, when he defended a PhD in Mathematics at the Faculty of Mechanics and Mathematics of M.V. Lomonosov Moscow State University. 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 first 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 a Lecturer in Mathematical Optimisation. Currently he is working on an EPSRC funded grant EP/P019676/1 "Tropical Optimisation", being focused on various forms of tropical optimisation such as tropical pseudoquadratic and bilevel optimisation. He 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. He is teaching Non-Linear Programming II, a module for 4th year students and Ph.D students which is mostly on Dynamic Programming and Optimal Control.

In June 2018, Sergey co-organized a one-day conference "Tropical Mathematics and Optimization for Railways" (joint with Prof. Clive Roberts).

## Teaching

- Lectures in Non-Linear Programming II
- Supervising MSci projects in tropical mathematics and optimisation
- Supervising Research Skills and Summer Projects (MSc) in Financial Engineering
- Year 1 and Year 2 tutorials
- Supervising PhD students in Tropical Mathematics

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

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.

## 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*. 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*. 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*. Soft Computing 17 (10), 2013, pp. 1767-1785. - V. Nitica and S. Sergeev,
*Tropical convexity over max-min semiring*. 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.