Distributed optimization problem

Question

Consider the following optimization problem: \begin{equation} \label{eq:1} \min_{x\in\mathcal X} \max_{i\in\mathcal I}\sum_{j\in\mathcal J} f_i(x_{(j)}), \end{equation} where $\mathcal{I}$ and $\mathcal{J}$ are discrete and finite sets, $\mathcal X\subset \mathbb{R}^N$ is a compact set, $(f_i)_{i\in\mathcal J}$ are convex and differentiable functions, and $x_{(j)}$ is a subvector of the global variable $x$. Note that $x_{(j)}$ and $x_{(j')}$ for $j,j'\in\mathcal J$ may overlap.

For example $x = (x_1,x_2,x_3)$, $x_{(1)} = (x_1,x_2)$ and $x_{(2)} = (x_2,x_3)$.

I am investigating whether there is a way to solve this problem in a distributed manner. Note that the problem, without the term "$\max_{i}$", is known as the general form consensus problem and is solved nicely by ADMM (see Boyd et al. Sec. 7.2).

Unfortunately, the term "$\max_{i}$" seemingly makes the problem non-separable, and the active index, i.e., the index $i^\star(x)\in\mathcal I$ which attains the maximum, cannot be computed in a decentralized way.

Is there an algorithm to separate the variable update steps for the problem above and apply an ADMM-like (or similar) algorithm in a decentralized way over $j\in\mathcal J$?

Update: I have found this monograph (Sec. 7.5) in which there is a problem of the type $$ \min_{x\in\mathcal X} \varphi(f_1(x),\dots,f_J(x)), $$ where $\varphi(\cdot)$ is a convex non-decreasing function.

Then they formulate the problem in epigraph form and propose a method to solve it. Any idea on whether this method will work in my case?

Answer 1

The problem could be written as $$ \begin{array}{rll} \mbox{minimize} &u\\ \mbox{subject to} & u \geq \sum_{j\in J}f_i(x_{(j)}) &i\in I \end{array} $$ which is much more similar to the consensus form. Introducing $u_i$ and $x_i$, we got $$ \begin{array}{rll} \mbox{minimize} &u\\ \mbox{subject to} & u_i \geq \sum_{j\in J}f_i(x_{i(j)}) &i\in I\\ &u_i=u &i\in I\\ &x_i=x &i\in I \end{array} $$ Then we are ready to use ADMM. The argumented Lagrange is $$ L(x,x_i,u,u_i,y_i,v_i)=u+\sum_i\left[v_i(u_i-u)+\rho/2(u-u_i)^2+y_i^T(x_i-x)+\rho/2\|x-x_i\|_2^2+\mathbb{I}\left(u_i\geq \sum_{j\in J}f_i(x_{i(j)})\right)\right] $$

The ADMM algorithm is $$ \begin{align} u_i^{k+1},x_i^{k+1}&= \arg\min\{v^k_i(u_i-u^k)+\rho/2(u^k-u_i)^2+y_i^{kT}(x_i-x^k)+\rho/2\|x^k-x_i\|_2^2,\;\mathrm{s.t.}\; u_i\geq \sum_{j\in J}f_i(x_{i(j)})\}\\ u_{k+1}&=\frac{\sum_i(\rho u_i^{k+1}+v_i^k)-1}{N\rho}\\ x_{k+1}&=\frac 1 N \sum_i(x_i^{k+1}+(1/\rho)y_i^k)\\ v_i^{k+1}&=v_i^k+\rho(u_i^{k+1}-u^{k+1})\\ y_i^{k+1}&=y_i^k+\rho(x_i^{k+1}-x^{k+1}) \end{align} $$