I left off a few days ago with my explanation of Weak Duality. Today, I will continue with the discussion of strong duality, which states
Strong duality does not always hold but for certain types of problems (especially most convex optimality problems), strong duality holds. Constraint qualifications are the conditions under which strong duality holds when these conditions are applied to convex optimality problems.
One simple but well-known constraint qualification is Slater’s condition:
such that and .
Slater’s condition basically states that there is a point in the relative interior of the domain of the optimization problem such that all constraints are strictly satisfied.
For linear programs, a well-known proof using Farkas’s Lemma shows that strong duality holds. You can view the proof here. However, here, I am interested in exploring the proof of Slater’s Theorem (below) since the main focus of this blog series is convex optimization. Slater’s Theorem states that strong duality holds for convex optimization problems that follow Slater’s condition.
Slater’s Theorem: If Slater’s condition is followed and the optimization problem is convex, then strong duality holds.
The proof of Slater’s Theorem relies on the geometric interpretation of duality. Suppose we define a set where
We may define the optimal solution, to the optimization problem in terms of since contains the values of the constraint functions and the objective function.
Once we have defined the optimal solution value in terms of , we may then define the dual in terms of . Recall that the Lagrangian dual is
We may rewrite the Lagrangian dual in terms of as
If the infimum of the Lagrangian dual is finite, then, by the same argument we gave last time,
for all . The above inequality defines a hyperplane given by .
Suppose that , then given a feasible solution where and . We can show weak duality by using the fact we just stated:
Geometrically, each pair of values defines a different hyperplane. The hyperplanes’ intersections with the axes define the Lagrangian dual values since at the intersections all constraints are satisfied.
Let’s look at a simple example with only one constraint:
This graph assumes . We first see that the optimal value is given by the tangent horizontal line that indicates the minimum value when (when all constraints are satisfied). For a given , the line provides the lower bound on the objective value for each . We may compute from our constraint , and we may also compute by minimizing .
To list some characteristics for the line (hyperplane) given above:
- The hyperplane has slope . Since we defined , .
- The hyperplane is always tangent to at least one point on the boundary of .
If we look at all values when , we find that we obtain the minimum value when . We need to only look at the values when because our feasible region is defined by the region of left of the axis. This value is then a lower bound on the optimal objective value.
However, what we want to find is the value of that will give the maximum so that we find the best lower bound on the optimal objective value. Therefore, we will plot the hyperplanes for different values of .
The figure shows the hyperplanes for different values of . We see that gives which is the best lower bound we may hope to achieve. Here, we also see that strong duality does not hold because .
We need to define one more concept before we may move on to the proof sketch of Slater’s Theorem. We define an epigraph of to be the set of points
where set contains all the points in and all points which lie above the points in set .
For example, for the one constraint problem, the graph below shows the set .
Set may also be used to express the objective as well as the Lagrangian dual. In some ways, it is actually easier to express the objective and dual in terms of than in terms of .
The optimal value in terms of is
and the dual
Using , we may also more easily show weak duality
Proof Sketch of Slater’s Theorem:
Now that we know the geometric interpretation of duality, we may finally use it to provide a proof sketch of Slater’s Theorem. To see a more complete proof, refer to pg. 234 in Boyd and Vandenberghe’s Convex Optimization.
We first define a second convex set
We can immediately see that sets and are disjoint since set contains all elements whose values are greater than or equal to . If any element in is in , then we have a contradiction because would no longer be the optimal value.
Since and are disjoint, convex sets, by the Separating Hyperplane Theorem (more formally given in Section 2.5.1 in Boyd and Vandenberghe), there exists and such that
By a simple argument, and . We will first prove the case that strong duality holds when .
Because , we may rewrite the first inequality to be
We see that minimizing over gives us the dual . By the second inequality, we obtain
since for all . We can conclude then
By Weak Duality, we have . Therefore, in the case that , we have
This proves strong duality because we know that . We see that in the case when , (otherwise, we contradict weak duality) and the hyperplane is tangent to (and also consequently, the corresponding point in where ).
Now, we must prove the case when . For the purposes of contradiction, we assume:
- The rank of is .
- relint int (subtle distinction, mainly that the interior of the domain is not empty).
In this case, we may again simplify the first inequality
From and since we are proving the case ,
Because Slater’s condition holds (i.e. we have a where and ), we may further simplify the inequality to
for some values of .
Since by the first inequality and by Slater’s condition, is the only possibility. Since and , to satisfy .
Thus, we know that
By Slater’s condition, since there are points int , so for some values, . We have a contradiction. Either , contradicting the condition we gave above, for some or , contradicting that the rank is .
(We know that for some values, because is in the interior of . Therefore, we may arbitrarily choose a such that so . It is easy to choose an arbitrary such that the inequality follows.)
References and More Reading:
- 6.854 Notes on Strong Duality and Farkas’s Lemma.
- A good introduction to convex optimization is UC Berkeley’s site on “Optimization Models and Applications.”
- Lecture notes on proof sketch of Slater’s Theorem and geometric interpretation of duality.
- Boyd and Vandenberghe’s Convex Optimization.