# Regularized least squares program and best approximation problem

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!

• Usually one considers the dual of a problem where there are equality and inequality constraints. However I don't see any constraints in your primal (except that each $h_i(w_i)$ must be finite). – Gabriel Romon May 21 at 8:41
• Yes that's the part also confuses me. I guess this may not be a direct dual conversion. Before that one may need to introduce a slack variable for $h_i$. My thought is replace $h_i$ with a slack variable $t_i$ and add in unequality constraint $t \geq <v, w_i>$ for all $v \in D_i$. Then one can apply the dual transform. That doesn't seem to solve the problem though. – JC Wang May 21 at 20:53

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.