Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Is there an intuitive way to understand the convex duality? If the primal problem is minimization, the dual is maximization over another set of variables - but I would love to have a geometric visualization of this and an intuitive way to understand why this ought to be true. I'd also want to see strong duality present in such an intuition.

Textbooks are dense in the math, but I haven't come across a place where this could be imagined in our minds without variables and equations. Could someone here help me out?

share|improve this question
    
You might want to look here: or-exchange.org/questions/783/visualizing-the-dual-problem –  Michael Grant Apr 23 '13 at 20:17
add comment

1 Answer

This isn't what was asked, but there's nice intuition for the fact that if $f$ is a closed convex function, then $f^{**} = f$. (Here $f^*$ is the convex conjugate of $f$.)

I think the source of all duality results in convex analysis is the fact that a closed convex set $C$ is the intersection of all closed half spaces that contain $C$.

If we apply this idea to the epigraph of a closed convex function $f$, we see that $f$ is the supremum of all affine functions that are majorized by $f$.

For any given slope $m$, there may be many different constants $b$ such that the affine function $\langle m, x \rangle - b$ is majorized by $f$. We only need the best such constant.

That's what the convex conjugate $f^*$ does for us. Given a slope $m$, $f^*$ returns the best constant $b$ such that $\langle m, x \rangle - b$ is majorized by $f$. And (clearly) the best choice of $b$ is:

\begin{equation} f^*(m) = \sup_x \quad \langle m, x \rangle - f(x). \end{equation} ($\langle m, x \rangle$ exceeds $f(x)$ by at most $f^*(m)$, so $\langle m, x \rangle - f^*(m)$ exceeds $f(x)$ by at most $0$.)

From this perspective it's immediate that for any $x$ \begin{equation} f(x) = \sup_m \quad \langle m, x \rangle - f^*(m). \end{equation} And this says that $f(x) = f^{**}(x)$.

Here there was a natural way to associate a closed convex set with the function $f$, and it led to a duality result. Is there a similar way to associate a closed convex set with a convex optimization problem, and obtain a duality result for convex optimization problems?

If the optimization problem is: \begin{align} \operatorname*{minimize}_x &\quad f(x) \\ \text{subject to} & \quad Ax = b \\ & \quad h_i(x) \leq 0 \quad \text{for } i = 1,\ldots, m \end{align} where $f$ and $h_i,i=1,\ldots, m$ are closed convex functions, then we can associate an "epigraph" to this convex optimization problem as follows: \begin{equation} C = \{ (u,v,t) \mid \exists \, x \,\text{such that } f(x) \leq t, Au = b, h_i(x) \leq v_i \text{ for } i = 1,\ldots,m \}. \end{equation}

By thinking of $C$ in terms of closed half-spaces that contain $C$, or in terms of hyperplanes that support $C$, we can get a geometric interpretation of the dual problem, and a nice proof of a strong duality theorem.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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