## Solving Linear Programs via Isospectral flows |05 September 2021|
In this post we will look at one of the many remarkable findings by Roger W. Brockett. Consider a Linear Program (LP) parametrized by the compact set and a suitable triple .
As a solution to can always be found to be a vertex of , a smooth method to solve seems somewhat awkward.
We will see that one can construct a so-called isospectral flow that does the job.
Here we will follow Before we continue, we need to establish some differential geometric results. Given the Special Orthogonal group , the tangent space is given by . Note, this is the explicit formulation, which is indeed equivalent to shifting the corresponding Lie Algebra. The easiest way to compute this is to look at the kernel of the map defining the underlying manifold. Now, following Brockett, consider the function defined by for some . This approach is not needed for the full construction, but it allows for more intuition and more computations. To construct the corresponding gradient flow, recall that the (Riemannian) gradient at is defined via for all . Using the explicit tangent space representation, we know that with . Then, see that by using we obtain the gradient via This means that (the minus is missing in the paper) the (a) gradient flow becomes Consider the standard commutator bracket and see that for one obtains from the equation above (typo in the paper) Hence, can be seen as a reparametrization of a gradient flow. It turns out that has a variety of remarkable properties. First of all, see that preserves the eigenvalues of . Also, observe the relation between extremizing and the function defined via . The idea to handle LPs is now that the limiting will relate to putting weight one the correct vertex to get the optimizer, gives you this weight as it will contain the corresponding largest costs. In fact, the matrix can be seen as an element of the set . This set is in fact a -smooth compact manifold as it can be written as the orbit space corresponding to the group action , , one can check that this map satisfies the group properties. Hence, to extremize over , it appears to be appealing to look at Riemannian optimization tools indeed. When doing so, it is convenient to understand the tangent space of . Consider the map defining the manifold , . Then by the construction of , see that yields the relation for any . For the moment, let such that and . First we consider the convergence of . Let have only distinct eigenvalues, then exists and is diagonal. Using the objective from before, consider and see that by using the skew-symmetry one recovers the following This means the cost monotonically increases, but by compactness converges to some point . By construction, this point must satisfy . As has distinct eigenvalues, this can only be true if itself is diagonal (due to the distinct eigenvalues). More can be said about , let be the eigenvalues of , that is, they correspond to the eigenvalues of as defined above. Then as preserves the eigenvalues of (), we must have , for a permutation matrix. This is also tells us there is just a finite number of equilibrium points (finite number of permutations). We will write this sometimes as . Now as is one of those points, when does converge to ? To start this investigation, we look at the linearization of , which at an equilibrium point becomes for . As we work with matrix-valued vector fields, this might seems like a duanting computation. However, at equilibrium points one does not need a connection and can again use the directional derivative approach, in combination with the construction of , to figure out the linearization. The beauty is that from there one can see that is the only asymptotically stable equilibrium point of . Differently put, almost all initial conditions will converge to with the rate captured by spectral gaps in and . If does not have distinct eigenvalues and we do not impose any eigenvalue ordering on , one sees that an asymptotically stable equilibrium point must have the same eigenvalue ordering as . This is the sorting property of the isospectral flow and this is of use for the next and final statement.
Please consider the references for more on the fascinating structure of . |