CIAO: Constrained Aggregative Optimization

Research code for centralized and distributed aggregative optimization, with a focus on shared-resource constraints and the proposed CIAO algorithm: ConstraIned Aggregative Optimization.

This repository accompanies the master's thesis:

Luca Fantini, Computational Offloading in Cloud Computing via Primal-Dual Distributed Aggregative Optimization, University of Bologna and UCLouvain, 2026.

The codebase is designed as an experimentation framework rather than a single solver. Cost functions, aggregation maps, constraints, communication graphs, algorithms, trajectory collection, and plots are separate components that can be combined to compare centralized benchmarks with distributed methods.

Research Context

Consider a network of $N$ agents. Agent $i$ controls a local decision $z_i \in \mathbb{R}^d$, contributes to a global aggregate through $\phi_i(z_i)$, and has a local objective that depends on both its own decision and the aggregate:

$$ \sigma(\mathbf{z}) = \frac{1}{N}\sum_{i=1}^{N}\phi_i(z_i), \qquad \ell_i\bigl(z_i,\sigma(\mathbf{z})\bigr). $$

The global optimization problem is

$$ \min_{\mathbf{z}} \sum_{i=1}^{N}\ell_i\bigl(z_i,\sigma(\mathbf{z})\bigr). $$

This structure models systems in which agents make private local decisions but interact through a shared quantity. The motivating application is computational offloading: each device chooses how much work to execute locally and how much to offload, while congestion and shared cloud resources depend on the collective decisions.

The repository studies three progressively richer settings:

1. Aggregative optimization with local box constraints

   $$ z_i \in [0,1]^d. $$

2. Aggregative optimization with affine coupling constraints

   $$ \sum_{i=1}^{N} B_i z_i \leq \sum_{i=1}^{N} b_i. $$

3. Aggregative optimization with a constraint directly on the aggregate

   $$ \sigma(\mathbf{z}) \leq c. $$

The third setting is the main research target. CIAO combines primal-dual updates with dynamic tracking and local communication so that every agent can enforce a constraint on an aggregate that no individual agent can compute directly.

Research Lineage

The foundation of the project is the distributed aggregative optimization framework introduced by Li, Xie, and Hong. Their method tracks the aggregate and the aggregate-dependent gradient using local exchanges over a communication network.

The affine-coupling reference is the distributed aggregative primal-dual method of Du and Meng. This repository implements that setting as a benchmark and uses its structure as a starting point for constraints imposed directly on $\sigma(\mathbf{z})$.

CIAO preserves the main distributed ingredients:

• local primal updates;
• dynamic average tracking of aggregative quantities;
• local dual variables and projection onto the nonnegative orthant;
• consensus-related auxiliary dynamics;
• synchronous updates based only on values available at iteration $k$.

Code Architecture

The framework follows a modular three-layer design:

flowchart TD
    Main["Experiment scripts<br/>main_*.py"]
    Graph["Communication graph<br/>utils/graph_utils.py"]
    Problem["OptimizationProblem hierarchy"]
    Agent["Agent"]
    Cost["CostFunction"]
    Phi["AggregationContributionFunction"]
    Constraint["Constraint"]
    Algorithm["Algorithm.run(params)"]
    Result["RunResult + trajectories"]
    Plot["Plotters and diagnostics"]

    Main --> Graph
    Main --> Problem
    Main --> Algorithm
    Problem --> Agent
    Agent --> Cost
    Agent --> Phi
    Agent --> Constraint
    Algorithm --> Problem
    Algorithm --> Result
    Result --> Plot

Loading

Repository Layout

.
├── src/
│   ├── main_agg_tracking.py
│   ├── main_affine_constr.py
│   ├── main_sigma_constr.py
│   ├── main_variance_constr.py
│   ├── algorithms/
│   │   ├── aggregative_tracking/
│   │   │   ├── centralized/
│   │   │   └── distributed/
│   │   ├── affine_constraints/
│   │   │   ├── centralized/
│   │   │   └── distributed/
│   │   └── sigma_constraints/
│   │       ├── centralized/
│   │       └── distributed/
│   ├── models/
│   │   ├── agent.py
│   │   ├── algorithm_interface.py
│   │   ├── constraints.py
│   │   ├── cost.py
│   │   ├── optimization_problem.py
│   │   └── phi.py
│   └── plots/
├── tests/
├── utils/
├── img/
└── output/

