0
$\begingroup$

I would like to solve the following projection problem utilizing some FAST first-order methods, e.g., Consensus ADMM or DR, etc.

\begin{align} x^* = \arg \min_{x \in \mathbb{R}^N} \Vert y - x\Vert^2 \ \text{ s.t. } x \in \bigcap_{i=1}^m C_i \ , \end{align} where $y \in \mathbb{R}^{N \times 1}$ and example, $C_i = \left\{x : a_i^T x \leq b\right\}$. For my case, the sets are convex.

I played with consensus ADMM (borrowed a recipe from an article) for the above example where $C_i = \left\{x_i : a_i^T x_i \leq b_i\right\}$, but the number of iterations to converge are really long. I also noticed some suggestion here, but I couldn't derive the Douglas-rachford suggestion (in fact I got stuck because my mathematics is not strong. So please excuse me). However, I can implement the other solution steepest descent (SD) though. This SD has also the same problem as ADMM that it takes so many iterations to converge (e.g., more than 1000 iterations :( ).

Questions:

  1. I am interested in deriving the consensus DR suggestion here.Can you help me?

  2. Also, do you have any suggestions to consider some FAST first order methods? (using some black box solvers, e.g., CVX,


Looking at the proposal here, I have pasted function splitting below for convenience

\begin{align*} \text{minimize} & \quad \underbrace{\|y - x \| + \sum_i \delta_i(x_i)}_{f(x_0,x_1,\ldots,x_m)} + \underbrace{\delta_S(x_0,x_1,\ldots,x_m)}_{g(x_0,x_1,\ldots,x_m)} \end{align*} where \begin{equation} S = \{(x_0,x_1,\ldots,x_m) \mid x_0 = x_1 = \cdots = x_m \} \end{equation} and $\delta_S$ is the indicator function of $S$. The variables in this reformulated problem are the vectors $x_0,x_1,\ldots,x_m$. The indicator function $\delta_S$ is being used to enforce the constraint that all these vectors should be equal.

Following the comments in the same link, the prox operators are

$(\overline{x}, \overline{x}, \cdots, \overline{x}) = {\rm prox}_g\left(x_1, x_2, \cdots, x_m\right) ,$ where $\overline{x} = \frac{1}{m} \sum_i x_i$.

if $C_i = \left\{x_i : a_i^T x_i \leq b_i \right\}$, then the prox operator is

\begin{align*} P_{{C_i}}\left(x_i\right) = \left\{ \begin{matrix} x_i + \frac{\left(b_i - a_i^{T} x_i \right)}{\left\|a_i\right\|_2^2} a_i, & \text { if } a_i^{T} x_i > b_i; \\ x_i, & \text { if } a_i^{T} x_i \leq b_i. \end{matrix} \right. \end{align*}

Now I have both prox operators, then my problem is how to plug it in the DR routine (sorry if it is obvious for you)

\begin{align} x^{(t)} &= {\rm prox}_f(z^{(t-1)}) \\ z^{(t)} &= z^{(t-1)} + {\rm prox}_g(2x^{(t)}-z^{(t-1)}) - x^{(t)} \end{align}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.