Let us assume for simplicity that , and consider the problem:
In fact, this can be done without loss of generality, using the pointwise maximum of the constraints as a single constraint.
To illustrate, we focus on the problem above, with defined as
A one-dimensional problem: the picture shows the problem above, which is to minimize a fifth-order polynomial on the domain , with one fourth-order polynomial constraint. The constraint expresses the fact that should belong to the union of two intervals (region in light blue). The optimal point is shown (in green on the -axis).
We can express the primal problem with two new scalar variables , as follows:
The set can be interpreted as the set of pairs that can be upper bounds on constraint / objective function pairs, by some choice of the original decision variable . The set corresponds to pairs that are achievable by some that is feasible for the original problem.
Two-dimensional representation of the problem above: The line in blue is the set of points of the form when runs . The set (blue and darker blue) is constructed as follows: for any point on the line, include all points that are to the upper right quadrant from that point (we show an example, in light green).
The part of in darker blue, which is , corresponds to . The fatter part of the blue line (which is inside corresponds to the points that are feasible for the original problem. The optimal value of the original problem, , in the smallest value of that can be achieved inside .
The dual function is
In the scalar problem above, the dual function is easy to compute, either by a direct (brute force) scan of values in , or by taking derivatives of the above objective function, and roots of a -th order polynomial.
The geometric interpretation of is a follows. We have
Consider a non-vertical line in plane, with non-positive slope given by . This line can be expressed as where the value of the constant is the intercept, that is, the point on the line on the -axis.
Dual function for the problem above: We plot the line , where , for . The value of is corresponds to the line which has the smallest intercept , and intersects the set . We check on the plot that is a lower bound on the optimal value, irrespective of the value of the downward slope .
The dual problem:
amounts to finding the best line, that is, search for slopes that achieves the highest intercept. It corresponds to replacing with its convex hull.
Dual problem for the problem above: The dual problem is to find the line of the form intercepting and producing the smallest intercept . The optimal dual value, , is that largest intercept; in our case, the optimal dual variable is . In this problem, there is a duality gap, in the sense that . This is the case for most non-convex problems.