# How to understand convex duality intuitively

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?

-
You might want to look here: or-exchange.org/questions/783/visualizing-the-dual-problem –  Michael Grant Apr 23 '13 at 20:17
Here is a relevant question (that includes my attempt to explain the intuition behind the dual problem in Convex Optimization). –  littleO Apr 21 at 22:50

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:

$$f^*(m) = \sup_x \quad \langle m, x \rangle - f(x).$$ ($\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$ $$f(x) = \sup_m \quad \langle m, x \rangle - f^*(m).$$ 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: $$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 \}.$$

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.

-