4

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.

AndreasT
  • 3,772

1 Answers1

5

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.

Michael Grant
  • 19,450
  • Thanks for your answer. I got what you mean with your technicality and I totally agree. Then again, if (P) is actually the problem with the equality constraints and, say, I am using an iterative primal-dual algorithm, I am still wondering what I can infer from the vector ${\bf L}^{!\sf T}y^k$. Would it be any different assuming $g=\delta_{{b}}$ be the characteristic function of a singleton? – AndreasT Oct 17 '14 at 01:02
  • Well, I guess you're asking what the general purpose of duality is, really. One interepretation is that if $b$ is changed slightly to $b+\delta b$, where $|\delta b|\ll b$, then the objective will change by $\langle \delta b,y\rangle$. I would suggest consulting general convex optimization texts for more information about the interpretation of dual information. – Michael Grant Oct 17 '14 at 03:20