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!

  • $\begingroup$ 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). $\endgroup$ – Gabriel Romon May 21 at 8:41
  • $\begingroup$ 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. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.