0
$\begingroup$

I would like to use ADMM for solving $Mx=b$, where $M\in \mathbb{R}^{R\times R}$ is symmetric and positive definite. I know that a lot of methods will do for me in this case, but I'm specially interested on using ADMM for this purpose. This is what I've done so far and why it fails.

The gradient decent method is convinient in my case and is based on the fact that the unique solution to

$$ \underset{x\in \mathbb{R}^R}{\min}\frac{1}{2}\langle Mx,x\rangle -\langle x,b\rangle$$

is precisely $\overline{x}:=M^{-1}b$.

For the same reasons, the optimization problem \begin{equation}\label{admm2} \begin{aligned} \min \frac{1}{2}\langle Mx,x \rangle -\langle b,z \rangle \\\text{s.a} \hspace{0.2 cm}x-z=0 \end{aligned} \end{equation} has a solution and is, again, $z^*=x^*=\overline{x}$. The form of the previous problem allows me to use ADMM and the functions involved implies that I will have convergence. The problem is that the $ k$th iteration step of the $ x$ variable involves solving the system $ Mx+\rho x=\rho z^k- y^k$ which is sad since if I could do that I wouldn't be using iterative methods.

The next idea I came up with is to use some other function and set $Mx=b$ on the restrictions but I'm not sure how to do this without excluding the $z$ variable. I'm not sure and I'm running out of ideas. Any suggestions on this? It would also be nice if someone knows for sure that this can't be done so I can give up happily.

PD: please don't suggest another iterative method that doesn't involves using ADMM.

$\endgroup$
  • $\begingroup$ First of all, the constraint you want to add is not $x=z$ but rather $Mx=z$. Secondly, standard ADMM has the drawback of not being explicit in one of its steps (as you have noticed). You should look at the proximal ADMM which circumvents this problem, see arxiv.org/pdf/1612.05057.pdf. $\endgroup$ – xel Apr 21 at 11:23
  • $\begingroup$ Also, it might be best if you include the definition of ADMM (as it may vary) in your question. $\endgroup$ – xel Apr 21 at 11:24

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.