Proposition weak duality [lcc-001W]

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

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.

Context

Convex Duality made Difficult [lcc-001Z]

Introduction

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

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

A convex optimization problem in standard form consists of

  1. A convex function f_0: \mathbb {R}^k \to \mathbb {R}
  2. A list of convex functions f_1, \dots f_n: \mathbb {R}^k \to \mathbb {R}
  3. 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]

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

Definition Convex Space [lcc-0020]

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]

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]

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]

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]

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]

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

Proof

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]

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]

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

Definition Minmax problem [lcc-001C]

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

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

  1. \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
  2. The property of strong duality amounts to the claim that a particular diagram has the local Beck-Chevalley property
  3. 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]

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]

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]

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]

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]

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

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]

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.

  1. 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
  2. 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)
  3. 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)
  4. 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

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]

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]

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]

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]

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

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

Proposition weak duality [lcc-001W]

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

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]

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]

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]

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

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]

Consider an optimization problem in standard form:

  1. Minimize f_0(x), x \in \mathbb {R}^k
  2. Subject to f_1(x), \dots , f_n(x) \leq 0
  3. And g_1(x), \dots , g_m(x) = 0
  4. 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

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

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]

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]

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

Proof

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]

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

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

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]

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

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]

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

Proof

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.

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]

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

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]

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

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

Definition Convex conjugate [lcc-001P]

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]

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]

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]

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

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]

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]

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

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)

Composition of minmax problems [lcc-001Y]

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]

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]

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

Backlinks

Definition Strong duality [lcc-002F]

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