# ADMM fails to converge on convex problem. Are there any tricks of trade for application?

## Convex Problem

I am trying to solve the semidefinite program:

$\min y$ (Objective, 0)

subject to

$y\geq0$ (Nonnegative, 1)

$y I + \Sigma_0 = \sum^{n}_{i=1} x_i \Sigma_i + Z$ (Linear Equality,2)

$x_i\geq0,\sum^{n}_{i=1} x_i =1$ (Simplex,3)

$Z\succeq0$ (SPD,4)

where $I$ is the identity-matrix and $\Sigma_i$ spd matrices

by the Alternating Direction Method of Multipliers (ADMM).

## Algorithm

Following Stephen Boyds formulation in https://stanford.edu/~boyd/papers/pdf/prox_algs.pdf page 153 I implemented ADMM by iterating

$(x,y,Z)'=prox_{\lambda\,(0,1,3,4)}((x,y,Z)-u)$

$(x,y,Z)=prox_{\lambda\, (2)}((x,y,Z)'+u)$

$u=u+(x,y,Z)'-(x,y,Z)$

This can be done efficiently. The reason is that $prox_{\lambda\,(2)}((x,y,Z)'+u)$ is a linear affine projection and that $prox_{\lambda\,(0,1,3,4)}((x,y,Z)-u)$ can be separately evaluated for each of the three $x,y,Z$:

• By projection of $Z-u_{Z}$ on the SPD-cone (4)
• By projection of $x-u_{x}$ on the simplex (3)
• By solving $prox_{\lambda\,(0,1)}$ for $y-u_{y}$ (0,1) .

## Results

On random matrices, the algorithm works sort of okay-ish. However, in my application ADMM totally fails to converge (for most of fixed $\lambda$) and is way off the optimal solution (computed by cvx). I know that ADMM is a first-order method that can take several iterations to convergence but this was unexpected.

## Question

Are there important tricks of trade to know for application of ADMM, that can help to obtain a convergent algorithm? Or is the algorithm I sketched simply no proper ADMM instance? Or may I have encountered a pathological (2) (the matrices $\Sigma$ have a non-trivial yet joint null-space)?