Geometric interpretation of duality and Slater's condition

Question

I am trying to study about optimization problems, Lagrange duality and related topics. I came across some presentation on the net, which claims to show the geometric interpretation of the duality and Slater's condition for a simple problem with only a single constraint :

$$\begin{equation*} \begin{aligned} & \underset{x}{\text{minimize}} & & f_0(x) \\ & \text{subject to} & & f_1(x) \leq 0. \end{aligned} \end{equation*}$$

Here is the following slide:

Now, I understand how $p^*$ is depicted: Primal problem has a constraint $f_1(x) \leq 0$ and we only consider negative $u$ values therefore. The point $(u,t)$ with the minimum $t$ value is picked where $u \leq 0$.

But I completely don't understand how I should interpret the dual function $g(\lambda)$ to begin with. $g(\lambda)$ is depicted as a line (hyperplane). But according to the definition of $g(\lambda)$ it must be a scalar value. The dual problem is $g(\lambda) = \inf_x(f_0(x) + \lambda f_1(x))$ where $\lambda \geq 0$. So, for a given $\lambda \geq 0$ we must go and seek a $(u,t)$ point in $G$ which minimizes $g(\lambda)$. How is this connected with a hyperplane to begin with? We are in $(u,t)$ space, which has no $\lambda$ parametrization in it. I direly need some clarifications here.

Answer 1

See lecture 8 of Stanford course convex optimization. At time 1.04 (one hour and 4 minutes from start) Stephen Boyd start explaining the geometric interpretation.

http://www.youtube.com/watch?v=FJVmflArCXc

You also have his book (free from his web site) with more formal details.

Answer 2

As you said $g(\lambda)$ for a given $\lambda$ is a scalar. Suppose $\lambda = 3$ and $g(\lambda) = 5$. That defines the line $3u+t=5$. The dual is $5$ (not $3u+t=5$). The intercept of $3u+t=5$ line is $5$ which is $g(\lambda)$. You get the dual function by varying the $\lambda$s (must be nonnegative). Therefore, the dual function defines a family of lines; find the largest intercept among all. That is $d^*$ which satisfies $d^* \leq p^*$ according to weak duality. In case there is more than one constraint you no longer have supporting lines but supporting hyperplanes.

In summary, the lines are not the duals. A dual (which is a scalar) helps to define the line.

Answer 3

A key idea in convex analysis is to think of a set (such as $\mathcal G$) in terms of the half-spaces that contain it.

For a given $\lambda$, you could imagine all the hyperplanes of the form $\lambda u + t = \text{const}$ for which $\mathcal G$ is contained in the upper half space.

And what is the "best" choice of the constant on the right hand side?

The "best" choice is $g(\lambda)$, because that is the largest constant such that $\mathcal G$ is contained in the upper half space of $\lambda u + t = \text{const}$.

So, you can think of $\lambda u + t = g(\lambda)$ as being a hyperplane for which $\mathcal G$ is contained in upper half space. Moreover, for this value of $\lambda$, this is the "best" hyperplane, in the sense that the containment is as tight as possible. If you shifted this hyperplane up any higher, containment would be violated.