9
$\begingroup$

Consider a convex optimization problem (call it $P$). Consider its dual (call it $D$). Is it true that the dual of $D$ is $P$?

For linear programming, it is true. I'd just like to know under which conditions hold that the dual of the dual is the primal. References would also be appreciated.

Thanks

$\endgroup$
3
$\begingroup$

$\renewcommand{\Re}{\mathbb{R}}\newcommand{\<}{\langle}\newcommand{\>}{\rangle}\newcommand{\barre}{\bar{\Re}}$Let us first introduce the convex conjugate of an extended-real-valued convex proper function $f:\Re^n\to\barre$ which is a function $f^*:\Re^n\to\barre$ defined as

$$ f^*(y) = \sup_x \<x,y\> - f(y). $$

Given a (primal) optimization problem

$$ \mathsf{P}: \mathrm{Minimize}_{x\in\Re^n}\ f(x) $$

Its Fenchel dual is

$$ \mathsf{D}: \mathrm{Maximize}_{y\in\Re^n}\ -f^*(y) $$

and the second dual is

$$ \mathsf{P}': \mathrm{Minimize}_{x\in\Re^n}\ f^{**}(x) $$

In general $f^{**}\leq f$. In the context of Fenchel duality, your question is equivalent to asking under what conditions $f=f^{**}$.

Necessary and sufficient conditions are provided by the Fenchel-Moreau Theorem according to which it is necessary and sufficient that $f$ is proper, convex and lower semi-continuous (i.e., it has a closed epigraph).

Note that $f=f^{**}$ implies strong duality.

References:

  1. H.H. Bauschke and P.L. Combettes, Convex Analysis and Monotone Operator Theory in Hilbert Spaces, Springer, 2011.
  2. R.T. Rockafellar, Convex Analysis, Princeton University Press, 1970.

Update: In the case of Lagrangian duality where we consider problems of the form \begin{align} \mathrm{Minimize}_{x\in\Re^n} f(x)\\ \text{subject to}: x\in C, \end{align} where $f:\Re^n\to\Re$ is a convex function and $C$ is a nonempty convex set, we can write this as \begin{align} \mathrm{Minimize}_x F(x) := f(x) + \delta_C(x), \end{align} where $\delta_C$ is the indicator function of $C$ defined as \begin{align} \delta_C(x) = \begin{cases} 0,&\text{ if } x\in C,\\ +\infty,&\text{ otherwise} \end{cases} \end{align} The set $C$ is given by $C=\{x\in\Re^n: g(x) \leq 0\}$. The Lagrangian dual (where we "dualize" the the constraints by introducing a dual variable $y$ and a cost $\<y,g(x)\>$ and so on) is equivalent to the Fenchel dual.

Then, we may apply the above: the second dual is equivalent to the dual provided that $F^{**}=F$, so, if (By the Fenchel-Moreau Theorem) $F$ is proper, convex and lower semicontinuous. I'll leave it up to you to tell what this means for $f$ and $C$.

$\endgroup$
  • $\begingroup$ Thanks for your answer. Within the conditions of Fenchel-Moreau Theorem, we should have indeed that f=f^{**}. This should give a positive answer to my question in the case of Fenchel duality. However, I'm missing how this connects to the case of "standard" duality, that is the one I implicitely assumed in my question, even in the case where strong duality holds (which would say that the primal optimal objective and the dual optimal of the dual optimal objective are equal). PS: there should be a typo in the definition of the conjugate. $\endgroup$ – user52227 May 5 '17 at 11:14
  • $\begingroup$ @user52227 It goes along the same lines, but I will update my answer with details. $\endgroup$ – Pantelis Sopasakis May 5 '17 at 14:57
  • $\begingroup$ I don't see very well how the Lagrangian dual is equivalent to the Fenchel dual after the transformation you mentioned (if you can elaborate a bit more, I'd be glad!), in any case I trust you, thank you. $\endgroup$ – user52227 May 6 '17 at 11:51
  • $\begingroup$ I think this is explained very elegantly in littleO's answer to this question as well as in the Variational Analysis by Rockafellar and Wets. $\endgroup$ – Pantelis Sopasakis May 6 '17 at 21:42
