2023/11/14 18:37

Weak duality

Let and be convex differentiable functions on . Let and note that by convexity of the functions , the set is actually a convex set. We are interested in the infimum of the convex function on the convex set . Define the Lagrange function where . We first show the weak duality relation. Start with this simple remark: for all , Taking the supremum wrt on both sides yields: And taking now the infimum wrt on both sides, we finally get the weak duality relation: Note that in the lhs (left-hand side), the infimum is wrt and therefore, there is no constraint, which is nice… The rhs (right-hand side) is called the primal problem and the lhs the dual problem. Note, since is convex, that the dual problem is equivalent to

To obtain the equality in \eqref{eq:weak} (which is named the strong duality relation), we actually need some additional assumptions (for example the existence of a Slater point). But before that, let us check a very useful relation…

Karush-Kuhn-Tucker conditions

Sufficient conditions

Lemma Assume that there exist such that and for all , we have either or . Then, the strong duality holds and

Click to see the proof

For every , the convexity of the function yields It remains to prove . Using first and then the convexity of the functions , we get This finishes the proof.

Saddle points

Definition We say that is a saddle point of the Lagrange function if for every ,

Saddle point Lemma If is a saddle point for then the strong duality holds, and the KKT conditions holds for .

click here to see the proof

Using \eqref{eq:saddle} with first and then with , we have for every , The existence of a saddle point implies the strong duality since which is the converse inequality of \eqref{eq:weak}. This finally implies:

Note that shows that .

The upper bound in \eqref{eq:saddle} regardless the value of shows that for every , that is . Now taking \eqref{eq:saddle} with yields for , which shows that . Combining with \eqref{eq:all} yields so that and since and , this implies for all .

Necessary conditions and strong duality

We now assume the existence of Slater points: there exists such that for all , .

The convex Farkas lemma Assume that there exists a Slater point. Then, iff there exists such that for all , .

Click here to see the proof

Set The condition is equivalent to saying that and since is clearly a convex set, by a separation argument, there exists a non-null vector such that Take an arbitrary . If then where and . The previous inequality implies for all , therefore . Now, since for all , a simple limiting argument yields for all , To conclude, and since we already know that for all , it only remains to prove that and to set in that case . The rest of the argument is by contradiction. If , then the previous inequality on a Slater point yields but since for all , we finally get for all . Finally all the components of are null and we are face to a contradiction. The proof is completed.

The Farkas lemma will imply the strong duality under the existence of a Slater point.

The necessary condition Assume that for some and that there exists a Slater point. Then there exist such that is a saddle point and by the Saddle point lemma, the strong duality holds.