Reformulating a Dual Problem

59 Views Asked by At

Let the following dual problem be given:

$$\sup_{p}\inf_{z, w, b}\left\{ J(z) + \frac{\alpha}{2}\vert\vert w\vert\vert^2 - \langle p, A^T w - yb - z\rangle \right\} \qquad (\mathcal D),$$

where $w\in \mathbb R^n$, $y\in \mathbb R^m$, $b\in \mathbb R$, $J: \mathbb R^m \rightarrow \mathbb R_{\infty}$ is a proper, closed, convex function, $\alpha > 0$ and matrix $A\in \mathbb R^{n\times m}$ with $A := \left[ y_1x_1, \dots, y_m x_m \right]$. In an exercise, we're supposed to show that the above Eq. $(\mathcal D)$ equals the following: $$-\min_{p\in \left(\mathbb R^{m}\right)^{\star}}\left\{ J^{\star}(-p) + \frac{1}{2\alpha}\vert\vert Ap\vert\vert_{2}^{2} \right\} \qquad \text{such that $p^T y = 0$},$$ where $J^{\star}$ refers to the Fenchel conjugate, i.e. $J^{\star}(-p): (\mathbb R^m)^{\star}\rightarrow\mathbb R_{\infty}$, $-p\mapsto \sup_{v\in \mathbb R^m} \left\{ \langle -p \vert v\rangle - J(v) \right\}$. The space $\left(\mathbb R^m\right)^{\star}$ refers to the dual space. I did plug this into the second expression with the $\min$, and using that $\sup\left\{ r\cdot A \right\} = r\cdot \inf\{A\}$ (cf. Wikipedia, $r \leq 0$), then we get that $$-\min_{p}\left\{ J^{\star}(-p) + \frac{1}{2\alpha}\vert\vert Ap\vert\vert_{2}^{2} \right\} = -\min_{p}\left\{ -\inf_{v}\left\{ \langle p \vert v\rangle + J(v)\right\} + \frac{1}{2\alpha}\vert\vert Ap\vert\vert_{2}^{2}\right\} \overset{!}{=} \\ \sup_{p}\inf_{z, w, b}\left\{ J(z) + \frac{\alpha}{2}\vert\vert w\vert\vert^2 - \langle p, A^T w - yb - z\rangle \right\} $$

But I am not sure how to prove the last equality, because it seems to me in the expression that we're supposed to prove.