« Home

Person Eigil Fjeldgren Rischel [eigil-rischel]

Contributions

Reference Metric Equational Theories [mardare-ghani-rischel-2025]

September 17, 2025
Radu Mardare, Neil Ghani, Eigil Fjeldgren Rischel
10.4204/eptcs.428.11

Abstract

September 17, 2025
Radu Mardare, Neil Ghani, Eigil Fjeldgren Rischel

This paper proposes appropriate sound and complete proof systems for algebraic structures over metric spaces by combining the development of Quantitative Equational Theories (QET) with the Enriched Lawvere Theories. We extend QETs to Metric Equational Theories (METs) where operations no longer have finite sets as arities (as in QETs and the general theory of universal algebras), but arities are now drawn from countable metric spaces. This extension is inspired by the theory of Enriched Lawvere Theories, which suggests that the arities of operations should be the lambda-presentable objects of the underlying lambda-accessible category. In this setting, the validity of terms in METs can no longer be guaranteed independently of the validity of equations, as is the case with QET. We solve this problem, and adapt the sound and complete proof system for QETs to these more general METs, taking advantage of the specific structure of metric spaces.

@article{Mardare2025,
  title = {Metric Equational Theories},
  volume = {428},
  ISSN = {2075-2180},
  url = {http://dx.doi.org/10.4204/EPTCS.428.11},
  DOI = {10.4204/eptcs.428.11},
  journal = {Electronic Proceedings in Theoretical Computer Science},
  publisher = {Open Publishing Association},
  author = {Mardare,  Radu and Ghani,  Neil and Rischel,  Eigil},
  year = {2025},
  month = sep,
  pages = {144–160}
}

Reference Convex Duality Made Difficult [rischel-cvxdual-2025]

June 2, 2025
Eigil Fjeldgren Rischel
https://cgi.cse.unsw.edu.au/~eptcs/paper.cgi?ACT2025:28

Convex Duality made Difficult [lcc-001Z]

April 30, 2024
Eigil Fjeldgren Rischel

Introduction

April 30, 2024
Eigil Fjeldgren Rischel

The study of convex functions - in particular, of their optimization (really minimization) is one of the most important fields of applied mathematics. Convexity seems to be one of those incredibly well-chosen hypotheses which is just specific enough to admit a wealth of theorems, just general enough to produce a nontrivial theory (and a large amount of important examples).

Convex optimization, possibly because it has an "analytical" rather than "algebraic" feel, has not been very thoroughly studied by applied category theorists. The one notable exception is Reference [hanks-etal-convex-2024], which studies the decomposition of optimization problems by categorical means. This paper takes a different approach, attempting to define a category with optimization problems as the objects, and to derive theorems about optimization by categorical means.

Convex optimization

April 30, 2024
Eigil Fjeldgren Rischel

Definition Standard form convex optimization problem [lcc-001G]

April 22, 2024
Eigil Fjeldgren Rischel

A convex optimization problem in standard form consists of

A convex function $f_0: \mathbb {R}^k \to \mathbb {R}$
A list of convex functions $f_1, \dots f_n: \mathbb {R}^k \to \mathbb {R}$
A list of affine functions $g_1,\dots g_m: \mathbb {R}^k \to \mathbb {R}$

The problem then is to find

x \in \mathbb {R}^k

which minimizes

f_0(x)

subject to the constraints

f_i(x) \leq 0, g_i(x)=0

Definition Lagrangian of an optimization problem [lcc-002K]

May 17, 2024
Eigil Fjeldgren Rischel

Let $f_0: \mathbb {R}^k \to \mathbb {R}, f_1, \dots f_n, g_1 , \dots g_m$ be a standard-form convex optimization problem, as in Definition [lcc-001G]. Then the Lagrangian of this problem is the function $L: \mathbb {R}^k \times \mathbb {R}^n_+ \times \mathbb {R}^m \to \mathbb {R}$ defined by $L(x;\lambda ,\nu ) = f_0(x) + \sum _i \lambda _i f_i(x) + \sum _i \nu _i g_i(x).$ Recall that $\mathbb {R}_+$ denotes the nonnegative reals.

Observe that $\sup _{\lambda ,\nu } L(x,\lambda ,\nu )$ is $f_0(x)$ if $x$ satisfies the constraints of the problem, and $\infty$ otherwise. Hence we can think of this minimization problem as playing a zero-sum game: we choose $x$ , our adversary chooses $\lambda ,\nu$ , and our loss function is $L$ .

It is natural to ask about the existence of Nash equilibria in this game - observe that the existence of an equilibrium $(x^*,\lambda ^*,\nu ^*)$ means that $\inf _x \sup _{\lambda ,\nu } L(x,\lambda ,\nu ) = \sup _{\lambda ,\nu } \inf _x L(x,\lambda ,\nu ) = L(x^*,\lambda ^*,\nu ^*)$ . This is of great utility in solving the original problem.

The dual problem is the problem of maximizing the function $\inf _x L(x,\lambda ,\nu )$ . This is always a concave problem.

In the world of convex optimization, two problems whose constraints carve out the same subset of $\mathbb {R}^k$ (and where the function to optimize is the same) would be called equivalent. But they can clearly not be regarded as isomorphic, because the choice of constraint functions makes an important difference to the theory of optimization (for example, it can lead to different dual problems). Here we take the viewpoint that the Lagrangian is really the fundamental object in convex optimization - by passing to a suitable category of Lagrangians, we can make the dual problem into an actual self-duality on this category.

Convex spaces

April 30, 2024
Eigil Fjeldgren Rischel

Definition Convex Space [lcc-0020]

April 30, 2024
Eigil Fjeldgren Rischel

The category of convex spaces is the category of algebras for the monad $\Delta : \mathsf {Set} \to \mathsf {Set}$ of discrete finite-support distributions. The morphisms are called $\Delta$ -homomorphisms or homomorphisms of convex spaces.

So as not to multiply notation unnecessarily, we simply denote the category of convex spaces by $\mathsf {Set}^\Delta$ , using the usual notation for the Eilenberg-Moore category.

Definition [lcc-002N]

May 20, 2024
Eigil Fjeldgren Rischel

A function between vector spaces is called affine if it preserves those linear combinations $\sum _i \lambda _i x_i$ where $\sum _i \lambda _i = 1$

Definition [lcc-002M]

May 20, 2024
Eigil Fjeldgren Rischel

Let $X$ be a convex space. A convex function on $X$ is a function $f: X \to \mathbb {R}$ so that $f(\theta x + (1-\theta )x') \leq \theta f(x) + (1-\theta )f(x')$

A concave function is a function so that $-f$ is convex (in other words, $f$ satisfies the opposite inequality).

The term "convex function" in this sense clashes with the usual practice of naming structure-preserving functions after the structure they preserve (since convex functions do not preserve the convex structure). Unfortunately this usage is far too established to alter. (Convex functions are called convex because they are exactly those functions where the area above their graph is a convex subset of $X \times \mathbb {R}$ . Although there appears to be no particular reason why the terms convex and concave should not be interchanged, other than convention).

Jensen's Inequality [lcc-002R]

May 19, 2024
Eigil Fjeldgren Rischel

The inequality $f(\theta x + (1-\theta )x') \leq \theta f(x) + (1-\theta )f(x'),$ which holds whenever $f$ is convex, is called Jensen's inequality. Sometimes this name is used for a stronger version of this inequality, like the claim that $f(\mathbb {E} X) \leq \mathbb {E} f(X)$ if $X$ is a random variable valued in the domain of $f$ . These generally follow just from convexity of $f$ .

[lcc-002Q]

May 19, 2024
Eigil Fjeldgren Rischel

There is an natural way to extend the convex structure of $\mathbb {R}$ to both $\lsqb -\infty , \infty \rpar$ and $\lpar -\infty , \infty \rsqb$ , by the convention that any nontrivial convex combination involving an infinity is equal to that infinity. This also gives the adjectives convex and concave a meaning when applied to functions $X \to \lpar -\infty , \infty \rsqb$ . For example, a function $f: X \to \lpar -\infty , \infty \rsqb$ is convex if and only if the subset where it's finite is a convex subset of $X$ , and it's a convex function in the ordinary sense on this set.

This doesn't work for the extended real line $\eRR = \lsqb -\infty , \infty \rsqb$ , since there is no sensible interpretation of $\theta \cdot -\infty + (1-\theta )\infty$ . We will inescapably meet some functions which take value in the full extended reals, but where we still wish to speak of their convexity (or concavity).

Hence we adopt the convention that a function $f: X \to \eRR$ is convex if it obeys Jensen's inequality whenever it makes sense, i.e whenever we do not have $f(x) = -\infty , f(x') = \infty$ or vice versa.

