$\min_{\beta_1,...,\beta_3,\beta}\sum_{i=1}^{3}\frac{1}{2}||y_i-X_i\beta_i||_2^2+\lambda||\beta||_1$ in augmented Lagrangian form

39 Views Asked by At

Write $\min_{\beta_1,...,\beta_3,\beta}\sum_{i=1}^{3}\frac{1}{2}||y_i-X_i\beta_i||_2^2+\lambda||\beta||_1$ in augmented Lagrangian form. s.t. $\beta_1=\beta_2=\beta_3=\beta$

Augmented Lagrangian is defined as:
$L(x,u;p)=f(x)+u^T(Ax-b)+\frac{p}{2}||Ax-b||_2^2$

$f(x)=\sum_{i=1}^{3}\frac{1}{2}||y_i-X_i\beta_i||_2^2$
$g(x)=\lambda||\beta||_1$

I'm not entirely sure where to go from here. My guess of solution is:

$$\min_{\beta_1,...,\beta_3,\beta}\sum_{i=1}^{3}\frac{1}{2}||y_i-X_i\beta_i||_2^2+\lambda||\beta||_1+\frac{p}{2}||(\beta_1-\beta) + (\beta_2-\beta) + (\beta_3-\beta)||_2^2$$ or perhaps the constraints have to be separated $$\min_{\beta_1,...,\beta_3,\beta}\sum_{i=1}^{3}\frac{1}{2}||y_i-X_i\beta_i||_2^2+\lambda||\beta||_1+\frac{p}{2}(||(\beta_1-\beta)||_2^2 + ||(\beta_2-\beta)||_2^2 + ||(\beta_3-\beta)||_2^2)$$

1

There are 1 best solutions below

0
On BEST ANSWER

For a problem of the form: $$\tag{1}\min_{\mathbf{x}, \mathbf{z}} f(\mathbf{x}) + g(\mathbf{z}) \\ s.t.: A\mathbf{x}+B\mathbf{z}=\mathbf{c}$$ we construct the augmented Lagrangian: $$\mathcal{L}_\rho(\mathbf{x},\mathbf{z},\mathbf{y})=f(\mathbf{x})+g(\mathbf{z})+\mathbf{y}^T(A\mathbf{x}+B\mathbf{z}-\mathbf{c})+\frac{\rho}{2}\|A\mathbf{x}+B\mathbf{z}-\mathbf{c}\|^2.$$ This could almost fit your model, by setting \begin{aligned}&A=I,\;\mathbf{x}=(\beta_1,\beta_2,\beta_3)^T\\&B=-I,\mathbf{z}=(\beta,\beta,\beta)^T\\& \mathbf{c}=\mathbf{0}.\end{aligned} However, your $f(\cdot)$ component has a linear transformation. So in fact, your problem is $$\min_{\mathbf{x}, \mathbf{z}} f(\mathbf{Ax}) + g(\mathbf{z}) \\ s.t.: \mathbf{x}-\mathbf{z}=\mathbf{0}.$$ We can still follow this framework and construct the augmented Lagrangian: $$\mathcal{L}_\rho(\mathbf{x},\mathbf{z},\mathbf{s})=\frac{1}{2}\|A\mathbf{x}-\mathbf{y}\|^2+\frac{\lambda}{3}\|\mathbf{z}\|_1+\mathbf{s}^T(\mathbf{x}-\mathbf{z})+\frac{\rho}{2}\|\mathbf{x}-\mathbf{z}\|^2.$$ The question is what do you plan to do next. The above formulation is without doubt the augmented Lagrangian. But general ADMM frameworks that are proven to converge to an optimal solution are designed to fit problem $(1)$. Your problem is somewhat different, therefore a generic ADMM algorithm might not work.