Let us consider the convex optimization problem $$ \tag{P} \underset{x\in\mathbb R^n}{\sf minimize} ~~ f(x) ~+~ g({\bf L}x) $$ where ${\bf L}\in\mathbb R^{m\times n}$. Using the convex conjugate, the corresponding dual problem can be written as $$ \tag{D} \underset{y\in\mathbb R^m}{\sf minimize} ~~ f^\star(-{\bf L}^{\!\sf T}y) ~+~ g^\star(y) $$ The quantity ${\bf L}x$ can be somehow interpreted as a feasibility residual (I am thinking of the case $g=\delta_{\{b\}}$ so that it embodies the linear equality constraints ${\bf L}x=b$), but what is the meaning of the quantity ${\bf L}^{\!\sf T}y$, and what is the information that it gives in terms of optimality/feasiblity?
I know that if $(x^\star,y^\star)$ is a primal-dual pair, then it satisfies the optimality conditions
- $-{\bf L}^{\!\sf T}y^\star \in \partial f(x^\star)$
- $y^\star \in \partial g({\bf L}x^\star)$
but I still don't get the role of ${\bf L}^{\!\sf T}y$.
Thanks for your help.
Technically, D is not the dual of P. P has no constraints, so its true dual is $$\begin{array}{ll} \text{maximize} & p^* \end{array}$$ where $p^*\triangleq \inf_x f(x)+g(Lx)$ is a (possibly infinite) constant. That's right: the dual has no variables. Needless to say it's somewhat useless.
D is actually the dual of $$\begin{array}{ll} \text{minimize}_{x,w} & f(x) + g(w) \\ \text{subject to} & L x = w \end{array}$$ The role of $y$, then, is to serve as the Lagrange multiplier of $Lx=w$. I'm not sure if there's a good alternative interpretation that doesn't involve the equality constraints.