Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

January 7, 2022

Optimal Transport and Enriched Categories IV: Examples of Kan-type Centres

Posted by Simon Willerton

Last time we were thinking about categories enriched over ¯ +\bar{\mathbb{R}}_+, the extended non-negative reals; such enriched categories are sometimes called generalized or Lawvere metric spaces. In the context of optimal transport with cost matrix kk, thought of as a ¯ +\bar{\mathbb{R}}_+-profunctor k:𝒮k\colon \mathcal{S}\rightsquigarrow\mathcal{R} between suppliers and receivers, we were interested in the centre of the ‘Kan-type adjunction’ between enriched functor categories, which is the following:

In this post I want to give some examples of the Kan-type centre in low dimension to try to give a sense of what they look like over ¯ +\bar{\mathbb{R}}_+. Here’s the simplest kind of example we will see.

kan_centre_32.png

Quick Recap

It’s been a while since my last post on this and I don’t want to a big recap but certainly a small recap is in order! I’m interested in transporting goods from a set {S i} i=1 s\{S_i\}_{i=1}^s of suppliers to a set {R j} j=1 r\{R_j\}_{j=1}^r of receivers. (Think of transporting loaves of bread from bakeries to cafés.) We have a supply of σ i\sigma_i units of good at supplier S iS_i and a demand of ρ j\rho_j at receiver R jR_j and the cost of transporting one unit of goods from S iS_i to R jR_j is k ij[0,)k_{ij}\in [0,\infty).

We saw that in the dual problem we want to find prices v=(v 1,,v s)v=(v_1,\dots,v_s) and u=(u 1,,u r)u=(u_1,\dots, u_r) at the suppliers and receivers respectively that maximize the total revenue ju jρ j iv iσ i \sum_j u_j\rho_j -\sum_i v_i\sigma_i subject to the competitivity constraint k iju jv ik_{ij}\ge u_j-v_i for all i,ji,j.

I’ll model this is the language of ¯ +\bar{\mathbb{R}}_+-categories. Recall that an ¯ +\bar{\mathbb{R}}_+-category is a generalization of a metric space: in an ¯ +\bar{\mathbb{R}}_+-category XX we have a ‘hom-object’ X(a,b)[0,]X(a,b)\in [0,\infty] between each pair of objects a,bXa,b\in X. This hom-object should be thought of as a distance which does not have to be finite, nor symmetric, and you can have distinct objects having zero distance between them. The right notion of ‘functor’ here is that of ‘distance non-increasing map’; the term ‘short map’ is used for short.

I model the situation in the following way.

Suppliers: 𝒮\mathcal{S}, a discrete ¯ +\bar{\mathbb{R}}_+-category
Receivers: \mathcal{R}, a discrete ¯ +\bar{\mathbb{R}}_+-category
Transport cost: k:𝒮k\colon \mathcal{S}\rightsquigarrow \mathcal{R}, an ¯ +\bar{\mathbb{R}}_+-profunctor
Prices at suppliers: v:𝒮¯ +v\colon \mathcal{S}\to \bar{\mathbb{R}}_+, an ¯ +\bar{\mathbb{R}}_+-functor
Prices at receivers:  u:𝒮¯ +u\colon \mathcal{S}\to \bar{\mathbb{R}}_+ an ¯ +\bar{\mathbb{R}}_+-functor

Note that I didn’t mention how to model the supply and demand. That is not of immediate interest to us, so I won’t say anything about that now.

We also saw that in finding prices which maximize total revenue we can restrict our attention to ‘tight price plans’, that is pairs of prices (v;u)(v; u) which lie in the centre Z K(k)Z_{\mathrm{K}}(k) of the following Kan-type adjunction.

The Kan centre is the full subcategory of ¯ + 𝒮ׯ + \bar{\mathbb{R}}_+^\mathcal{S}\times \bar{\mathbb{R}}_+^\mathcal{R} consisting of objects (v,u)(v,u) such that kv=uk\circ v = u and v=kuv=k\triangleright u; in the notation of previous posts I would write v^=u\hat{v} =u and v=u˜v=\tilde{u}.

Note that the Kan-type adjunction is not the same as the Isbell-type (*) adjunction I’ve discussed in previous posts on profunctor nuclei and Isbell tight-spans. I will discuss a relationship between them in a future post.

(*) I don’t like using the terms ‘Kan’ and ‘Isbell’ for these adjunctions, I’d much rather use more descriptive adjectives. It anyone has any ideas…

In this post I want to visualize the Kan centre Z K(k)Z_{\mathrm{K}}(k) for you, and as the Kan centre is a subset of ¯ + 𝒮ׯ + ¯ + 𝒮\bar{\mathbb{R}}_+^\mathcal{S}\times \bar{\mathbb{R}}_+^\mathcal{R}\cong \bar{\mathbb{R}}_+^{\mathcal{S}\sqcup\mathcal{R}}, it would be wise to start in a case with a very small number of suppliers and receivers, namely where |𝒮|3\left | \mathcal{S}\sqcup\mathcal{R}\right|\le 3. We will see that we can in fact visualize, in a certain way, higher dimensional cases, but we will start with a slightly silly example — from an optimal transport perspective — to illustrate some basic features.

A first example

Let’s start with two suppliers and one receivers, |𝒮|=2|\mathcal{S}|=2 and ||=1|\mathcal{R}|=1. I will think of these as bakeries and cafés and I’ll pick some simpler numbers than I did in the old café example I used. The numbers on the arrows represent the cost of transporting one loaf of bread. The numbers in circles represent the supply and demand in loaves of bread.

The profunctor in this situation can be represented by the matrix k=(3 2)k=\left(\begin{smallmatrix}3\\2\end{smallmatrix}\right). (I might be regretting my choice of conventions and I might have preferred to have the transpose of this matrix.)

