Consider the Fenchel dual and the Lagrangian dual.

Are these duals equivalent? In other words, is using one of the these duals (say for solving an optimization), would give the same answer as using the other one?

I think the answer is no, but I am not sure. One reason for saying that, is that, in the Lagrange dual, we have a relatively straightforward way to add the constraints into the objective function. But what about the Fenchel? I have not seen any.

But I have seen some problems in which both of these give same answers. So, I would assume that, on a subset of problems, these two dualities, are exactly the same.

And also, if they are different, how would you choose which one to use on your problem?

  • 1
    It seems to me that you're making a category error here. A Fenchel dual is something you determine for a function, whereas a Lagrange dual is something you determine for a constrained optimization model. Can you give us a specific example of a "problem" that has both a Fenchel dual and a Lagrange dual? – Michael Grant Sep 28 '14 at 17:11
  • For example, Fenchel dual of hinge-loss – Daniel Sep 28 '14 at 17:33
  • Yeah, that is what I am saying. I think they are completely different creatures, although I am not sure if there is a direct link between them (and if so, how). – Daniel Sep 28 '14 at 17:34
  • 1
    "Fenchel dual of hinge-loss" What's the corresponding Lagrange dual here? My point is, they're not the same kind of thing. Lagrange and Wolfe duals, for instance, are the same kind of thing. Lagrange and Fenchel duals are not. It doesn't make sense to ask whether "using one of these duals... would give the same answer as using the other one". You say "you've seen problems in which both of these give the same answers." Please give us a complete example (both the Fenchel and Lagrange options). – Michael Grant Sep 28 '14 at 20:44
  • 2
    I see your point. I am convinced by your explanation. I'd accept it as answer if you write it as an answer. – Daniel Sep 28 '14 at 21:30

From your comments, I understand that your confusion is about the relation of Fenchel and Lagrange duality. So I will focus on that relation. Particularly, I would like to contradict the comment which stated, that Lagrange and Fenchel duality are two categorically different concepts.

Consider the primal problem $$\nu(0) = \inf_{x \in \mathbb R^n} \varphi(x,0) = \inf_{x \in \mathbb R^n} f(x)\text,$$ where $\varphi(x,u)$ is the perturbation function of $f$ with $\varphi(x,0) = f(x)$.

Using Fenchel conjugates, one can show that $$\nu^{\ast\ast}(0) = \sup_{p\in\mathbb R^m} -\varphi^\ast(0,p)\text,$$ which is known as the dual problem.

The relation $\nu^{\ast\ast} \leq \nu$ is known as weak duality, and it is immediately seen from $\nu^{\ast\ast}$ being the Fenchel biconjugate of $\nu$. The difference $\nu(0) - \nu^{\ast\ast}(0)$ is the famous duality gap. As you probably know, strong duality refers to the special case $\nu^{\ast\ast}=\nu$, which occurs if $f$ is convex and some other mathematical requirements are satisfied.

Why am I recalling all this? Because you should note, that all these concepts exist despite that we haven't even mentioned Lagrangians yet. These concepts are part of the Fenchel duality.

Now, consider the special case that $$f(x) = f_0(x) + g(F(x))$$ with the perturbation function $$\varphi(x,u) = f_0(x) + g(F(x) + u)\text,$$ such that $\varphi(x,0) = f(x)$ is still satisfied.

With $f_0 : \mathbb R^n \to \overline{\mathbb R}$, $g : \mathbb R^m \to \overline{\mathbb R}$, and $F : \mathbb R^n \to \mathbb R^m$, where $$\overline{\mathbb R} = \mathbb R \cup \{-\infty, +\infty\}$$ is the extension of the real line, this primal problem implicitly induces the feasibility set $\mathcal G = \{ x \in \operatorname{dom} f_0 : F(x) \in \operatorname{dom} g \}$, where $\operatorname{dom}$ denotes the effective domain, that is the set of arguments to a function, where the function is not infinity-valued.

By calculating the Fenchel conjugate $\varphi^\ast$, we obtain the dual problem $$\nu^{\ast\ast}(0) = \sup_{p \in \mathbb R^m} \inf_{x \in \mathbb R^n} L(x,p) - g^\ast(p) \text,$$ where $$L(x,p) = f_0(x) + \langle F(x), p \rangle$$ is called the Lagrangian.

