« Home

Menu

List of Publications
Blog
Problems that haunt me

Proposition [lcc-001F]

April 22, 2024
Eigil Fjeldgren Rischel

Let $\phi : L \to L'$ be a morphism of minmax problems. Then $L^+(x) \geq L'^+(\phi ^+(x))$ and $L^-(\phi ^-(y)) \geq (L')^-(y)$

Context

Convex optimization with a categorical point of view [lcc-001H]

April 22, 2024
Eigil Fjeldgren Rischel

Recall the usual definition of convex optimization problem

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

Given such a problem, the Lagrangian is the function given by $L(x,\lambda ,\nu ) = f_0(x) + \sum _i \lambda _i f_i(x) + \sum _i \nu _i g_i(x),$ defined on $\mathbb {R}^k \times \mathbb {R}^n_+ \times \mathbb {R}^m$ , where $\mathbb {R}_+ = \lsqb 0,\infty \rpar$ .

In the theory of convex optimization, the Lagrangian, and data derived from it, plays a central role. Note that replacing the constraints of the problem with different, equivalent ones, would result in a totally different Lagrangian. Thus problems that are "equivalent", in the sense of having the same solutions (or solutions that are readily translated to each other) may not always be freely replaced with each other.

Observe that $\sup _{\lambda ,\nu } L(-,\lambda ,\nu )$ is $\infty$ if $x$ does not satisfy the constraints, and $f_0(x)$ if it does. Hence we can think of $L$ as a two-player zero-sum game, and the original problem is what we get if "we" control the $x$ variable, our adversary controls the other variables, and our adversary "moves second". We may think of this as replacing a hard constraint $f_i(x) \leq 0$ with a soft constraint (a cost which must be paid to violate that constraint), but letting the price be controlled by the adversary.

This suggests that, perhaps, such two-player minmax games should be thought of as the fundamental object in the theory of convex optimization

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

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}$

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.

Proposition [lcc-001F]

April 22, 2024
Eigil Fjeldgren Rischel

Let $\phi : L \to L'$ be a morphism of minmax problems. Then $L^+(x) \geq L'^+(\phi ^+(x))$ and $L^-(\phi ^-(y)) \geq (L')^-(y)$

Example [lcc-001I]

April 22, 2024
Eigil Fjeldgren Rischel

Consider the problem "Optimize $f(Ax + b)$ ", where $A: X \to Y$ is a linear map between two finite-dimensional real vector spaces. This is clearly equivalent (in an informal sense) to "Optimize $f(y)$ subject to $y = Ax + b$ ".

The first of these problems corresponds to $L_1 = (X,*,L_1(x,*) = f(Ax + b))$

The second corresponds to $L_2 = (X \times Y, Y^*, L_2(x,y,\alpha ) = f(y) + \alpha (Ax + b---y))$ (Where by $Y^*$ I just mean the vector space dual of $Y$ )

There is a morphism $L_1 \to L_2$ , defined by $\phi ^+(x) = (x, Ax+b)$ . The fact that this is a morphism gives the inequality $(L_1)_*(x) \geq (L_2)_*(\phi ^+(x)),$ which is one part of the "equivalence".

In the other direction, we have the map $(x,y) \mapsto x$ , the first projection. Now, it is true that $(L_2)_*(x,y) \geq (L_1)_*(x)$ ---the former is $\infty$ unless $y = Ax + b$ , in which case they're both equal to the infimal value of $f(Ax + b)$ . But there is no map $* \to Y^*$ picking out an $\alpha$ which witnesses this---even if we pass to some sort of extended reals, the signs we want to choose depend on the sign of $Ax + b---y$ , which could go either way. This is one sense in which the problems are "equivalent but not isomorphic".

The structure of minmax

April 22, 2024
Eigil Fjeldgren Rischel

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

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

Proposition [lcc-001L]

April 23, 2024
Eigil Fjeldgren Rischel

Let $\Delta : \mathsf {Set} \to Set$ be the discrete probability distribution monad, so that its algebras are convex spaces. $\Delta$ is finitary, so by abstract nonsense $\mathsf {Alg}(\Delta )$ has coproducts. These are given by $0 = \emptyset$ (with a trivial convex structure), and $X + Y = X \sqcup X \times Y \times (0,1) \sqcup Y,$ with the convex structure given by regarding $(x,y,\alpha )$ as $\alpha x + (1-\alpha ) y$ , and reducing any convex combination to one containing at most one element from each of $X$ and $Y$ .

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.

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)

[lcc-001O]

April 23, 2024
Eigil Fjeldgren Rischel

Given a convex space $X$ and a convex function $p: X \to \mathbb {R}$ , we may of course form the convex subspace $\{x \mid p(x) \leq 0\}$ .

Given some minmax problem involving $X$ , $L: X \times Y \to \mathbb {R}$ , we can instead form $L' : X \times (Y \times \mathbb {R}^+) \to RR$ given by $L'(x;y,\alpha ) = L(x,y) + \alpha p(x)$ . We have a map into $L$ in this case, given by the identity on $X$ and carrying $y$ to $(y,0)$ , which is an alternative "version" of the inclusion of $\{x \mid p(x) \leq 0\}$ .

Related

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