Algebraic Dynamics, Optimization, and Control

Three agents' trajectories, marked in green, orange and blue, converging on a triangular formation that is itself sliding to the right
Three agents holding a formation while it moves, from the AlgebraicOptimization.jl documentation.

An optimization problem is usually handed to a solver whole. That is fine until the problem is large, or distributed across machines that each hold one piece of it, at which point someone has to decompose it by hand and argue that the distributed algorithm still solves the original problem.

This project takes the composite structure as the input rather than the obstacle. An optimization problem is assembled from subproblems with an algebraic syntax, and the distributed algorithm that solves it is generated from the same structure – not written to match it. Model predictive control is the case that motivates the work: an MPC problem is already a sequence of coupled subproblems across a horizon, which is exactly what composition describes.

Project team

How the papers fit together

Tyler Hanks led this project and James Fairbanks is an author on the papers below, so each entry names the rest of the collaborators.

Modeling model predictive control: a category theoretic framework for multistage control problems, with Baike She, Matthew Hale, Evan Patterson and Matthew Klawonn of the Air Force Research Laboratory, is the founding paper: a monoidal category whose morphisms are constrained convex problems, in which the multistage structure of MPC is sequential composition and cross-stage constraints are parallel composition.

Characterizing compositionality of LQR from the categorical perspective, with Baike She and Matthew Hale, asks when compositional design is exact – when the optimal controller for a whole system really is the composite of optimal controllers for its parts – and reduces the check to controllability and observability of one linear time-invariant system.

A compositional framework for first-order optimization, with Matthew Klawonn, Evan Patterson and Matthew Hale, is the general statement: problems form operad algebras, and gradient descent, Uzawa’s algorithm and their subgradient variants are algebra morphisms into algebras of dynamical systems. This is what the software implements.

Generalized gradient descent is a hypergraph functor, with Matthew Klawonn, sharpens that to a single sentence: taken over a cartesian reverse derivative category, generalized gradient descent is a functor from open optimization problems to open dynamical systems, so the distributed algorithm is the image of the problem’s structure rather than a design decision.

Software

Project articles

Where an entry carries a note, it says what the paper establishes and what to read it for.

  1. Hanks, T., Fairbanks, J. P., & Klawonn, M. (2025). Generalized Gradient Descent is a Hypergraph Functor. In Electronic Proceedings in Theoretical Computer Science (pp. 217-233). https://doi.org/10.4204/EPTCS.429.12

    Generalized gradient descent, taken with respect to a cartesian reverse derivative category, is a hypergraph functor from a category of open objective functions to a category of open dynamical systems. Composite problems in the domain therefore induce distributed algorithms in the codomain, and parameter-sharing multitask models are one example of a problem the framework covers. It is the sharpest form of the claim the optimization project keeps making: the algorithm is not designed to match the problem’s structure, it is the image of that structure under a functor.

    Read it for The functor and its proof. The multitask learning example shows what the generality buys you.

    Read first A Compositional Framework for First-Order Optimization

  2. Hanks, T., She, B., Hale, M., Patterson, E., Klawonn, M., & Fairbanks, J. P. (2024). Modeling Model Predictive Control: A Category Theoretic Framework for Multistage Control Problems. In 2024 American Control Conference (ACC) (pp. 4850-4857). IEEE. https://doi.org/10.23919/ACC60939.2024.10644848

    Model predictive control problems compose. The paper builds a monoidal category whose objects are Euclidean spaces and whose morphisms are constrained convex optimization problems, then shows that the multistage structure of an MPC problem is sequential composition in that category, and constraints tying stages together are parallel composition. The syntax is diagrammatic, and it maps onto existing Julia mathematical programming libraries. It is the project’s founding paper: the first place the lab treated a control problem as something assembled from parts with a syntax, rather than as a monolith handed to a solver.

    Read it for The construction of the category and the worked MPC diagram. The software section is short and worth the detour.

  3. Hanks, T., Klawonn, M., Patterson, E., Hale, M., & Fairbanks, J. P. (2024). A Compositional Framework for First-Order Optimization. arXiv. https://doi.org/10.48550/arXiv.2403.05711

    An algebraic account of optimization problems composed on a hypergraph: operads for syntax, operad algebras for semantics, algebra morphisms for the transformations that preserve structure. Classes of optimization problems form operad algebras, and first-order methods – gradient descent, Uzawa’s algorithm, their subgradient variants – are algebra morphisms into algebras of dynamical systems, so a distributed solver falls out of the way the problem was assembled. It is the general statement the lab’s optimization software implements: the reason AlgebraicOptimization.jl can generate a distributed algorithm from the structure of a problem rather than from a hand-written decomposition.

    Read it for Sections 3 and 4, where the problem algebra and the solver morphism are defined. The rest can wait for a second pass.

  4. She, B., Hanks, T., Fairbanks, J. P., & Hale, M. (2023). Characterizing Compositionality of LQR from the Categorical Perspective. In 2023 62nd IEEE Conference on Decision and Control (CDC) (pp. 1680-1685). https://doi.org/10.1109/CDC49753.2023.10383467

    Designing an optimal controller for a whole system and composing optimal controllers designed for its parts are not the same thing. Using resource sharing machines, the paper gives sufficient conditions under which the LQR for a composite system does equal the composite of the subsystems’ LQRs, and reduces checking them to the controllability and observability of one linear time-invariant system. Compositional design is only useful if you know when it is exact. This is the negative-result-and-its-boundary paper the rest of the optimization work leans on.

    Read it for The counterexample and the sufficient conditions. Skim the LQR background if you have seen it before.

Sponsors

AlgebraicOptimization and Control has been supported by the following programs:

  • NSF: Graduate Research Fellowship Program
  • ONR: Domain Transfer for Continuity of Performance
  • AFRL: Griffis Summer Internship Program