Let us a consider the problem
where f and g are convex. Let denote the constrained minimizer and .
The dual function is defined as , and given appropriate conditions, we have . Why is that?
Let’s plot all the possible values that (g(x), f(x)) can take for every point in the domain. This gives us a 2-dimensional shape in . But obviously, for optimization purposes we can ignore the bulk of the points in this curve and focus on the lower boundary, orenvelope.
Now, the problem is to find the minimum value that f(x) can possible take given that g(x) is less than or equal to zero. As you can see, this corresponds to the point circled in the graph, which is located at .
Now consider adding to . To do this, we add a line to the above graph.
The black line is the envelope of (g(x), f(x)) and the blue line is the plot of . Now, plot for a particular .
As you can see, adding has the effect of “tilting” the curve. Let us plot for several values of :
Each of the colored lines is for a different value of . But what do we notice? The circled red point, corresponding to the constrained minimum, remains unaffected! In hindsight, this is obvious because , therefore is independent of .
Now, because every curve passes through the circled red point , the minimum of that curve must always be equal to or less than .
In order to get the correct answer, we have to find so that the colored curve is minimized at the circled red point. In order to do this, we have to tilt the function just right, so that the curve is flat at the circled red point. This also maximizes the dual function.