Oracle-Structured Bundle Distributed Optimization
Project description
Oracle-Structured Bundle Distributed Optimization (OSBDO)
This repository accompanies the manuscript An Oracle-Structured Bundle Method for Distributed Optimization.
We consider the optimization problem
\begin{array}{ll}
\mbox{minimize} & h(x) = f(x) + g(x),
\end{array}
where $x \in {\mbox{\bf R}}^n$ is the variable, and $f, g:{\mbox{\bf R}}^n \to {\mbox{\bf R}}\cup {\infty}$ are the oracle and structured convex objective functions, respectively.
The oracle objective function $f$ is block separable, i.e., is of the form
f(x) = \sum_{i=1}^M f_i(x_i),
where $x_i \in {\mbox{\bf R}}^{n_i}$ and $x=(x_1, \ldots, x_M)$. We refer to $x_i$ as the public variable and $f_i$ as the objective function of the agent $i$. Our access to $f_i$ is only via an oracle that evaluates the function value and a subgradient at a given point $x_i$, i.e., $f_i(x_i)$ and $q_i \in \partial f_i(x_i)$.
The function $g$ is structured in the sense that we are given its complete description in disciplined convex programming (DCP) format. Presumably the function $g$ couples the block variables $x_1, \ldots, x_M$.
In this repository we provide an implementation of the bundle-type method proposed in our manuscript.
Installation
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
Getting started
To start using osbdo
solver, follow the procedure below.
-
Describe each objective function $f_i$ in a class that inherits from
osbdo.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 an
osbdo.Coupling(agents, function, domain)
by specifyingagents
: 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 specifyingagents
: 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()
Hello world
We provide a guideline on how to use our method using the hello world example Jupyter notebook.
Example notebooks
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.
Extra example
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).
Project details
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distribution
File details
Details for the file osbdo-0.0.6.tar.gz
.
File metadata
- Download URL: osbdo-0.0.6.tar.gz
- Upload date:
- Size: 16.0 kB
- Tags: Source
- Uploaded using Trusted Publishing? No
- Uploaded via: twine/4.0.1 CPython/3.8.10
File hashes
Algorithm | Hash digest | |
---|---|---|
SHA256 | f1ea6f369f074557c1e696cccdb09bc3afcf87b6eb2d48870279927c5fe15d31 |
|
MD5 | 8a85bb48a871ffa443c6882ea240170b |
|
BLAKE2b-256 | db9b62a3ff097b9e86e5807b030d3f29e18b77dd46d5531e06a0abeac031690a |
File details
Details for the file osbdo-0.0.6-py3-none-any.whl
.
File metadata
- Download URL: osbdo-0.0.6-py3-none-any.whl
- Upload date:
- Size: 19.9 kB
- Tags: Python 3
- Uploaded using Trusted Publishing? No
- Uploaded via: twine/4.0.1 CPython/3.8.10
File hashes
Algorithm | Hash digest | |
---|---|---|
SHA256 | 1b9e1ebe3580de15159961d720782a4f78aea36493e1c4995d012f182755fe37 |
|
MD5 | fe6b860d740f5fb354fbc5489528aaef |
|
BLAKE2b-256 | 580b9f3d6bc78d8af97277e714b6bfded023da49d50ac22ff3fb14baa69c134b |