Now, we specialize further. Consider the prominent case, that our primal problem was to minimize a convex function $f_0(x)$ with $\operatorname{dom} f_0 = \mathbb R^n$ subject to $f_i(x) \leq 0$ for all $i = 1, \dots, k$ and $f_i(x) = 0$ for the remaining i = $k+1, \dots, m$. Using the notation of an indicator function $$\delta_K(p) = \begin{cases} 0 & \text{if } p \in K \\ +\infty & \text{else,} \end{cases}$$ we can write the primal problem like $$\inf_{x \in \mathbb R^n} f_0(x) + \delta_K(F(x))\text,$$ where we set $g = \delta_K$, choose $F^{\mathsf T} = \begin{bmatrix}f_1, \dots, f_m\end{bmatrix}$, and $K = \mathbb R^k_- \times \{0\}^{m-k}$ correspondingly. Since the Fenchel conjugate of the indicator function of a closed convex cone $K$ equals to the indicator function of the polar cone $K^\ast$, that is, $\delta_K^\ast = \delta_{K^\ast}$, the dual problem reads $$\nu^{\ast\ast}(0) = \sup_{p \in \mathbb R^m} \inf_{x \in \mathbb R^n} L(x,p) - \delta_{K^\ast}(p) = \sup_{p \in K^\ast} \inf_{x \in \mathbb R^n} L(x,p)\text.$$

Note that by its formal definition, the the polar cone of $K = \mathbb R^k_- \times \{0\}^{m-k}$ $$K^\ast = \left\{ p \in \mathbb R^m \middle| \langle p,q \rangle \leq 0 \forall q \in K \right\}$$ translates to $$K^\ast = \left\{ p \in \mathbb R^m \middle| p_i \geq 0 \forall i = 1, \dots, k \right\} = \mathbb R^k_+ \times \mathbb R^{m-k} \text,$$ which are precisely the constraints that we have in mind, when we choose the Lagrangian multipliers, namely non-negative factors for the inequalities $f_1, \dots, f_k$ and arbitrary factors for the equality constraints $f_{k+1}, \dots, f_m$. Hence, our dual problem is to maximize $$\inf_{x \in \mathbb R^n} L(x,\left[\begin{smallmatrix}\lambda\\\mu\end{smallmatrix}\right]) = \inf_{x \in \mathbb R^n} f_0(x) + \sum_{i=1}^k \lambda_i f_i(x) + \sum_{i=1}^{m-k} \mu_i f_{k+i}(x)$$ w.r.t. the dual variables $\lambda \in \mathbb R^k$ and $\mu \in \mathbb R^{m-k}$, and subject to $\lambda \geq 0$.

So ultimately, we obtain the famous Lagrangian dual problem as a special case of Fenchel duality. To put it more precisely in view of your original question: Lagrangian duality is a result of Fenchel duality, the latter being a more general concept. Thus, of course, they are not equivalent.

  • @theVOID Do you have any favorite books for this type of material? – littleO Jul 6 '17 at 5:52
  • @littleO My explanation mostly followed lecture notes on convex analysis, which in turn are based on the famous, same-named book by Rockafellar. – theV0ID Jul 6 '17 at 19:43
  • @theVOID Thanks, are the lecture notes available online? If they are like a streamlined version of Rockafellar, that would be nice. – littleO Jul 6 '17 at 20:45

Let the fenchel dual of a function $f : \mathbb{R}^n \to \mathbb{R}$ be $D_f$. Consider the convex program $P^{+} = \min f(x)$ s.t. $x \ge \boldsymbol{0}$ and let $D_l$ be this program's lagrangian dual then for $\boldsymbol{\lambda} \ge \boldsymbol{0}$ $D_f(\lambda) = -D_l(\lambda)$. So on the positive orthant the fenchel dual agrees with the lagrangian dual of $P^{+}$.

Similarly on the negative orthant $D_f$ agrees with the dual of $P^{-} = \min f(x)$ s.t. $x \le \boldsymbol{0}$.

The general case is let $P^{A,b} = \min f(x)$ s.t. $Ax \le b$ and let $D_l^{A,b}$ be its dual, then for $\boldsymbol{\lambda} \ge \boldsymbol{0}$ $D_f(-A^T\boldsymbol{\lambda}) + D_l^{A,b}(\boldsymbol{\lambda}) + \boldsymbol{\lambda}^Tb=0$.

So the Fenchel dual is stitched together from lots of lagrange duals. Or conversely the lagrange dual of convex problems on polyhedrons can be constructed from the fenchel dual.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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