I have the primal least-squares problem
$$\min_{w \in \mathbb R^p} \quad \frac{1}{2} \| y - Xw \|_2^2 + \sum_{i=1}^{d} h_i (w_i)$$
where $w_i$ are partitions of $w$, $w_i \in \mathbb R^{p_i}$, and $X_i$ denotes the corresponding columns in $X$. Let
$$h_i(w_i) = \max_{v \in D_i} \langle v, w_i \rangle$$
where set $D_i \subseteq \mathbb R^{p_i}$ is convex and closed. I need to prove the dual of this primal is a best approximation problem, namely,
$$\min_{u \in \bigcap_{i=1}^d C_i} \| y - u \|_2^2$$
where $C_i$ are inverse image of $D_i$ under ${X_i}^T$, or ${X_i}^T c \in D_i, c \in C_i$.
I don't know exactly how to convert a set constraint to a dual so I have no idea how to tackle this. Any help is appreciated. Thanks!
I found the solution of this. One needs to introduce two set of slack variables. Let $z = Xw$ substituting in the square part, $w^{'}_i = w_i$ substituting in the $h_i$ part. Then one can introduce the corresponding Lagrange multipliers $u$ and $v_i$. Note that the $h_i$ here is the support function of set $D_i$, whose conjugate function is the indicator function $I_{D_i}$. Take derivative wrt to $z$ yields result of $u = y - Xw$, take derivative wrt to $w^{'}_i$ yields $v_i \in D_i$ and take derivative wrt to $w_i$ yields $X_i^T u = v_i$. This concludes the proof.