I am trying to minimize and $L_1$ problem with inequality constraints:
\begin{equation} ||Ax - b||_1 \;\text{subject to}\; x > c \end{equation} I believe the way to formulate this with ADMM is:
\begin{equation} \text{minimize}\; f(x) + g(z) \\ \text{subject to:}\; Ax - b - z = 0 \end{equation}
where $g(z)=|z|$ and $f(x)$ is and indicator function that is 0 when x > c and $\infty$ otherwise. The update steps are then: \begin{align} x&=argmin_x \; f(x) + 0.5\rho ||Ax - b - z + u||^2 \\ z&=S_{1/\rho}(Ax-b+u) \\ u&= u + Ax - z - b \end{align}
Where $S_{1/p}$ is the $L_1$ proximal operator. The x-update is the only one that differs from standard $L_1$ minimization with ADMM. To solve for the best x-update you can solve a quadratic program: \begin{equation} \text{let}\;d=b+z-u \\ \text{min} ||Ax -d||_2^2= x^TA^TAx - 2x^TA^Td + d^Td \\ \text{subject to:}\;x > c \end{equation}
Solving the problem this way does not yield a valid solution. I am using the ADMM solvers directly from the stanford website for solving the QP and modifying the L1 problem. Is there something wrong with my formulation? Is there an easier way to solve this problem?
It seems you omitted the step-size $\rho$ in the algorithm scheme. The augmented lagrangian of that problem has the form: \begin{equation} \mathcal{L}_p(x,z,u)=f(x)+g(z)+\langle u,Ax-z-b\rangle+\frac{\rho}{2}\Vert Ax-z-b\Vert^2_2 \end{equation}
If the algorithm doesn't converge, you might want to reformulate the problem with $\rho$ smaller than 1.