Geometric View of Weak Duality

Weak Duality > Dual problem | Geometry | Minimax Inequality

Two-dimensional view of the primal problem

Let us assume for simplicity that m=1 , 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 f_0,f_1 defined as

$f_0(x) := left{ begin{array}{ll} begin{array}{l} 0.0025x^5-0.00175x^4-0.212625x^3+0.3384375x^2+3.368x-1.692 end{array} & -10 le x le 10, +infty & mbox{otherwise,} end{array} right.$

f_1(x) :=0.0025x^4-0.0005x^3-0.2129x^2+0.0320x+3.5340.

A one-dimensional problem: the picture shows the problem above, which is to minimize a fifth-order polynomial on the domain [-10,10] , with one quadratic 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 u,t , as follows:

$begin{array}{rcl} p^ast &=& displaystylemin_{u,t,x} : left{ t ~:~ 0 ge u ge f_1(x), ;; t ge f_0(x) right} &=& displaystylemin_{u,t} : t ~:~ (u,t) in mathbf{A}_{rm feas}, end{array}$

where

$begin{array}{ll} mathbf{A} :=& left{ (u,t) in mathbf{R}^2 ~:~ exists : x , ;; u ge f_1(x), ;; t ge f_0(x) right}, mathbf{A}_{rm feas} :=& left{ (u,t) in mathbf{A} ~:~ u le 0 right}. end{array}$

The set mathbf{A} can be interpreted as the set of constraint / objective pairs (u,t) that can be achieved by some choice of the original decision variable . The set $mathbf{A}_{rm feas}$ 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 (u,t)=(f_1(x),f_0(x)) when runs [-10,10] . The set mathbf{A} (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 mathbf{A} in darker blue, which is $mathbf{A}_{rm feas}$ , corresponds to ule 0 . 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, p^ast , in the smallest value of that can be achieved inside $mathbf{A}_{rm feas}$ .

Dual function

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 [-10,10] , or by taking derivatives of the above objective function, and roots of a -th order polynomial.

The geometric interpretation of g(y) is a follows. We have

$g(y) = min_{u,t} : t + y u ~:~ (u,t) in mathbf{A}.$

Consider a non-vertical line in (u,t) plane, with non-positive slope given by -yle 0 . 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 t = g(y) - yu , where g(y) = min_x f_0(x)+ yf_1(x) , for y=1 . The value of g(1) is corresponds to the line t = g-u which has the smallest intercept , and intersects the set mathbf{A} . We check on the plot that g(y) is a lower bound on the optimal value, irrespective of the value of the downward slope -yle0 .

Dual problem

The dual problem:

$d^ast := max_{y ge 0} : g(y),$

amounts to finding the best line, that is, search for slopes y ge 0 that achieves the highest intercept. It corresponds to replacing mathbf{A} with its convex hull.

Dual problem for the problem above: The dual problem is to find the line of the form t = g-uy intercepting mathbf{A} and producing the smallest intercept . The optimal dual value, d^ast , is that largest intercept; in our case, the optimal dual variable is y^ast approx 2.15 . In this problem, there is a duality gap, in the sense that p^ast > d^ast . This is the case for most non-convex problems.