13
$\begingroup$

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?

$\endgroup$
10
$\begingroup$

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.

$\endgroup$

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.