# Convex optimization with a categorical point of view

This is a companion discussion topic for the original entry at https://forest.localcharts.org/efr-001h.xml
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.

2 Likes

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.