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

Recall the usual definition of convex optimization problem

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

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]

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

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}

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.

Proposition [lcc-001F]

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]

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

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

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

Proposition [lcc-001L]

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]

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]

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]

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\}.