2
$\begingroup$

The phenomenon in convex optimization that the dual of the dual problem is (usually) the same as the primal problem is seemingly a total surprise, and it is only rarely explained. But there's a nice, enlightening explanation that I learned from reading Ekeland and Temam. This material can also be found in the book Variational Analysis by Rockafellar and Wets, starting on p. 502.

The ideas are most clear when we work at an appropriate level of generality. We don't obtain a dual problem until we specify how to perturb the primal problem.

Suppose that the primal problem is $$ \operatorname{minimize}_x \,\phi(x,0), $$ where $\phi:\mathbb R^m \times \mathbb R^n \to \mathbb R \cup \{ \infty \}$ is a convex function. For a given $y$, the problem of minimizing $\phi(x,y)$ with respect to $x$ can be viewed as a "perturbed" version of the primal problem. Let's introduce the "value function" $h(y) = \inf_x \, \phi(x,y)$. So, the primal problem is to evaluate $h(0)$. If we have a basic understanding of the Fenchel conjugate, then we know that $h(0) \geq h^{**}(0)$, and typically $h(0) = h^{**}(0)$. The dual problem is simply to evaluate $h^{**}(0)$.

Let's try to write the dual problem more explicitly. First of all, \begin{align} h^*(z) &= \sup_y \, \langle y, z \rangle - h(y) \\ &= \sup_y \, \langle y, z \rangle - \inf_x \, \phi(x,y) \\ &= \sup_y \, \langle y, z \rangle + \sup_x - \phi(x,y) \\ &= \sup_{x,y} \, \langle x, 0 \rangle + \langle y, z \rangle - \phi(x,y) \\ &= \phi^*(0,z). \end{align} It follows that \begin{align} h^{**}(0) &= \sup_z \, \langle 0, z \rangle - \phi^*(0,z) \\ &= - \inf_z \, \phi^*(0,z). \end{align} So the dual problem, written as a minimization problem, is $$ \operatorname{minimize}_z \, \phi^*(0,z). $$ Look at the beautiful similarity between the primal and dual problems.

We did not obtain a dual problem until we specified how to perturb the primal problem. So, what if we now perturb the dual problem in the obvious way? A perturbed dual problem is $$ \operatorname{minimize}_z \, \phi^*(w,z). $$ Now that we have specified how to perturb the dual problem, we can obtain a dual for the dual problem, in exactly the same manner as above. And you can see immediately what the dual of the dual problem will be, without doing any work. The dual of the dual problem is: $$ \operatorname{minimize}_x \, \phi^{**}(x,0). $$ But typically we have $\phi^{**} = \phi$, in which case the dual of the dual problem is exactly the primal problem.


You might wonder how this dual problem construction connects to the standard dual problem construction (where you first form the Lagrangian, etc.). Suppose the primal problem is \begin{align} \text{minimize} & \quad f(x) \\ \text{subject to} & \quad g(x) \leq 0. \end{align} A perturbed problem is \begin{align} \text{minimize} & \quad f(x) \\ \text{subject to} & \quad g(x) + y\leq 0. \end{align} Having specified how to perturb the primal problem, we now obtain a dual problem, and if you work out the details it turns out to be exactly the dual problem that you would expect. I gave more details here:

Please explain the intuition behind the dual problem in optimization.

$\endgroup$
  • $\begingroup$ Thanks for your enormous effort. My question would have indeed a positive answer if we have $\phi^{**}=\phi$ as you write but at the end of your answer, if I understand correctly, you just say that this is "typically" true, i.e., without giving precise conditions. Or am I missing something? $\endgroup$ – user52227 May 5 '17 at 11:00

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.