Skip to main content

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.

  1. 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 bound
        • params = {"dimension"= ..., "lower_bound"=..., "upper_bound":..., }
    • implement methods
      • Agent_i.query(v): returns output of the subgradient oracle at point $v$ as a Point(v, q, f_i(v))
      • Agent_i._construct_params(): construct necessary parameters for $f_i$ from params
      • Agent_i.get_init_minorant(): returns initial minorant of agent's objective $\hat f^0_i$ as a cvxpy.Expression
  2. Define a structured function $g$ as an osbdo.Coupling(agents, function, domain) by specifying

    • agents: list of $M$ agents of type Agent_i
    • function: function $g$ on its domain, given as a cvxpy.Expression
    • domain: domain of $g$ given as a list of cvxpy constraints
  3. Define a distributed optimization problem as an osbdo.Problem(agents, g) by specifying

    • agents: list of $M$ agents of type Agent_i
    • g: a structured function $g$ of type Coupling
  4. 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 the Problem.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.

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

osbdo-0.0.6.tar.gz (16.0 kB view details)

Uploaded Source

Built Distribution

osbdo-0.0.6-py3-none-any.whl (19.9 kB view details)

Uploaded Python 3

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

Hashes for osbdo-0.0.6.tar.gz
Algorithm Hash digest
SHA256 f1ea6f369f074557c1e696cccdb09bc3afcf87b6eb2d48870279927c5fe15d31
MD5 8a85bb48a871ffa443c6882ea240170b
BLAKE2b-256 db9b62a3ff097b9e86e5807b030d3f29e18b77dd46d5531e06a0abeac031690a

See more details on using hashes here.

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

Hashes for osbdo-0.0.6-py3-none-any.whl
Algorithm Hash digest
SHA256 1b9e1ebe3580de15159961d720782a4f78aea36493e1c4995d012f182755fe37
MD5 fe6b860d740f5fb354fbc5489528aaef
BLAKE2b-256 580b9f3d6bc78d8af97277e714b6bfded023da49d50ac22ff3fb14baa69c134b

See more details on using hashes here.

Supported by

AWS AWS Cloud computing and Security Sponsor Datadog Datadog Monitoring Fastly Fastly CDN Google Google Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Sentry Sentry Error logging StatusPage StatusPage Status page