[Math] Geometric interpretation of duality and Slater’s condition

convex optimizationlagrange multipliermultivariable-calculusoptimization

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:

enter image description here

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.

Best Answer

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.

Related Question