Proposition [lcc-002O]

May 20, 2024
Eigil Fjeldgren Rischel

A function between vector spaces is affine if and only if it is a $\Delta$ -homomorphism.

Proof

May 20, 2024
Eigil Fjeldgren Rischel

It's clear that an affine function is a $\Delta$ -homomorphism. Suppose $f: X \to Y$ is a $\Delta$ -homomorphism. Note it suffices to prove $f$ preserves binary affine combinations $\theta x + (1-\theta )x'$ (for $\theta$ not necessarily in $[0,1]$ ). If $\theta \in [0,1]$ , we are done by assumption. Otherwise suppose $\theta > 1$ (if not, replace it by $1-\theta$ by symmetry). Then $x = (1/\theta )(\theta x + (1-\theta )x') + (1 - 1/\theta )x'$ This is a convex combination, so $f(x) = (1/\theta )f(\theta x + (1-\theta )x') + (1-1/\theta )f(x')$ Rearranging, we find $\theta f(x) + (1-\theta )f(x') = f(\theta x + (1-\theta ')x)$ as desired.

Justified by Proposition [lcc-002O], we will appropriate the term affine to refer to $\Delta$ -homomorphisms, even between convex spaces which are not vector spaces. There is generally no chance of confusion, but it's worth emphasizing that the use of this term does not entail that the domain is closed under arbitrary affine combinations, for example.

Convex spaces admit both a Cartesian product (given by the product of the underlying sets equipped with pointwise operations) and a tensor product, which (co)represents "bihomomorphisms". This is analogous to the situation for vector spaces. Unlike vector spaces, however, since all constant maps are homomorphisms, the projections $X \times Y \to X,Y$ are bihomomorphisms, which induces a map $X \otimes Y \to X \times Y$ . Thus homomorphisms $X \times Y \to Z$ are a subset of bihomomorphisms.

Since we are generally dealing with convex or concave functions, which can't freely be extended to the tensor product, we will work with the Cartesian product in this paper. But it's very possible that most of our constructions would work also with the tensor product, and maybe there is some situation where the extra generality is necessary.

Definition Simplex [lcc-002S]

May 21, 2024
Eigil Fjeldgren Rischel

The free convex space on a finite set $\{0, \dots n\}$ of $n+1$ elements is called the $n$ -simplex and denoted $\Delta ^n$ (the reason for the apparent mismatch of numbering is that the $n$ -simplex is $n$ -dimensional). Note that an element of $\Delta ^n$ is a tuple $(s_i)_{i=0,\dots , n}$ so that $\sum _i s_i = 1$ and $s_i \geq 0$ . In particular, $\Delta ^1 \cong [0,1]$ .

Definition Topological convex space [lcc-002U]

May 21, 2024
Eigil Fjeldgren Rischel

A topological convex space is a convex space $X$ equipped with a topology so that any affine map $\Delta ^n \to X$ is continuous (when $\Delta ^n \subseteq \mathbb {R}^{n+1}$ is given the subspace topology).

The Category of Minmax problems

April 30, 2024
Eigil Fjeldgren Rischel

Definition Minmax problem [lcc-001C]

April 22, 2024
Eigil Fjeldgren Rischel

A minmax problem is a triple $(X,Y,L),$ where $X,Y$ are convex spaces (that is, algebras for the discrete distribution monad---more topological assumptions may be necessary here), and $L: X \times Y \to \mathbb {R}$ is a function which is

Pointwise convex in $X$ ---for each $y$ , given $x_1,x_2 \in X, \theta \in [0,1]$ , $L(\theta x_1 + (1-\theta )x-2,y) \leq \theta L(x_1,y) + (1-\theta )L(x_2,y)$
Pointwise concave in $Y$ ---for each $x$ , given $y_1,y_2 \in Y, \theta \in [0,1]$ , $L(x,\theta y_1 + (1-\theta )y_2) \geq \theta L(x,y_1) + (1-\theta )L(x,y_2)$

A morphism of minmax problems $(X,Y,L) \to (X',Y',L')$ is a pair of functions $\phi ^+: X \to X'$ and $\phi ^-: Y' \to Y$ so that $L(x, \phi ^-(y')) \geq L'(\phi (x),y')$

We will see that various constructions on this category, which are natural and well-behaved from the point of view of category theory, capture relevant constructions from the theory of convex optimization.

$\mathsf {Minmax}$ is bifibred over $\mathsf {Set}^\Delta \times \mathsf {Set}^{\Delta ,\mathrm {op}}$ , and the Cartesian and coCartesian lifts capture the operations of minimizing over the primal variables or maximizing over the dual variables
The property of strong duality amounts to the claim that a particular diagram has the local Beck-Chevalley property
Relatedly, the existence of a Nash equilibrium for the game corresponding to $L$ amounts to the existence of a certain morphism. The fact that this implies strong duality can be derived by purely categorical means.

Proposition [lcc-002H]

May 10, 2024
Eigil Fjeldgren Rischel

Let $(X,A,L)$ be a minmax problem. Suppose $A$ is a convex subspace of a vector space $V$ , and $L(x,-): A \to \mathbb {R}$ is affine for each $x$ . Then there exists functions $f: X \to \mathbb {R}, g: X \to V^*$ , so that $L(x,a) = f(x)+\langle g(x),a \rangle$ .

Observe that minmax problems affine in $A$ are thus very similar to standard-form convex optimization problems, the main difference being that the set of allowed points in $A$ may be constrained in some other way than by requiring certain coordinates to be nonnegative.

On the other hand, if $A$ is thus constrained, the proposition doesn't actually imply that $f,g$ are convex! The easiest way to see this is by considering $A = \{a\}$ for some nonzero $a$ . Then we have $L(x,a) = f(x) + ag(x),$ , and clearly we can choose this decomposition in such a way that these functions are not convex.

However, if $A \subset \mathbb {R}^m$ contains the positive cone $\mathbb {R}^m_+,$ for example, we do have both $f$ and all the coordinates of $g$ convex.

Definition Primal and dual optimization problems [lcc-001D]

April 22, 2024
Eigil Fjeldgren Rischel

Let $L: X \times Y \to \mathbb {R}$ be a minimax problem. The primal optimization problem associated to $L$ is the function $L^+(-) = \sup _y L(-,y): X \to \mathbb {R}$ (the problem being to minimize this function).

The dual optimization problem is the function $L^-(-) = \inf _x L(x,-): Y \to \mathbb {R}$

Definition Dual minmax problem [lcc-001J]

April 23, 2024
Eigil Fjeldgren Rischel

Let $L = (X,Y,L)$ be a minmax problem. Then let $L^*$ denote the dual problem given by $(Y,X,L^*(y,x) = -L(x,y))$ .

If $\phi = (\phi ^+,\phi ^-) : L \to L'$ is a morphism of minmax problems, then $\phi ^* = (\phi ^-,\phi ^+): L'^* \to L^*$ is again a morphism in the other direction. This assignment makes $(-)^*$ into a self-inverse functor on the category of minmax problems

We will often utilize this duality to abbreviate proofs, proving something, for example, for the forwards direction and arguing "by duality" that it holds for the backwards direction as well.

Definition Backwards and forwards morphisms [lcc-0027]

May 1, 2024
Eigil Fjeldgren Rischel

Let a morphism $\phi = (\phi ^+,\phi ^-)$ in $\mathsf {Set}^\Delta \times \mathsf {Set}^{\Delta ,\mathrm {op}}$ be called forwards if $\phi ^-$ is an isomorphism, and backwards if $\phi ^+$ is an isomorphism. Let $F$ denote the set of forwards morphisms, $B$ the set of backwards. Then clearly $(F,B)$ form an orthogonal factorization system - in fact, both $(F,B)$ and $(B,F)$ do.

