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).


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\, (2)}((x,y,Z)'+u)$


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) .


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.


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)?


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.