## Alternating Direction Method of Multipliers (ADMM)

ADMM is applied to problems whose structure can be represented as a bipartite graph.

A bipartite graph is a graph whose vertices (nodes) are divided into two disjoint sets. Edges only connect nodes from the opposite sets.



#### Notation

The bipartite graph representing the problem structure is referred to as computation graph. Each node in the graph is associated with a computing agent.  

In the above graph
1. Circles - nodes (agents) of type I
2. Rectangles - nodes (agents) of type II

ADMM solves the problem

$
    \begin{aligned}
    \underset{x \in \Omega, z \in \Theta}{\text{minimize}}\quad & \sum\limits_{i} f_i(x_i) + \sum\limits_{i} g_i(z_i)\\
    \text{subject to}\quad  & x_i = z_j
    \end{aligned}
$

where\
$x_i$ and $f_i(x_i)$ are variables and objective of *i*-th agent I\
$z_i$ and $g_i(z_i)$ are variables and objective of *i*-th agent II

Shared variables represented by edges must meet the consensus constraint $x_i = z_j$

The augmented Lagrangian function associated with the above problem

$L(x,z,\lambda) = \sum\limits_{i} f_i(x_i) + \sum\limits_{i} g_i(z_i) + \frac{\rho}{2} \sum\limits_{i} \|x_i-z_i+u_i\|_2^2$

The Lagrangian function is solved applying the following steps

__Step 1__ Type I agents solve their local subproblems

$x_{i}^{(k+1)}  = \text{argmin} \; f_i(x_i) + \frac{\rho}{2} \|x_i - (z_i^k - u_i^k)\|_2^2$

__Step 2__ Type II agents solve their local subproblems

$ z_{i}^{(k+1)} = \text{argmin} \; g_i(z_i) + \frac{\rho}{2} \|z_i - (x_i^{(k+1)} + u_i^k)\|_2^2 $

__Step 3__ Type II agents update dual variables

$u_{i}^{(k+1)}  = u_i^k + (x_i^{(k+1)} - z_i^{(k+1)})$

The above steps are repeated until convergence criteria are met. The convergence criteria are defined locally for primal and dual residuals.

$
\begin{equation}
\begin{aligned}
r^{\text{primal}} &<  \epsilon^{\text{primal}} \\
r^{\text{dual}} &<  \epsilon^{\text{dual}} \\
\end{aligned}
\end{equation}
$

where $\epsilon^{\text{primal}},\epsilon^{\text{dual}}$ are small positive numbers representing primal and dual tolerances, respectively. The primal and dual residuals are computed as

$
\begin{equation}
\begin{aligned}
r^{\text{primal}} &= \| x_i^k - z_i^k \|_2 \\
r^{\text{dual}} &= \| \rho (z_i^k - z_i^{k-1}) \| _2 \\
\end{aligned}
\end{equation}
$

## ADMM4J: Alternating Direction Method of Multipliers for Java

ADMM4J is an implementation of ADMM algorithm in Java. It is devised to be able to run in parallel and distributed settings and being applicable to a wide range of problems. 

Note: Currently, only parallel implementation is available. Distributed implementation could be available in future.

To use ADMM4J the following steps need to be performed:

1. Devise a computation graph representing the problem as a bipartite graph
2. Implement nodes as Java classes extending org.admm4j.core.Node
3. Create the JSON input defining the graph
4. Execute admm4j (in Java environment or through command line)

At the heart there is a notion of node.

The org.admm4j.core.Node.java is an abstract class representing a node in a bipartite graph.\
This class implements ADMM specific functionality through its local variables and methods. 

An application specific node can be implemented by extending org.admm4j.core.Node.java.\
A minimal implementation requires overriding the _solve_ method specifing how a local subproblem is solved (Step 1 or 2 depending on whether the node is of type I or II).\
A specific input to the node can provided overriding _build_ method. This method is called before the start of optimization.\
Overriding the methods _evalObjective_ and _evalConstraintViolation_ allows to output the values of objective function and constraint violation in the results. Though they are optional.\
Additionaly, any specific information about this node can be returned overriding the _getJsonInternal_ method.

## Interface

ADMM4J accepts input and returns output in the form of JSON objects.

JSON format is used because:
1. It has a well defined structured that is easy to understand.
2. It provides a convenient way to address a broad range of problems with the same structure.
3. It is human readable.
4. It can be created manually as well as programmatically almost in any programming languages.
5. It is convenient for running in a distributed setting.

### Input

The following JSON schema describes input 



The nodesI and nodesII list JSON models of nodes in the computation graph.

In the input, JSON schema of node is



The fields are self-explonatory:
- name - the name of the node. All nodes in the graph should have different names.
- class - the full name of the Java class implementing the node.
- neighbors - list of nodes connected through edges with this node
- input - JSON object with additional input for this node, it can be null if the node has no input

### Output

The following JSON schema describes output 



The nodesI and nodesII list outcomes of optimization for nodes in the computation graph.

In the output, JSON schema of node is



The main information about results of optimization is given in _variables_ and _multipliers_ JSON objects.\
These contain corresponding values for each neighbor of the node.\
Examples of output files provide more insights.

# Example

Suppose the problem at hand is represented by the following graph 



The vectors $x$ and $z$ represent variables of the corresponding nodes.\
Edges represent shared variables and these should satisfy $x=z$.\
A node can have different number of shared variables with its neighbors.

The JSON model and input for admm4j would have the following form



#### Specifying neighbors

Each element in the array of neighbors follows the format __"name:nvar:rho"__
- name - name of the neighboring node (neighbor is the node with which there is an edge)
- nvar - number of shared variables with this neighbor
- rho - scaling parameter in ADMM algorithm 

In principle, the value of scaling parameter ($\rho$) can be different in the different parts of the computation graph. Though, this example uses rho=1 for all nodes.

Consider the node with the name "B".\
Its neighbors are specified by the array ["D:20:1", "E:10:1"]\
This means the node B has the nodes D and E as its neighbors, sharing 20 and 10 variables with each of them correspondingly. The scaling parameter rho is equal to 1 for all nodes.

See examples of input and output files for more details.

For modeling complex energy networks:

R. Denysiuk, F. Lilliu, M. Vinyals and D. Reforgiato Recupero (2020). Multiagent system for community energy management.\
*In Proceedings of the 12th International Conference on Agents and Artificial Intelligence - Volume 1: ICAART*, pages 28-39.


```python

```

a5f44d7d8f5b2e851f0657a89d42f6b4c71dc10d
ipynb
Jupyter Notebook
Tutorial.ipynb
romden/admm4j
178b4d5e12c9008a3d9881feefe4421a9915a5b8
MIT
Tutorial.ipynb
romden/admm4j
178b4d5e12c9008a3d9881feefe4421a9915a5b8
MIT
Tutorial.ipynb
romden/admm4j
178b4d5e12c9008a3d9881feefe4421a9915a5b8
MIT
Qwen/Qwen-72B
1. YES
2. YES