Core Components

Agent

Agent is intentionally lightweight. It owns:

• the local decision state zz;
• a cost function;
• an aggregation contribution function $\phi_i$;
• an optional local constraint;
• a dictionary of algorithm-specific buffers.

Algorithms can add local states without modifying the Agent class:

agent["ss"] = agent.phi()
agent["vv"] = agent.nabla_2(agent["zz"], agent["ss"])
agent["ll"] = np.zeros(problem.m)

This is used for trackers, dual variables, previous iterates, and auxiliary consensus states.

Optimization Problems

The problem hierarchy centralizes global structure while keeping the agents modular:

Class	Purpose
OptimizationProblem	Agents, mixing matrix, aggregate, centralized cost, and centralized gradient
ConstrainedOptimizationProblem	Abstract interface for residuals, feasibility, and global constraint data
AffineCouplingProblem	Builds local and global affine-coupling matrices
ConstrainedSigmaProblem	Enforces $\sigma(\mathbf{z}) \leq c$

OptimizationProblem also checks that the communication matrix is nonnegative and doubly stochastic, as required by the implemented tracking dynamics.

Cost and Aggregation Models

Cost functions implement:

cost_fn(z_i, sigma)
nabla_1(z_i, sigma)
nabla_2(z_i, sigma)

Available models include:

• QuadraticCostFunction;
• LocalCloudTradeoffCostFunction;
• linear and superlinear cloud-congestion variants.

Aggregation contribution functions implement:

eval(z_i)
nabla(z_i)

Available mappings include:

• IdentityFunction;
• LinearFunction;
• SquareComponentWiseFunction;
• WeightedQuadraticContribution.

The nonlinear weighted quadratic map is used in the main experiments:

$$ \phi_i(z_i) = w_i\left(z_i + \rho_i z_i^2\right). $$

Common Algorithm Interface

Every solver inherits from Algorithm and exposes the same entry point:

result = algorithm.run(algorithm.AlgorithmParams(...))

Every run returns a RunResult containing:

RunResult(
    algorithm_name=...,
    algorithm_fullname=...,
    algorithm_module=...,
    cost_fn_name=...,
    zz_traj=...,
    grad_traj=...,
    cost_traj=...,
    aux=...,
)

TrajectoryCollector preallocates and validates histories during execution. The common result format decouples numerical algorithms from visualization and makes centralized/distributed comparisons straightforward.

Why the Main Scripts Look Similar

The four main_* scripts deliberately follow the same experiment lifecycle:

1. Fix dimensions, seed, model parameters, and initial conditions.
2. Define setup_problem() as a reproducible problem factory.
3. Build a fresh problem for the centralized benchmark.
4. Configure parameters and call Algorithm.run(...).
5. Build a fresh equivalent problem for the distributed method.
6. Configure parameters and call the same Algorithm.run(...) interface.
7. Analyze both RunResult objects with the same plotting API.

Fresh problem instances matter because algorithms update agent states in place. Rebuilding the problem ensures that centralized and distributed methods start from equivalent initial conditions rather than from the final state of a previous run.

This repeated structure is intentional: the experiment changes, but the execution and evaluation pipeline stays stable.

Script	Problem	Centralized benchmark	Distributed method
main_agg_tracking.py	Unconstrained aggregative optimization with box projection	CentralizedGradientMethod	AggregativeTracking
main_affine_constr.py	Affine coupling constraints	AugmentedPrimalDualGradientDescent or ArrowHurwiczUzawaPrimalDualGradientDescent	DuMeng2
main_sigma_constr.py	Constraint on $\sigma(\mathbf{z})$	SigmaConstraint	CIAO
main_variance_constr.py	Variance-constrained exploratory extension	Not yet provided	Implementation missing from the current repository snapshot

Implemented Algorithms

Aggregative Tracking

Algorithm	Type	Role
CentralizedGradientMethod	Centralized	Computes the exact aggregate and global aggregative gradient
AggregativeTracking	Distributed	Tracks the aggregate and aggregate-gradient contribution using local consensus

The distributed method stores:

• ss: local estimate of $\sigma(\mathbf{z})$;
• vv: local estimate of the average aggregate-dependent gradient.

Affine Coupling Constraints

Algorithm	Type	Status
ArrowHurwiczUzawaPrimalDualGradientDescent	Centralized	Reference implementation
AugmentedPrimalDualGradientDescent	Centralized	Main centralized affine benchmark
DuMeng2	Distributed	Main working affine-coupling reference
DuMeng, DuMeng3, DuMeng4, DuMeng5, DuMeng6	Distributed	Research variants retained for comparison and algorithm development

The DuMeng* files document alternative realizations of the distributed dual subsystem. Their detailed status and motivation are recorded in src/algorithms/affine_constraints/distributed/README.md.

Constraint on the Aggregative Variable

Algorithm	Type	Role
SigmaConstraint	Centralized	Primal-dual benchmark for $\sigma(\mathbf{z}) \leq c$
CIAO	Distributed	Proposed constrained aggregative optimization method

CIAO combines:

• a local primal step using tracked aggregative information;
• an ss dynamic tracker for the aggregate;
• a vv dynamic tracker for the aggregate-dependent gradient;
• projected local dual variables;
• an auxiliary network state for dual consensus;
• a regularization parameter theta.

The implementation uses snapshot-then-writeback updates: all $k+1$ values are computed from the shared iteration-$k$ state before agent buffers are updated. This mirrors a synchronous distributed execution and avoids accidentally exposing a neighbor's new value during the same iteration.

Installation

The repository currently does not include packaged dependency metadata. A minimal environment can be created with:

python -m venv .venv
source .venv/bin/activate
python -m pip install numpy matplotlib networkx multipledispatch pytest

sympy is only needed for the optional symbolic utility script.

python -m pip install sympy

Running Experiments

The current imports and output paths are designed for execution from src/:

cd src

python main_agg_tracking.py
python main_affine_constr.py
python main_sigma_constr.py

Each main script defines flags controlling interactive display and file output:

SHOW_CENTRALIZED = False
SHOW_DISTRIBUTED = False
SHOW_COMPARISON = False

SAVE_CENTRALIZED = True
SAVE_DISTRIBUTED = True
SAVE_COMPARISON = True

Generated figures are written to output/.

The main parameters to tune are:

• N: number of agents;
• d: local decision dimension;
• seed: reproducible random seed;
• max_iter: number of iterations;
• stepsize: primal step size;
• dual_stepsize: centralized dual step size;
• beta, gamma: distributed dual-dynamics parameters;
• theta: CIAO regularization parameter;
• communication graph type and connectivity.

Minimal Programmatic Example

The following example assembles and runs a small centralized aggregative problem:

import numpy as np

from algorithms.aggregative_tracking.centralized import CentralizedGradientMethod
from models.agent import Agent
from models.cost import QuadraticCostFunction
from models.optimization_problem import OptimizationProblem
from models.phi import IdentityFunction

N, d = 3, 1
adj = np.ones((N, N)) / N

agents = []
for i in range(N):
    cost = QuadraticCostFunction(
        QuadraticCostFunction.CostParams(cc=np.ones(d))
    )
    agents.append(
        Agent(
            idx=i,
            cost_fn=cost,
            phi=IdentityFunction(d),
            init_state=np.array([0.2 + 0.1 * i]),
        )
    )

problem = OptimizationProblem(agents, adj, seed=7)
algorithm = CentralizedGradientMethod(problem)
params = algorithm.AlgorithmParams(max_iter=1000, stepsize=0.01, seed=7)
result = algorithm.run(params)

result.summary()

Communication Graphs

utils/graph_utils.py generates:

• Erdos-Renyi graphs;
• cycles;
• paths;
• stars;
• complete graphs.

The Metropolis-Hastings rule converts an undirected connected graph into a doubly stochastic mixing matrix. Distributed algorithms access row i of this matrix as the local communication weights available to agent $i$.

Results and Diagnostics

The plotting layer consumes only RunResult, not algorithm internals.

Available diagnostics include:

• objective or augmented-Lagrangian evolution;
• gradient norm;
• agent trajectories;
• aggregate/tracker trajectories;
• local multiplier trajectories;
• consensus errors;
• primal and dual projected-stationarity residuals;
• KKT stationarity, feasibility, and complementarity proxies;
• two-agent phase portraits;
• centralized/distributed comparisons.