It is clear what the solution to the optimal transport problem is in this case as there’s only one feasible solution, namely both bakeries send all their bread to the one café. But this should be a useful example none-the-less.

We have the adjunction

with

k(v 1,v 2)=(min{3+v 1,2+v 2})k(u 1)=(u 1˙3,u 1˙2). k\circ(v_1, v_2)=(\min\{3+v_1, 2+v_2\}) \qquad k\triangleright(u_1) = (u_1\,\dot{{}-{}}\,3, u_1\,\dot{{}-{}}\,2).

You can check that the centre is

{((λ˙1,λ),(2+λ))λ[0,]}¯ + 2ׯ + 1 \{((\lambda\,\dot{{}-{}}\,1, \lambda), (2+\lambda))\mid \lambda\in [0,\infty]\} \subset \bar{\mathbb{R}}_+^2\times \bar{\mathbb{R}}_+^1

and this (or at least a finite portion of it) can be drawn as follows.

kan_centre_32.png

You can observe that this is the union of two closed line segments, or, as might be more useful, that this is the union of two open line segments (one bounded, one unbounded) and two points. In fact, in general the Kan centre is a cell complex of open, piece-wise affine cells.

Another thing to observe here is that if (v,u)(v,u) is a pair in the Kan centre then vv determines uu and uu determines vv, so we can project onto ¯ + 2\bar{\mathbb{R}}_+^2 or ¯ + 1\bar{\mathbb{R}}_+^1 without losing any information. Here are the projections, I’ve drawn the boundary of the view box that I’ve picked, but the picture should be unbounded.

 

Here they are, drawn in a more standard way.

 

Some generalities

Projecting in this way gives us two views of the Kan centre and will allow us to visualize some higher dimensional examples. You need to bear in mind, however, that neither picture is the ‘true’ centre as this naturally sits in the higher dimensional space. For instance, the total revenue function can be restricted to the tight price plans, i.e. the centre, this is the restriction of a linear function when the centre is considered as a subset of (v,u)(v,u)-space, but it is not the restriction of a linear function when the centre is considered as a subset of vv-space or uu-space. Remember that we are hoping to maximize the total revenue function on the Kan centre.

There’s a very general statement about adjunctions when enriching over commutative quantales like ¯ +\bar{\mathbb{R}}_+. I won’t go into the details, many of which can be found in my Legendre-Fenchel transform paper. Anyway, roughly speaking, for an adjunction LRL\dashv R between ¯ +\bar{\mathbb{R}}_+-categories we have a counit LRidL R\Rightarrow\mathrm{id} and a unit idRL\mathrm{id}\Rightarrow R L, thus we have RLRRR L R\Rightarrow R and RRLRR\Rightarrow R L R (which means 0𝒞(RLR(d),R(d))0\ge \mathcal{C}(R L R(d), R(d)) and 0𝒞(R(d),RLR(d))0\ge \mathcal{C}(R(d), R L R(d)) for all d𝒟d\in \mathcal{D}) and so RRLRR \cong R L R. Similarly LLRLL \cong L R L. We saw that manifested earlier as v˜^˜=v˜\tilde{\hat{\tilde{v}}}= \tilde{v}. This gives us that any monad on an ¯ +\bar{\mathbb{R}}_+-category is idempotent and also the following.

Lemma 1. For an adjunction LRL\dashv R between ¯ +\bar{\mathbb{R}}_+-categories 𝒞\mathcal{C} and 𝒟\mathcal{D} there is the following identification of categories where Im\mathrm{Im} denotes the image of a functor and Fix\mathrm{Fix} denotes the fixed category of an endofunctor.

So in our case this means that the left-hand view or the space of tight price plans on the suppliers can be thought of as the image of the functor kk\triangleright{-}, or as the fixed space of the monad k(k)k\triangleright(k\circ{-}).

Examples

Here are some more examples. In each case I’ll give the profunctor and then pictures of the two views of the Kan-type centre, or, if you prefer, the tight price plans.

I computed these (as cell complexes) using some rather inefficient SageMath code; however, having seen what they look like I now realise there will be better algorithms out there. I’ll maybe say more on this next time.

(2 1 3 5)\begin{pmatrix}2&1\\3&5\end{pmatrix}

 

(2 7 3 5)\begin{pmatrix}2&7\\3&5\end{pmatrix}

 

(4 6 10 5 11 11 8 14)\begin{pmatrix} 4 & 6 \\ 10 & 5 \\ 11 & 11 \\ 8 & 14 \end{pmatrix}

 

In the above example I couldn’t actually show you the picture of the left-hand view as I’m not good at putting 4d objects on the the screen. However in the next example, by the magic of three.js, I can (hopefully!) put some fairly basic 3d objects on the screen which you can navigate and move with your mouse/touchpad/fingers. By clicking on the border you should be able to open models in fullscreen if you desire.

Due to laziness on my part, I’ll only show the one-cells; however, the two-cells and three-cells fill in the obvious holes (or at least I think they are obvious).

(1 4 6 2 7 1 8 7 8)\begin{pmatrix} 1 & 4 & 6 \\ 2 & 7 & 1 \\ 8 & 7 & 8 \end{pmatrix}

Your browser will not allow the embedded object! Your browser will not allow the embedded object!

So there’s some examples to get one thinking.

Next time

I hope that next time I will explain some of the structure of these examples and relate these to the notion of the semi-tropical convex hull. (The tropically aware amongst you might have noticed something convex hully going on.) And later on I would like to compare and contrast these with Isbell-type centres.

Posted at January 7, 2022 1:55 PM UTC

TrackBack URL for this Entry:   https://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/3352

0 Comments & 0 Trackbacks

Post a New Comment