How to Solve ADMM Optimization Problem

15 Views Asked by At

We are trying to solve the following Optimization Problem

$$ \begin{aligned} & \min _{\left\{y_{i j}^{m}\right\}} \sum_{i \in I_{m}} f_{i j}^{m}\left(y_{i j}^{m}\right)+\sum_{j \in J} \Phi^{m}\left(z_{i j}^{m}\right) \\ & \text { subject to } y_{i j}^{m}-z_{i j}^{m}=0 \quad \forall i, j, m \end{aligned} $$

where $\Phi^{m}\left(z_{i j}^{m}\right)=\mathbb{I}_{c}\left(z_{i j}^{m}\right)$ is an indicator function and the global variable $z_{i j}^{m}$ represents the resource allocation decision of each link.

Now, the problem is separable and can be solved using ADMM. The augmented Lagrangian of the problem is defined as follows:

$$ \begin{aligned} & L_{p}\left(y_{i j}^{m}, z_{i j}^{m}, \theta_{i j}^{m}\right)=\sum_{i \in I_{m}} f_{i j}^{m}\left(y_{i j}^{m}\right) \\ & +\sum_{j \in J} \Phi^{m}\left(z_{i j}^{m}\right)+\sum_{i \in I_{m}, j \in J} \theta_{i j}^{m}\left(y_{i j}^{m}-z_{i j}^{m}\right) \\ & +\frac{\rho}{2} \sum_{i \in I_{m}, j \in J}\left(y_{i j}^{m}-z_{i j}^{m}\right)^{2} \end{aligned} $$

The ADMM iterations are formulated as follows:

$$ \begin{aligned} y_{i j}^{m(t+1)}= & \operatorname{argmin}\left\{f_{i j}^{m}\left(y_{i j}^{m}\right)+\sum_{j \in J} \theta_{i j}^{m(t)} y_{i j}^{m}\right. \\ & +\frac{\rho}{2} \sum_{j \in J}\left(y_{i j}^{m}-z_{i j}^{m(t)}\right)^{2} \\ z_{i j}^{m(t+1)}:= & \operatorname{argmin}\left\{\Phi^{m}\left(z_{i j}^{m}\right)-\sum_{i \in I_{m}} \theta_{i j}^{m(t)} z_{i j}^{m}\right. \\ & \left.+\frac{\rho}{2} \sum_{i \in I_{m}}\left(y_{i j}^{m(t+1)}-z_{i j}^{m}\right)^{2}\right\} \end{aligned} $$

and

$$ \theta_{i j}^{m(t+1)}=\theta_{i j}^{m(t)}+\rho\left(y_{i j}^{m(t+1)}-z_{i j}^{m(t+1)}\right) $$

MY QUESTION:

1)

$\Phi^{m}\left(z_{i j}^{m}\right)=\mathbb{I}_{c}\left(z_{i j}^{m}\right)$ is an indicator function. The indicator function takes a value of either 0 or 1.

How should we define the function $\Phi^{m}\left(z_{i j}^{m}\right)$?

In the equation where we update $z_{ij}^{m(t+1)}$, we have to use $\Phi^{m}\left(z_{i j}^{m}\right)$. Now, if $\Phi^{m}\left(z_{i j}^{m}\right)$ takes a value of either zero or one how we are going to carry out the gradient ascent procedure?