The fluent plotting API supports compact experiment definitions:

plotter = plots.ConstrainedRunResultPlotter(problem, result)

plotter \
    .clear() \
    .plot_cost() \
    .plot_grad_norm() \
    .plot_lambda_trajectory(semilogy=False) \
    .plot_sigma_trajectory() \
    .plot_lagr_stationarity() \
    .plot_kkt_conditions() \
    .save(filename)

Extending the Framework

Add a Cost Function

Implement the common value and partial-gradient interface:

class MyCost(CostFunction):
    def cost_fn(self, z_i, sigma):
        ...

    def nabla_1(self, z_i, sigma):
        ...

    def nabla_2(self, z_i, sigma):
        ...

Add an Aggregation Map

class MyAggregation(AggregationContributionFunction):
    def eval(self, z_i):
        ...

    def nabla(self, z_i):
        ...

Add an Algorithm

Implement the shared Algorithm contract and return standard trajectories:

class MyAlgorithm(Algorithm):
    class AlgorithmParams(Algorithm.AlgorithmParams):
        def __init__(self, max_iter, stepsize, seed, my_parameter):
            super().__init__(max_iter, stepsize, seed)
            self.my_parameter = my_parameter

    def run(self, params):
        ...
        return RunResult(
            algorithm_name="MyAlgorithm",
            algorithm_fullname=type(self).__name__,
            algorithm_module=self.__class__.__module__,
            cost_fn_name=type(self.problem.agents[0]._cost_fn_obj).__name__,
            zz_traj=...,
            grad_traj=...,
            cost_traj=...,
            aux={"sigma_traj": ...},
        )

Keeping RunResult compatible makes the existing plotting and comparison tools immediately reusable.

Tests

The test suite covers:

• trajectory shapes and finite values;
• decreasing gradient-norm proxies;
• bounded and decreasing costs;
• affine feasibility and stationarity proxies;
• centralized/distributed agreement;
• reproducibility from fresh problem factories;
• rejection of non-doubly-stochastic communication matrices.

Run:

PYTHONPATH=src:. pytest -q

Some comparisons are marked as slow:

PYTHONPATH=src:. pytest -q -m slow

References

The two central references are:

1. X. Li, L. Xie, and Y. Hong, “Distributed Aggregative Optimization Over Multi-Agent Networks,” IEEE Transactions on Automatic Control, vol. 67, no. 6, pp. 3165-3171, Jun. 2022. https://doi.org/10.1109/TAC.2021.3095456

2. K. Du and M. Meng, “Distributed aggregative optimization with affine coupling constraints,” Neural Networks, vol. 184, Art. no. 107085, 2025. https://doi.org/10.1016/j.neunet.2024.107085

Additional references directly connected to the implemented methods:

3. M. Zhu and S. Martinez, “Discrete-time dynamic average consensus,” Automatica, vol. 46, no. 2, pp. 322-329, 2010. https://doi.org/10.1016/j.automatica.2009.10.021

4. G. Qu and N. Li, "On the Exponential Stability of Primal-Dual Gradient Dynamics," IEEE Control Systems Letters, vol. 3, no. 1, pp. 43-48, Jan. 2019,. https://ieeexplore.ieee.org/document/8399490

5. M. Bin, I. Notarnicola, and T. Parisini, “Semiglobal exponential stability of the discrete-time Arrow-Hurwicz-Uzawa primal-dual algorithm for constrained optimization,” Mathematical Programming, vol. 208, pp. 629-660, 2024. https://doi.org/10.1007/s10107-023-02051-2

6. S. A. Alghunaim, Q. Lyu, M. Yan, and A. H. Sayed, “Dual consensus proximal algorithm for multi-agent sharing problems,” IEEE Transactions on Signal Processing, vol. 69, pp. 5568-5579, 2021. https://doi.org/10.1109/TSP.2021.3114978

Author

Luca Fantini

Master's thesis developed with the supervision of Prof. Giuseppe Notarstefano and Prof. Gianluca Bianchin, and the co-supervision of Dr. Riccardo Brumali and Dr. Amir Mehrnoosh.