This repository accompanies the manuscript Implementation of an Oracle-Structured Bundle Method for Distributed Optimization.
We consider the optimization problem
where
The oracle objective function
where
The function
In this repository we provide an implementation of the bundle-type method proposed in our manuscript.
OSBDO is available on the Python Package Index, use
pip install osbdo
Requirements
- python >= 3.8
- CVXPY >= 1.2.0
- numpy >= 1.22.2
- matplotlib >= 1.16.0
- scipy >= 1.8.0
To start using osbdo
solver, follow the procedure below.
-
Describe each objective function
$f_i$ in a class that inherits fromosbdo.Agent
Agent_i(osbdo.Agent)
- create dictionary with parameters
params
relevant for function$f_i$ - dictionary
params
contains items with the dimension of public variable$x_i$ and its lower and upper boundparams = {"dimension"= ..., "lower_bound"=..., "upper_bound":..., }
- dictionary
- implement methods
-
Agent_i.query(v)
: returns output of the subgradient oracle at point$v$ as aPoint(v, q, f_i(v))
-
Agent_i._construct_params()
: construct necessary parameters for$f_i$ fromparams
-
Agent_i.get_init_minorant()
: returns initial minorant of agent's objective$\hat f^0_i$ as acvxpy.Expression
-
-
Define a structured function
$g$ as anosbdo.Coupling(agents, function, domain)
by specifying-
agents
: list of$M$ agents of typeAgent_i
-
function
: function$g$ on its domain, given as acvxpy.Expression
-
domain
: domain of$g$ given as a list ofcvxpy
constraints
-
-
Define a distributed optimization problem as an
osbdo.Problem(agents, g)
by specifying-
agents
: list of$M$ agents of typeAgent_i
-
g
: a structured function$g$ of typeCoupling
-
-
Solve a distributed optimization problem
-
osbdo.Problem.solve()
-
memory
is an optional parameter that limits the memory (set to infinity by default); see the manuscript
-
-
osbdo.Problem.upper_bnd
,osbdo.Problem.lower_bnd
: upper and lower bounds on optimal problem value in each iteration, populated after calling theProblem.solve()
-
We provide a guideline on how to use our method using the hello world example Jupyter notebook.
We have example notebooks that show how to use our method on a number of different problems.
- supply chain problem
- resource allocation problem
- multi-commodity flow problem
- federated learning problem
Please consult our manuscript for the details of mentioned problems and their oracle-structured form.
We use our method for finding the intersection of the convex sets.
We also check the performance of OSBDO when applied to the action directed Walrasian equilibrium (over the primal variables) and price directed Walrasian equilibrium (over the dual variable).
If you use OSBDO please cite the associated paper.
@article{parshakova2022oraclestructured,
title={An Oracle-Structured Bundle Method for Distributed Optimization},
author={Tetiana Parshakova and Fangzhao Zhang and Stephen Boyd},
year={2022},
eprint={2211.01418},
archivePrefix={arXiv},
primaryClass={math.OC}
}