3
$\begingroup$

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

$\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.