Note that $F$ consists exactly of the local equivalences for the inclusion of $* \times \mathsf {Set}^{\Delta ,\mathrm {op}}$ , so that the localization of $(X,A)$ can be formed as the terminal forwards map from it, which is clearly $(X,A) \to (*,A)$ (of course, this is not surprising).

We will say a morphism in $\mathsf {Minmax}$ is forwards, respectively backwards, if it is so considered as a morphism in $\mathsf {Set}^\Delta \times \mathsf {Set}^{\Delta ,\mathrm {op}}$ , and reuse the notation $F,B$ for these subclasses of morphism.

Lemma [lcc-002A]

May 7, 2024
Eigil Fjeldgren Rischel

Let $X,Y$ be convex spaces and let $A \subset X \times Y$ be a convex subspace. Let $f: A \to \mathbb {R}$ be a convex function. Then $x \mapsto \inf _{y: (x,y) \in A} f(x,y)$ is again convex.

Proof

May 7, 2024
Eigil Fjeldgren Rischel

Let $\theta \in [0,1],x,x' \in X$ be given, and consider:

inf_{y: (\theta x + (1-\theta )x',y) \in A}f(\theta x + (1-\theta x'),y).

Since if $(x,y), (x',y') \in A$ then $(\theta x + (1-\theta )x',\theta y + (1-\theta )y') \in A$ , we have that this is less than: $\leq \inf _{y,y': (x,y),(x',y')\in A} f(\theta x + (1-\theta )x', \theta y + (1-\theta ) y'),$ because in the latter we are taking the infimum over a smaller set of $f$ 's

Applying convexity, we get $\leq \inf _{y,y': (x,y),(x,y') \in A} \theta f(x,y) + (1-\theta )f(x',y')$ $\leq \theta \inf _{y: (x,y) \in A}f(x,y) + (1-\theta )\inf _{y': (x',y')\in A} f(x',y')$ This is precisely the desired inequality.

Proposition [lcc-0023]

April 30, 2024
Eigil Fjeldgren Rischel

The forgetful functor $\mathsf {Minmax} \to \mathsf {Set}^\Delta \times \mathsf {Set}^{\Delta ,\mathrm {op}}$ is a bifibration. Moreover, we have the following description of the (co)Cartesian morphisms over backwards and forwards maps.

A forwards morphism $(\phi ,1_A): (X,A,L) \to (Y,A,L')$ is Cartesian if and only if $L(x,a) = L'(\phi (x),a)$ for all $x,a$
A forwards morphism $(\phi ,1_A): (X,A,L) \to (Y,A,L')$ is coCartesian if and only if $L'(y,a) = \inf _{\phi (x) = y} L(x,a)$
A backwards morphism $(1_X,\phi ): (X,A,L) \to (X,B,L')$ is Cartesian if and only if $L(x,a) = \inf _{\phi (b)=a} L'(x,b)$
A backwards morphism $(1_X,\phi ): (X,A,L) \to (X,B,L')$ is coCartesian if and only if $L'(x,b) = L(x,\phi (b))$

Proof

April 30, 2024
Eigil Fjeldgren Rischel

Note that it suffices to provide Cartesian and coCartesian lifts for backwards and forwards morphisms (Definition [lcc-0027]), since such lifts compose. Hence it suffices to verify that the given descriptions are correct, since clearly they suffice to compute a (co)Cartesian lift over any such morphism.

Note also that, since the forgetful functor is faithful, to verify a morphism $\phi$ is (co)Cartesian, it suffices to prove that any factorization in the base lifts - uniqueness is automatic.

Thus let $\phi = (\phi ,1_A): (X,A,L) \to (Y,A,L')$ be so that $L(x,a) = L'(\phi (x),a)$ . Note that composition of a $\Delta$ -homomorphism with a convex function is again convex, so this is indeed an object of $\mathsf {Minmax}$

Now let $\psi = (\psi ^-,\psi ^+): (Z,B,K) \to (Y,A,L')$ be some morphism so that we have the factorization $\psi = \phi \psi '$ in $\mathsf {Set}^\Delta \times \mathsf {Set}^{\Delta ,\mathrm {op}}$ . The goal is now to prove $\psi ' : (Z,B,K) \to (X,A,L)$ is a homomorphism. This is the inequality $K(z,(\psi ')^-(a)) \geq L((\psi ')^+(z),a) = L'((\phi \psi ')^+(z),a),$ which holds by assumption

Let $\phi$ be as above, but suppose $L'(y,a) = \inf {\phi (x)=y}L(x,a)$ . First, observe that by https://erischel.com/lcc-002A/, this function is in fact convex in $y$ as desired.

Let $\psi : (X,A,L) \to (Z,B,K)$ be given, and now suppose we have a factorization $\psi = \psi '\phi$ in the base. We must prove that $L'(y,(\psi ')^-(b)) \geq K((\psi ')^+(y),b),$ but since $L'(y,(\psi ')^-(b)) = \inf _{\phi (x)=y}L(x,(\psi ')^-(b)),$ this amounts to the equation $L(x,(\psi ')^-(b)) \geq K((\psi ')^+\phi (x),b),$ which is again true by assumption.

Now the case for backwards morphisms simply follows by duality.

What's "really" going on here is that $\mathsf {Minmax}$ is a two-sided fibration, the result of taking the functor $\mathsf {Set}^{\Delta ,\mathrm {op}} \times \mathsf {Set}^{\Delta ,\mathrm {op}} \to \mathsf {Cat}$ carrying a pair $X,Y$ to the poset of minmax problems $L: X \times Y \to \mathbb {R}$ (in the opposite order), with morphisms acting by precomposition, and applying the Grothendieck construction "contravariantly in the first variable and covariantly in the second variable". (And then observing that the precomposition action has left/right adjoints given by $\inf$ / $\sup$ , to make this into a bifibration). But the theory of two-sided fibrations is quite complicated in general, and we will not go into it here.

Note also that this functor is quite close to displaying $\mathsf {Minmax}$ as topological. If we remove the restriction that minmax problems be convex/concave, we can construct the universal lifts required using a similar supremum formula. The problem is that the supremum of a general set of concave functions is not automatically concave (however, the supremum taken over a convex set, in a suitable sense, is).

Definition $\Conv$ and $\Conc$ [lcc-001R]

April 25, 2024
Eigil Fjeldgren Rischel

Let $\mathsf {Conv}$ be the category where objects are pairs $(X,f: X \to \mathbb {R})$ consisting of a convex space and a convex function, and where morphisms $\phi : (X,f) \to (Y,g)$ are affine maps so that $g(\phi (x)) \leq f(x)$ .

Let $\mathsf {Conc}$ be the category where objects are pairs $(X,f: X \to \mathbb {R})$ consisting of a convex space and a concave function, and where morphisms $\phi : (X,f) \to (Y,g)$ are affine maps so that $g(\phi (x)) \geq f(x)$ .

Proposition [lcc-001S]

April 25, 2024
Eigil Fjeldgren Rischel

The assignment $(X,Y,L) \mapsto (X,L^+),$ $(\phi ^+,\phi ^-): L \to L' \mapsto \phi ^+$ defines a functor $(-)^+: \mathsf {Minmax} \to \mathsf {Conv}$

Similarly, $(-)^-$ defines a functor $\mathsf {Minmax} \to \mathsf {Conc}^\mathrm {op}$ . (The reason for this idiosyncratic way of writing a contravariant functor will become apparent in a minute)

The assignment $(X,f) \mapsto (X,-f)$ defines a functor (identity on morphisms) $\mathsf {Conc} \to \mathsf {Conv}$ , and vice versa. Then $L^- = -(L^*)^+$

The assignment $(X,f) \mapsto (X,*, f)$ defines a fully faithful functor $\mathsf {Conv} \to \mathsf {Minmax}$ , whose essential image consists of those tuples $(X,Y,L)$ where $Y$ is singleton. Analogously, $(Y,f) \mapsto (*,Y,f)$ defines a fully faithful functor $\mathsf {Conc}^\mathrm {op} \to \mathsf {Minmax}$

We will abuse notation and identify $\mathsf {Conv}$ and $\mathsf {Conc}$ with their images under these inclusions - thus, for example, $L^+$ will be regarded as an object of $\mathsf {Minmax}$ .

$(-)^+$ is right adjoint to the inclusion of $\mathsf {Conv}$ , and $(-)^-$ (viewed as a functor $\mathsf {Minmax} \to \mathsf {Conc}^\mathrm {op}$ ) is left adjoint to the inclusion of $\mathsf {Conc}^\mathrm {op}$

Using these identifications, we have $(-)^- = (((-)^*)^+)^*$

Note that if $\phi = (\phi ^+,\phi ^-): L \to L'$ is a morphism of $\mathsf {Minmax}$ , the two meanings of the notation $\phi ^+$ agree, and the same is true of $\phi ^-$ .

Note also that the reflexive subcategory $\mathsf {Conc}^\mathrm {op} \subseteq \mathsf {Minmax}$ is the local subcategory with respect to the forwards morphisms - a morphism is forward if and only if $\phi ^-$ is an isomorphism (by definition), and the unit $L \to L^-$ is the terminal forwards morphism with domain $L$ . A dual statement holds for $\mathsf {Conv} \subseteq \mathsf {Minmax}$ (it is the colocalization with respect to the class of backwards morphisms).

Definition Monoidal structure on minmax problems [lcc-001N]

April 23, 2024
Eigil Fjeldgren Rischel

There is a monoidal structure on minmax problems, given by $(L \otimes L') = (X \otimes X', Y \otimes Y', (x,x',y,y') \mapsto L(x,y) + L(x',y')).$ The unit here is $(*,*,0)$ .

A state is a point $x_0$ so that $L(x_0,y) \leq 0$ for all $y$ . More interesting is asking for a state of $L \otimes L^*$ . This is a pair $x \in X, y \in Y$ so that the inequality $L(x,y') \leq L(x',y)$ holds for all $y',x'$

Note that $\sup _{y'} L(x,y') \geq \inf _x L(x',y)$ for all $x,y$ , this is the minmax inequality (or "weak duality").

Thus a choice of $x,y$ giving a state gives equality in that inequation---it is a solution of the minmax game. In other words, $L \otimes L^*$ has a state if and only if strong duality holds for $L$ , and the state is given by an optimal and dual optimal pair in that case.

(By duality, and since $(L \otimes L^*)^* \cong L \otimes L^*$ , such an object has a state if and only if it has a costate)

Proposition [lcc-002D]

May 8, 2024
Eigil Fjeldgren Rischel

The forgetful functor $\mathsf {Minmax} \to \mathsf {Set}^\Delta \times \mathsf {Set}^{\Delta ,\mathrm {op}}$ is a monoidal fibration, in the sense of Reference [shulman-monfibs], (see also Reference [moeller-vasilakopoulou]). It is also a monoidal opfibration - in other words, both the classes of Cartesian and coCartesian maps are stable under tensor product.

In the case of a Cartesian base, a monoidal fibration (like the one we have here) is equivalent to a fibration with a monoidal structure on each fiber, compatible with the reindexing in a certain way. Our base is not Cartesian, but does seem to come from a monoidal structure on each fiber, given by addition of $L$ s. The point is that, given $(X,A,L)$ , there is a canonical way to obtain an $L$ on $(X\times Y, A \times B)$ , given by using a Cartesian lift of $X \times Y \to X$ and a coCartesian lift of $A \times B \to A$ . This suggests there should be a useful theory of monoidal two-sided fibrations, but this notion does not appear to have been studied before.

Proposition [lcc-002P]

May 19, 2024
Eigil Fjeldgren Rischel

The localization (resp. colocalization) $\mathsf {Conc}^\mathrm {op} \hookrightarrow \mathsf {Minmax}$ ( $\mathsf {Conv} \hookrightarrow \mathsf {Minmax}$ ) is monoidal, in the sense that the class local equivalences is stable under tensor products. The thus induced monoidal structure on $\mathsf {Conc}^\mathrm {op}$ is given by $(X,f) \otimes (Y,g) = (X \times Y, (x,y) \mapsto f(x) + g(y))$ (and the same for $\mathsf {Conv}$ ). In particular the (co)localization functor is strong monoidal.

Strong duality

April 30, 2024
Eigil Fjeldgren Rischel

Proposition weak duality [lcc-001W]

April 26, 2024
Eigil Fjeldgren Rischel

Let $L$ be a minmax problem. Then $\inf _x \sup _y L(x,y) = (L^+)^- \geq (L^-)^+ = \sup _x \inf _y L(x,y),$ where we abuse notation by identifying a minmax problem $*,*, r$ with the number $r(*,*)$

Proof

April 26, 2024
Eigil Fjeldgren Rischel

The equations are clearly true by definition. Note that the inequality is equivalent to the existence of a morphism $(L^+)^- \to (L^-)^+$

We have canonical morphisms $L^+ \to L \to L^-$ Since $L^+$ is a right adjoint to the inclusion of $\mathsf {Conv}$ , the above composite induces a map $L^+ \to (L^-)^+$

Since $(-)^-$ is a left adjoint to the inclusion of $\mathsf {Conc}^\mathrm {op}$ , that map induces a map $(L^+)^- \to (L^-)^+,$ as desired.

Definition Strong duality [lcc-002F]

May 9, 2024
Eigil Fjeldgren Rischel

Let $L = (X,A,L)$ be a minmax problem. By Proposition [lcc-001W], there is a morphism $(L^+)^- \to (L^-)^+$ . We say $L$ satisfies strong duality if it is an isomorphism. (Note that this is really just an inequality of real numbers, which must be an equality).

Proposition [lcc-001X]

April 26, 2024
Eigil Fjeldgren Rischel

Let $L$ be a minmax problem. Suppose there exists $\phi : I \to L \otimes L^*$ . Then strong duality holds, i.e $(L^+)^- \cong (L^-)^+$

$((\phi )^+)^-$ gives a morphism $I = (I^+)^- \to ((L \otimes L^*)^+)^- \cong (L^+)^- \otimes ((L^*)^+)^- \cong (L^+)^- \otimes ((L^-)^+)^*$ Here we use the isomorphisms $(L^+)^* = (L^*)^-$ and vice versa, as well as strong monoidality of $(-)^-$ and $(-)^+$ . The existence of that morphism means that $(L^+)^- \leq (L^-)^+,$ which is the other direction of the morphism we wanted.

If a minmax problem is a zero-sum game, a point $I \to L \otimes L^*$ is a choice of Nash equilibrium for this game.

Proposition [lcc-0029]

May 6, 2024
Eigil Fjeldgren Rischel

Let $(X,Y,L)$ be a minmax problem. Then there is a canonical commutative diagram

in

\mathsf {Set}^\Delta \times \mathsf {Set}^{\Delta ,\mathrm {op}},

which is a pullback.

L

obeys strong duality if and only if this square has the local Beck-Chevalley condition for

L

, in the sense that the canonical map

\pi _{X,!}\pi _A^*L \to \pi _A^*\pi _{X,!}L

is an isomorphism.

Proof

May 6, 2024
Eigil Fjeldgren Rischel

Recall that

\pi _{X,!}(L) = L^-, \pi _Y^*(L) = L^+

. Hence the claim is just that

\inf _x \sup _a L(x,a) = (L^+)^- = (L^-)^+ = \sup _a\inf _x L(x,a),

which is precisely strong duality.

(For more on the Beck-Chevalley condition, see Reference [pavlovic-descent-beck-chevalley-1991] or nlab: Beck-Chevalley Condition)

Proposition Slater's Constraint Qualification [lcc-002L]

May 18, 2024
Eigil Fjeldgren Rischel

Consider an optimization problem in standard form:

Minimize $f_0(x), x \in \mathbb {R}^k$
Subject to $f_1(x), \dots , f_n(x) \leq 0$
And $g_1(x), \dots , g_m(x) = 0$
With each $f_i$ convex and each $g_i$ affine

Now assume that

l

is such that

f_1, \dots , f_l

are all affine (possibly

l=0

, and none of the

f_i

are affine), and suppose there exists

x_0 \in \mathbb {R}^k

so that

f_i(x) < 0

for all

i > l

, and

f_i(x) \leq 0

for all other

i

,

g_i(x) = 0

for all

i

. Then strong duality holds for this optimization problem, and the dual optimal value is attained.

Note: This is usually stated for a function defined on an arbitrary convex subset of $\mathbb {R}^k$ . In this case we must further ask that $x_0$ is in the relative interior of this domain.

Proof

May 18, 2024
Eigil Fjeldgren Rischel

(Proof adapted from )

For simplicity, we will assume $l = 0$ , i.e we will not assume any of the $f_i$ are affine, and $f_u(x_0) \leq 0$ for all $i \geq 1$ . (This is the standard form of Slater's constraint qualification).

Let $A, b$ be a matrix and vector so that $(g_i(x)) = Ax - b$ . Then assume without loss of generality that $A$ has full rank. (Suppose $g_j$ is in the span of the other $g_i$ s. Then if the affine constraints are feasible at all, the equation corresponding to $g_j$ must be a consequence of the others. Hence we can delete $g_j$ without altering the primal optimal value, and given a dual optimal value for the problem with $g_j$ deleted, just set $\nu _j = 0$ .)

Let $\mathcal {A} = \{(u,v,t) \mid x \in \mathbb {R}^k, u_i \geq f_i(x), v_i = g_i(x), t \geq f_0(x)\}$ Observe that the optimal value is $p^* = \inf _{(0,0,t) \in \mathcal {A}} t$ . Let $\mathcal {B} = \{(0,0,t) \mid s \leq p^*\}$ . It's not hard to see that these sets are disjoint and convex, and hence there exists a hyperplane separating them. In other words, there exists $\tilde {\lambda },\tilde {\nu },\tilde {\mu },\alpha$ (not all $0$ ) so that $(u,v,t) \in \mathcal {A} \Rightarrow \langle \tilde {\lambda },u \rangle + \langle \tilde {\nu },v \rangle + \mu t \geq \alpha$ $(u,v,t) \in \mathcal {B} \Rightarrow \langle \tilde {\lambda },u \rangle + \langle \tilde {\nu },v \rangle + \mu t \leq \alpha$ By the first inequality, we must have $\tilde {\lambda } \geq 0$ (or the right-hand side would be unbounded below on $\mathcal {A}$ , which is impossible). Similarly we have $\mu \geq 0$ . The latter of the two statements is equivalent to the statement that $\mu t \leq \alpha$ when $t \leq p^*$ , which simply means $\mu p^* \leq \alpha$ . Combining this with the first statement, we get for all $x,$ $\sum _i \tilde {\lambda }_i f_i(x) + \sum _i \tilde {nu}_i g_i(x) + \mu f_0(x) \geq \alpha \geq \mu p^*.$

First assume $\mu \neq 0$ . Then we can divide out and get $L(x, \tilde {\lambda }/\mu , \tilde {\nu }/\mu ) \geq p^*$ , which proves that $(\tilde {\lambda }/\mu , \tilde {\nu }/\mu )$ is a dual optimal value and that strong duality holds.

If $\mu =0$ , we have for all $x$ $\sum _i \tilde {\lambda }_i f_i(x) + \sum _i \tilde {nu}_i g_i(x) \geq 0$

Inserting $x_0$ , we find $\sum _i \tilde {\lambda }_i f_i(x_0) \geq 0,$ and since $f_i(x_0) = 0,$ we must have $\tilde {\lambda } = 0$ . This then implies $\sum _i \tilde {\nu }_i g_i(x) \geq 0 = \langle \tilde {nu},Ax - b \rangle$ for all $x$ . But since this is an affine function, this can only be true if it's constantly zero. Since $\tilde {\nu }$ is nonzero and $A$ has full rank, this is impossible.

Theorem Minimax theorem [lcc-001E]

April 22, 2024
Eigil Fjeldgren Rischel

Let $(L,X,A) \in \mathsf {Minmax}$ . If $X,A$ are both convex, compact subspaces of finite-dimensional vector spaces, and $L$ is continuous, then strong duality holds for $L$ , and moreover an equilibrium $I \to L \otimes L^*$ exists.

This theorem can be derived from the Kakutani fixpoint theorem in a very similar way to the usual proof of Nash's theorem about general, non-zerosum games - although note that it is not a special case, since $X$ and $A$ may not be simplices, and the payoff function here is merely convex, not necessarily affine as it is for a game-theoretic game.

However, we will give a different proof, which uses the structure of $\mathsf {Minmax}$ in a more direct way. Essentially, we will use compactness to reduce to the case of simplexes, then use an inductive argument to reduce to the case where $X = A = \Delta ^1 = [0,1],$ which can be shown by a direct topological argument. The inductive step is a fiber sequence argument, where we use the characterization of strong duality in terms of the Beck-Chevalley property, Proposition [lcc-0029].

Definition Solvable pair [lcc-002T]

May 21, 2024
Eigil Fjeldgren Rischel

Let $X,A$ be topological convex spaces. We say the pair $(X,A)$ is a solvable pair if, for any continuous minmax problem $L: X \times A \to \mathbb {R}$ , strong duality holds.

Proposition [lcc-002V]

May 21, 2024
Eigil Fjeldgren Rischel

The pair $([0,1],[0,1])$ (in other words, $(\Delta ^1,\Delta ^1)$ ) is solvable.

Proof

May 21, 2024
Eigil Fjeldgren Rischel

Let $L: [0,1] \times [0,1] \to \mathbb {R}$ be a continuous minmax problem. Suppose strong duality does not hold. Then by adding a constant to $L$ , we can arrange that $\sup _\theta \inf _s L(s,\theta ) < 0 < \inf _s \sup _\theta L(s,\theta ).$

Consider the set $P = \{(s,\theta ) \mid L(s,\theta ) > 0\}$ . Since we must have $\sup _\theta L(s,\theta ) > 0$ for each $s$ , the first projection $P \to [0,1]$ must be surjective. Since each fiber is convex, and hence connected, and the projection $[0,1] \times [0,1] \to [0,1]$ is open, $P$ is connected. As an open connected subset of a convex space, it is path connected. Hence there exists some path $\gamma (t) \in P$ where $\gamma (0) = (0,\theta _0)$ and $\gamma (1) = (1,\theta _1)$ . In other words (picturing the square with the first coordinate horizontal), there exists a path from the left to the right side of the cube so that $L(\gamma (t)) > 0$ everywhere on the path. Dually, there also exists a path from top to bottom so that $L$ is strictly negative everywhere on that path. But they must intersect somewhere, and this is a contradiction. Hence $L$ must have a state or a costate, finishing the proof.

Proposition [lcc-002W]

May 21, 2024
Eigil Fjeldgren Rischel

Let $E \to B$ be a continuous, affine map between topological convex spaces. Let $A$ be another topological convex space, and suppose

$(B,A)$ is solvable.
For every $b \in B$ , $(E_b,A)$ is solvable, where $E_b \subseteq E$ is the fiber.

Then also

(E,A)

is solvable.

Proof

May 21, 2024
Eigil Fjeldgren Rischel

Recall that $(E,A)$ being solvable means the following square has the Beck-Chevalley condition for continuous $L$ :

Now we can factor this as follows:

Note that the right-hand square here has the Beck-Chevalley condition by assumption. So it suffices to show the left-hand square does. For a given $L$ , this means showing that these two functions on $B$ are the same $b \mapsto \inf _{e \mapsto b} \sup _a L(e,a)$ $b \mapsto \sup _a \inf _{e \mapsto b} L(e,a)$ But this equation, for some given $b$ , is exactly strong duality in the restriction of $L$ to $(E_b,A)$ , which must hold because this is a solvable pair by assumption.

Corollary

May 21, 2024
Eigil Fjeldgren Rischel

If $(X,[0,1])$ is solvable, so is $(X,\Delta ^n)$ for each $n$ , because the map $\Delta ^n \to [0,1]$ which picks out the first coordinate has fibers isomorphic to $\Delta ^{n-1},$ so we can proceed by induction (the case $n=0$ being trivial.)

Lemma [lcc-002X]

May 21, 2024
Eigil Fjeldgren Rischel

Let $X$ be a compact topological convex space. Suppose $(X,\Delta ^n)$ is solvable for all $n$ . Then $(X,A)$ is solvable for all topological convex spaces $A$ .

Proof

May 21, 2024
Eigil Fjeldgren Rischel

Suppose for contradiction

L: X \times A \to \mathbb {R}

does not have strong duality, and assume without loss of generality that

\sup _a \inf _x L(x,a) < 0 < \inf _x \sup _a L(x,a)

. For each

a \in A

let

X_a

consist of those

x \in X

so that

L(x,a) \leq 0

. Given some finite family

a_0, \dots a_n,

consider the induced map

a: \Delta ^n \to A

and apply solvability to the problem

(a_!L,X,\Delta ^n)

- this implies in particular that

\inf _x \sup _i L(x,a_i) \leq 0

. This means the family

X_a

has the finite intersection property, so by compactness it has nonempty intersection. But then an element

x^*

of the intersection must satisfy

\sup _a L(x^*,a) \leq 0,

which is a contradiction.

Corollary [lcc-002Y]

May 21, 2024
Eigil Fjeldgren Rischel

If $X$ is compact, $(X,A)$ is solvable for any $A$ .

Proof

May 21, 2024
Eigil Fjeldgren Rischel

By Proposition [lcc-002W] and its corollary, applied to Proposition [lcc-002V], we have

([0,1],\Delta ^n)

solvable for all

n

. Since

[0,1]

is compact, this means

([0,1],A)

is solvable for all

A

, by Lemma [lcc-002X]. Now by duality we have

(X,[0,1])

solvable for all

X,

which means

(X,\Delta ^n)

is solvable, and by using Lemma [lcc-002X] again, we're done.

April 30, 2024
Eigil Fjeldgren Rischel

By Corollary [lcc-002Y], the pair $(X,A)$ is solvable, and strong duality holds. Since $X,A$ are both compact, there must exist $x^*,a^*$ attaining the infimum $\inf _x \sup _a L(x,a)$ and the supremum $\sup _a \inf _x L(x,a)$ . These form an equilibrium.

It is interesting to note the use of compactness here. Recall that topological compactness is closely connected with the property, also called compactness, of $\operatorname {\mathrm {Hom}}(X,-)$ preserving filtered colimits (this property, instantiated in $\mathsf {Top}$ , is not actually the same thing as topological compactness). Our use of compactness here, to derive from the existence of a state in the "finitary" subproblems $(L,X,\Delta ^n)$ the existence of a state in the entire problem, does not have this form (nor is it even the case that $A$ is the colimit of its subsimplices), but it's possible that the proof could be rewritten to make this step more categorical.

The idea of proceeding by induction on $n$ was inspired by Reference [weinstein-elementary-minimax-2022], although our proof is rather different - they are only looking at affine games, and hence their induction step is completely different (and they have no need for the complicated $n=1$ base case that we do), and since we are not merely interested in games on simplices, we need an additional compactness argument.

We can use the minimax theorem to derive other statements of interest about convex optimization

Theorem The separating hyperplane theorem (compact case) [lcc-002Z]

May 22, 2024
Eigil Fjeldgren Rischel

Let $X,Y \subset \mathbb {R}^k$ be disjoint, compact, convex subspaces. Then there exists $v \in \mathbb {R}^k$ and $\alpha \in \mathbb {R}$ so that $\langle v,x \rangle + \alpha < 0 < \langle v,y \rangle + \alpha$ whenever $x \in X, y \in Y$ .

Proof

May 22, 2024
Eigil Fjeldgren Rischel

Consider the minmax problem

(L,X \times Y, A = \overline {B(0,1)} \subseteq \mathbb {R}^k), L(x,y,v) = \langle v,y-x \rangle .

Since the closed unit ball is compact, by the minimax theorem there exists an equilibrium $x^*,y^*,v^*$ , which then satisfies $\langle v,y^*-x^* \rangle \leq \langle v^*,y^*-x^* \rangle \leq \langle v^*,y-x \rangle$

By disjointness, $y^*-x^*$ must be nonzero, so with a suitable choice of $v$ we can clearly make the left-hand item strictly positive. Hence $\langle v^*,y^*-x^* \rangle =: \delta > 0$ . Now there must exist some $\alpha \in \mathbb {R}$ so that $\langle v^*,y^* \rangle + \alpha = -\langle v^*,x^* \rangle - \alpha = \delta /2 > 0$ .

By the equilibrium property, we see that $y^*$ must minimize $\langle v^*,y \rangle$ on $Y$ , and analogously $x^*$ must maximize $\langle v^*,x \rangle$ on $X$ . Hence for all $x,y$ , we have $\langle v^*,x \rangle + \alpha \leq -\delta /2 < 0 < \delta /2 \leq \langle v^*,y \rangle + \alpha ,$ which concludes the proof.

Theorem The separating hyperplane theorem (general case) [lcc-0030]

May 22, 2024
Eigil Fjeldgren Rischel

Let $X,Y \subseteq \mathbb {R}^k$ be disjoint convex subsets. Then there exists $v,\alpha$ so that $\langle v,x \rangle + \alpha \leq 0 \leq \langle v,y \rangle + \alpha$ for all $x \in X, y \in Y$ .

Proof

May 22, 2024
Eigil Fjeldgren Rischel

Let $K_i, L_i, i=1, \dots$ be two sequences of sets with the following properties:

For each $i$ , $K_i,L_i$ are disjoint.
For each $i$ , $K_i \subseteq K_{i+1}$
Each of the $K_i,L_i$ are compact and convex
$\cup _i K_i = X, \cup _i L_i = Y$

These can be constructed for example by taking the intersection of

X

and

Y

with the boxes

[-i,i]^k

to obtain compact, convex, disjoint subsets which exhaust

X

and

Y

.

Now apply Theorem [lcc-002Z] to obtain a sequence of $v_i \in \overline {B(0,1)}$ so that $\langle v_i,- \rangle$ is negative on $K_i$ and positive on $L_i$ . By compactness of the unit ball, this sequence has a point of density $v^*$ . Now for every pair $x \in X, y \in Y$ , we can find some $i$ so that $\langle v_i,x \rangle$ is within an arbitrary $\epsilon$ of $\langle v^*,x \rangle$ and the same is true for $y$ , and so that $x \in K_i, y \in L_i$ . But then $\langle v^*,y-x \rangle$ is within $2\epsilon$ of $\langle v_i,y-x \rangle ,$ which is positive, so that $\langle v^*,y-x \rangle \geq 0$ .

Now for each $i$ , $\langle v^*,- \rangle$ has a maximizer $x_i^*$ on $K_i$ and a minimizer $y_i^*$ on $L_i$ . Hence, by an argument analogous to the proof of Theorem [lcc-002Z], there is a nonempty closed interval $[a_i,b_i]$ so that, if $\alpha \in [a_i,b_i],$ we have $\langle v^*,- \rangle + \alpha$ $\leq 0$ on $K_i$ and $\geq 0$ on $L_i$ . But since the sets $K_i, L_i$ are increasing this sequence of intervals must be decreasing, and hence the intersection must be nonempty - and then any $\alpha$ in this intersection will make $\langle v^*,- \rangle + \alpha$ nonpositive on $X$ , nonnegative on $Y$ , as desired.

The Legendre Transform

April 30, 2024
Eigil Fjeldgren Rischel

Definition Convex conjugate [lcc-001P]

April 25, 2024
Eigil Fjeldgren Rischel

Let $V$ be a (real) vector space, and $f: V \to \mathbb {R}$ be a function (not necessarily linear). Then the convex conjugate $f^*: V^* \to \mathbb {R}$ is defined by $f^*(\alpha ) = \sup _x \alpha (x) - f(x)$

The convex conjugate is also called the Legendre transform or the Fenchel-Legendre transform. It is intimately related to convex duality. We will prove the following fundamental property of the convex conjugate using the categorical language of minmax problems, and along the way we will see the role that convex duality plays. Note that our invocation of the term "strong duality" here is somewhat more complicated than strictly necessary - normally one would merely invoke the separating hyperplane theorem directly.

Proposition [lcc-001Q]

April 25, 2024
Eigil Fjeldgren Rischel

Let $f: V \to \mathbb {R}$ be convex, so that $(V,*,f)$ is a minmax problem. Then we can form the modified minmax problem $L = (V,V^*,(x,\alpha ) \mapsto f(x) - \alpha (x))$ - note that, up to a sign change in the domain, this amounts to adding the constraint $x = 0$ .

Then $(L^*)^+ = -L^- = f^*$

Note that the two uses of the asterisk in this equation conflict. We have both the reversed optimization problem $L^*$ given by flipping the variables, and the convex conjugate function $f^*$ . It may be good to alter this notation to resolve the conflict.

Proposition [lcc-001T]

April 25, 2024
Eigil Fjeldgren Rischel

Given a minmax problem $L = (X,Y,L)$ where $X$ is a finite-dimensional real vector space, let $L|_{0} = (X, Y \oplus X^*, L \oplus - \langle -,- \rangle )$ Note that $(L|_0)^+(x) = \infty$ when $x = 0$ and $L^+(0)$ otherwise. Thus this amounts to adding a constraint that $x = 0$ . Analogously, define $L|^0 = (L^*|_0)^* = (X \oplus Y^*, Y, L \oplus \langle -, - \rangle )$

Then the Legendre transform $f^* = ((f|_0)^*)^+$ (viewing both $f$ and $f^*$ as minmax problems using the inclusion $\mathsf {Conv} \to \mathsf {Minmax}$ )

Proposition [lcc-001U]

April 25, 2024
Eigil Fjeldgren Rischel

Let $f: X \to \mathbb {R}$ be a continuous convex function defined on a vector space. Then there is strong duality in the minmax problem $f|_0$

Proof

April 25, 2024
Eigil Fjeldgren Rischel

Observe that $\{x,t \mid f(x) \leq t\} \subseteq X \oplus \mathbb {R}$ is a closed convex set. Hence there is a hyperplane through $(0,f(0))$ so that the entire set is in one half-space. This means a nontrivial affine equation $A(x,t) \geq b$ which is satisfied whenever $t \geq f(x)$ , and where $A(0,f(0)) = b$ .

Clearly $A(x,t) = \alpha _0(x) - at$ for some $\alpha _0 \in X^*, a \in \mathbb {R}$ . If $a = 0$ we have $\alpha _0(x) \leq b$ for all $x$ , which impossible. So by normalizing let's set $a = 1$ . This means $\alpha _0 (x) + f(x) \geq b = f(0)$ .

Recall that the minmax problem $f|_0$ is given by $(X,X^*,L(x,\alpha ) \mapsto f(x) - \alpha (x))$ . Strong duality means $\inf _x\sup _\alpha L(x,\alpha ) = \sup _\alpha \inf _x L(x,\alpha )$ . We always have the inequality $\geq$ , so it suffices to identify an $\alpha ^*$ so that $\inf _x \sup _\alpha L(x,\alpha ) \leq \inf _x L(x,\alpha ^*)$

Clearly, for our $L$ , we have $\inf _x\sup _\alpha L(x,\alpha ) = f(0)$ , since the supremum is $\infty$ unless $x = 0$ . On the other hand, taking $\alpha ^* = -\alpha _0$ , we have $f(0) \leq f(x) - \alpha ^*(x)$ for all $x$ by construction, finishing the proof.

Lemma [lcc-003C]

June 4, 2024
Eigil Fjeldgren Rischel

Given a commutative square:

in

\mathsf {Set}^\Delta \times \mathsf {Set}^{\Delta ,\mathrm {op}},

with the Beck-Chevalley property for the fibration from

\mathsf {Minmax},

let

(Z,C)

be some other pair of convex spaces. Then the square

also has the Beck-Chevalley condition

Proposition [lcc-001V]

April 25, 2024
Eigil Fjeldgren Rischel

Let $f$ be a convex function. Then $f = (f^*)^*$ (where $f^*$ denotes the Legendre transform), under the identification $(X^*)^* = X$ of a finite-dimensional vector space with its double dual.

Proof

April 25, 2024
Eigil Fjeldgren Rischel

Recall that $f^* = ((f|_0)^*)^+,$ as a minmax problem. Then the claim is that $(((((f|_0)^*)^+)|_0)^*)^+ = f.$ Using first the rewrite $((-)^*)^+ = ((-)^-)^*,$ and the notation $((-)^*|_0)^* = -|^0,$ we can rewrite that as $((f|_0)^-|^0)^+$

Now observe that, restricted to the subcategory $\mathsf {Minmax}_l$ given by minmax problems $(X,Y,L)$ where $X,Y$ are real vector spaces, and those homomorphisms given by linear (rather than merely affine) maps, $(-)|_0$ and $-|^0$ form endofunctors, and $(-)|_0 \dashv (-)|^0$ .

Since $(-)^-$ is left adjoint to the inclusion, we have $(-)|_0^- \dashv -|^0$ . Hence there is a canonical map, the unit of the adjunction, $L \to (L|_0)^-|^0$ for any $L$ . If $L = (X,*,f)$ is an element of $\mathsf {Conv}$ , then by the universal property, this map factors over $((f|_0)^-|^0)^+$ . This gives us the inequality $f \geq (f^*)^*$ .

(Note that this inequality actually holds even if $f$ is not convex, and indeed we haven't really used convexity yet).

Observe that, using the natural identification $(X^*)^* = X$ , we have $(f|_0)|^0 = (X \oplus X, X^*, (x,x';\alpha ) \mapsto f(x) - \alpha (x) + \alpha (x')).$ Clearly $\inf _x \sup _\alpha f(x) - \alpha (x) + \alpha (x') = f(x'),$ since the supremum is infinite unless $x = x'$ . But observe that $(f^*)^*(x') = \sup _\alpha \inf _x f(x) - \alpha (x) + \alpha (x')$

Our claim now is that we may exchange these extremizers by strong duality. This amounts to the claim that the local Beck-Chevalley property holds for this square at $(f|_0)|^0$ :

But by Proposition [lcc-001U], strong duality holds in every square of the form

and by Lemma [lcc-003C], this is establishes that the previous square has the Beck-Chevalley condition as well, which finishes the proof.

Misc stuff (sorting)

April 30, 2024
Eigil Fjeldgren Rischel

Composition of minmax problems [lcc-001Y]

April 26, 2024
Eigil Fjeldgren Rischel

Let $Y$ be a real vector space, and let $(X,Y,L), (Y^*,Z,L)$ be minmax problems. Then we can try to define a composite minmax problem $L\circ _Y L'(x,z) = \sup _y \inf _{y'} L(x,y) + L(y',z) - y'(y)$

For this composition to be associative relies on a strong duality property. We probably shouldn't want to treat this as well-defined unless it holds.

Note that by the convex duality stuff, the minmax problem $Y^*,Y,\operatorname {ev}$ acts as an identity for this composition.

This may fit together into a double category type structure for minmax problems (maybe restricted to linear maps between the spaces).

Minmax problems are not star-autonomous [lcc-001M]

April 23, 2024
Eigil Fjeldgren Rischel

Since the category of minmax problems is very similar to a Chu construction, we might hope that we could define a similar star-autonomous structure on minmax problems. Unfortunately, this does not work. We do have the duality, Dual minmax problem, but it doesn't extend to a star-autonomous structure.

Morally speaking, the tensor product of $(X,Y,L), (X',Y',L')$ would be given by $X \otimes X'$ in the forwards direction, and pairs of affine functions $f: X \to Y', g: X' \to Y$ satisfying $L(x,g(x')) = L'(x',f(x))$ in the backwards direction, with either of these expressions giving the pairing. Since the first formula implies the pairing is convex in $x$ (as it must be), but the latter implies it's concave in $x$ , $g$ must take values only those $y$ so that $L(-,y)$ is affine, and similarly for $f$ . This can easily be an empty set, but in a star-autonomous category we always have a canonical costate $L \otimes L^* \to I$ , which would be impossible in that case.

Proposition [lcc-001K]

April 23, 2024
Eigil Fjeldgren Rischel

The category of minmax problems has products, given by $(X,Y,L) \times (X',Y',L') = (X \times X', Y \oplus Y', (L \times L')),$ $(L \times L')(x,x'; \alpha y + \beta y') = \alpha L(x,y) + \beta L'(x',y')$

$(L \times L')^+(x,x') = \max (L^+(x),L'^+(x'))$

Here $Y \oplus Y'$ denotes the coproduct of convex spaces, and $\alpha y + \beta y'$ is a generic element (note that $\alpha ,\beta \in [0,1], \alpha + \beta = 1$ )

By duality (with $(-)^*$ ), it also has coproducts given by $(X,Y,L) \oplus (X',Y',L') = (X \oplus X', Y \times Y', L(\alpha x + \beta x';y,y') = \alpha L(x,y) + \beta L'(x',y'))$ .

 @article
{rischel-cvxdual-2025, title={Convex Duality Made Difficult}, volume={??}, journal={EPTCS}, author={Rischel, Eigil Fjeldgren}, pages={1–14}, date={2025} }

Reference Representable Markov categories and comparison of statistical experiments in categorical probability [fritz-gonda-perrone-rischel-rep]

June 15, 2023
Tobias Fritz, Tomas Gonda, Paolo Perrone, Eigil Fjeldgren Rischel
10.1016/j.tcs.2023.113896

Abstract

June 15, 2023
Tobias Fritz, Tomas Gonda, Paolo Perrone, Eigil Fjeldgren Rischel

Markov categories are a recent categorical approach to the mathematical foundations of probability and statistics. Here, this approach is advanced by stating and proving equivalent conditions for second-order stochastic dominance, a widely used way of comparing probability distributions by their spread. Furthermore, we lay the foundation for the theory of comparing statistical experiments within Markov categories by stating and proving the classical Blackwell-Sherman-Stein Theorem. Our version not only offers new insight into the proof, but its abstract nature also makes the result more general, automatically specializing to the standard Blackwell-Sherman-Stein Theorem in measure-theoretic probability as well as a Bayesian version that involves prior-dependent garbling. Along the way, we define and characterize representable Markov categories, within which one can talk about Markov kernels to or from spaces of distributions. We do so by exploring the relation between Markov categories and Kleisli categories of probability monads.

 @article
{fritz-gonda-perrone-rischel-rep, title={Representable Markov categories and comparison of statistical experiments in categorical probability}, volume={961}, ISSN={0304-3975}, DOI={10.1016/j.tcs.2023.113896}, journal={Theoretical Computer Science}, author={Fritz, Tobias and Gonda, Tomas and Perrone, Paolo and Fjeldgren Rischel, Eigil}, year={2023}, month={Jun}, pages={113896} }

Reference Towards Foundations of Categorical Cybernetics [towards-cybercat]

November 3, 2022
Matteo Capucci, Bruno Gavranović, Jules Hedges, Eigil Fjeldgren Rischel
10.4204/EPTCS.372.17

Abstract

November 3, 2022
Matteo Capucci, Bruno Gavranović, Jules Hedges, Eigil Fjeldgren Rischel

We propose a categorical framework for processes which interact bidirectionally with both an environment and a “controller”. Examples include open learners, in which the controller is an optimiser such as gradient descent, and an approach to compositional game theory closely related to open games, in which the controller is a composite of game-theoretic agents. We believe that “cybernetic” is an appropriate name for the processes that can be described in this framework.

@article
{towards-cybercat, title={Towards Foundations of Categorical Cybernetics}, volume={372}, ISSN={2075-2180}, DOI={10.4204/EPTCS.372.17}, url={https://arxiv.org/abs/2105.06332}, journal={Electronic Proceedings in Theoretical Computer Science}, author={Capucci, Matteo and Gavranović, Bruno and Hedges, Jules and Rischel, Eigil Fjeldgren}, year={2022}, month={Nov}, pages={235–248} }

Reference Fibre optics [fibre-optics-2021]

December 21, 2021
Dylan Braithwaite, Matteo Capucci, Bruno Gavranović, Jules Hedges, Eigil Fjeldgren Rischel
10.48550/arXiv.2112.11145
http://arxiv.org/abs/2112.11145

Abstract

December 21, 2021
Dylan Braithwaite, Matteo Capucci, Bruno Gavranović, Jules Hedges, Eigil Fjeldgren Rischel

Lenses, optics and dependent lenses (or equivalently morphisms of containers, or equivalently natural transformations of polynomial functors) are all widely used in applied category theory as models of bidirectional processes. From the definition of lenses over a finite product category, optics weaken the required structure to actions of monoidal categories, and dependent lenses make use of the additional property of finite completeness (or, in case of polynomials, even local cartesian closure). This has caused a split in the applied category theory literature between those using optics and those using dependent lenses. The goal of this paper is to unify optics with dependent lenses, by finding a definition of fibre optics admitting both as special cases.

 @article
{fibre-optics-2021, title={Fibre optics}, url={http://arxiv.org/abs/2112.11145}, DOI={10.48550/arXiv.2112.11145}, number={arXiv:2112.11145}, publisher={arXiv}, author={Braithwaite, Dylan and Capucci, Matteo and Gavranović, Bruno and Hedges, Jules and Rischel, Eigil Fjeldgren}, year={2021}, month={Dec} }

Reference Compositional abstraction error and a category of causal models [rischel_compositional_2021]

August 5, 2021
Eigil Fjeldgren Rischel, Sebastian Weichwald
10.48550/arXiv.2103.15758

Abstract

August 5, 2021
Eigil Fjeldgren Rischel, Sebastian Weichwald

Interventional causal models describe several joint distributions over some variables used to describe a system, one for each intervention setting. They provide a formal recipe for how to move between the different joint distributions and make predictions about the variables upon intervening on the system. Yet, it is difficult to formalise how we may change the underlying variables used to describe the system, say moving from fine-grained to coarse-grained variables. Here, we argue that compositionality is a desideratum for such model transformations and the associated errors: When abstracting a reference model M iteratively, first obtaining M' and then further simplifying that to obtain M'', we expect the composite transformation from M to M'' to exist and its error to be bounded by the errors incurred by each individual transformation step. Category theory, the study of mathematical objects via compositional transformations between them, offers a natural language to develop our framework for model transformations and abstractions. We introduce a category of finite interventional causal models and, leveraging theory of enriched categories, prove the desired compositionality properties for our framework.

@misc{rischel_compositional_2021,
 author = {Rischel, Eigil F. and Weichwald, Sebastian},
 date = {2021-08-05},
 doi = {10.48550/arXiv.2103.15758},
 eprint = {2103.15758 [cs, math, stat]},
 eprinttype = {arxiv},
 keywords = {Computer Science - Artificial Intelligence, Computer Science - Logic in Computer Science, Computer Science - Machine Learning, Mathematics - Category Theory, Statistics - Machine Learning},
 number = {{arXiv}:2103.15758},
 publisher = {{arXiv}},
 title = {Compositional Abstraction Error and a Category of Causal Models},
 url = {http://arxiv.org/abs/2103.15758},
 urldate = {2024-05-25}
}

Reference Infinite products and zero-one laws in categorical probability [rischel-fritz-infinite-products]

August 11, 2020
Tobias Fritz, Eigil Fjeldgren Rischel
10.32408/compositionality-2-3

Abstract

August 11, 2020
Tobias Fritz, Eigil Fjeldgren Rischel

We state and prove the zero-one laws of Kolmogorov and Hewitt-Savage within the setting of Markov categories, a category-theoretic approach to the foundations of probability and statistics. This gives general versions of these results which can be instantiated not only in measure-theoretic probability, where they specialize to the standard ones in the setting of standard Borel spaces, but also in other contexts. For example, applying the Kolmogorov law to the Kleisli category of the hyperspace monad on topological spaces gives criteria for when maps out of an infinite product of topological spaces into a Hausdorff space are constant.

 @article
{rischel-fritz-infinite-products, title={Infinite products and zero-one laws in categorical probability}, volume={2}, ISSN={2631-4444}, DOI={10.32408/compositionality-2-3}, journal={Compositionality}, author={Fritz, Tobias and Rischel, Eigil Fjeldgren}, year={2020}, month={Aug}, pages={3},language={en} }