Convex optimization with a categorical point of view

This is a companion discussion topic for the original entry at
1 Like

I took an algorithms class with dual/primal linear optimization stuff, I TAed that same algorithms class, and this is the first time I’m like “oh, OK, that makes sense.” Also, I’m not sure if you are aware of Tyler Hank’s work on optimization, might be interesting. [2403.05711] A Compositional Framework for First-Order Optimization.


Not all the way through reading this yet, but I’m enjoying it already.

It seems like your definition of a minimax problem is as a Chu space in convex spaces, though not quite since the right hand side is concave. We can define a sort of Chu construction in any equipment, and applying this to enriched categories says that a Chu space is a bimodule A \otimes B^{\text{op}} \to \mathcal{V}, which reminds me a lot of the concave on the right, convex on the left part of your definition. I wonder if there is a double category of minimax problems, constructed by the Chu construction from an equipment of convex spaces and “convex-concave bimodules”.

1 Like

Yes, I agree there is something very bimodule-like about the convex/concave thing, although I haven’t been able to figure out exactly what the right analogy is.

One somewhat clunky way to do this is the following:

Given an algebra TA \to A of a monad, we can equip the free algebra TA with a partial order given by partial evaluations (ie t \leq t' if t' is a partial evaluation of t).
Then if A = (\Delta A \to A) a convex space, a map \Delta A \to \mathbb{R} which is order-preserving and a \Delta-algebra homomorphism is exactly a concave function in the usual sense. Then a convex map is one defined on the opposite order, and just maybe a “sesquiconvex” map is one defined on something like (\Delta A)^{op} \otimes \Delta B (it’s not totally clear the tensor product can be lifted to partially ordered convex spaces).

1 Like

I think a cleaner way to do this is just make \Delta a 2-monad on the (2,1)-category of posets. Then we can consider lax and colax algebra maps from an algebra with a discrete carrier to \mathbb{R} with its normal order.

1 Like

I was thinking something along these lines, but I couldn’t figure out how to do bilinearity (ie lax homomorphic in one variable, colax in the other)…

OK, now I understand better Eigil’s approach and why it’s important. I wonder if one could construct Eigil’s approach via some kind of universal property where order preserving, strict maps \Delta A \to \mathbb{R} are in natural bijection with lax maps A \to \mathbb{R}, if that makes sense.