.md .pdf

repository open issue

Contents

9.4. Basic Duality

9.4.1. The Geometry of the $\mathbb{V}\oplus \mathbb{R}$ Space

As we concern ourselves with the optimization of proper functions of type $f:\mathbb{V}\to (-\mathrm{\infty },\mathrm{\infty }]$, it is pertinent for us to introduce some terminology to explore the geometry of the $\mathbb{V}\oplus \mathbb{R}$ space. We recall that $\mathrm{epi}f\subseteq \mathbb{V}\oplus \mathbb{R}$.

1. The $\mathbb{V}$ part forms the horizontal axes for the product space $\mathbb{V}\oplus \mathbb{R}$.

2. The $\mathbb{R}$ part forms the vertical axis.

3. We write the vectors in $\mathbb{V}\oplus \mathbb{R}$ as $(\mathbf{x},t)$ where $\mathbf{x}\in \mathbb{V}$ and $t\in \mathbb{R}$.

4. A hyperplane in $\mathbb{V}\oplus \mathbb{R}$ is associated with a nonzero normal vector of the form $(\mathbf{a},b)$ where $\mathbf{a}\in \mathbb{V}$ and $b\in \mathbb{R}$.

   $$H=\{(\mathbf{x},t)\in \mathbb{V}\oplus \mathbb{R}|⟨\mathbf{x},\mathbf{a}⟩+tb=c\}.$$

   Since the normal vector must be nonzero, hence either $\mathbf{a}$ or $b$ or both must be nonzero.

5. If a specific point $({\mathbf{x}}_0,t_0)\in H$, then

   $$H=\{(\mathbf{x},t)\in \mathbb{V}\oplus \mathbb{R}|⟨\mathbf{x},\mathbf{a}⟩+tb=⟨{\mathbf{x}}_0,\mathbf{a}⟩+t_{0}b\}.$$

9.4.1.1. Different Types of Hyperplanes

Definition 9.10 (Vertical, horizontal and nonvertical hyperplanes)

Let $H$ be a hyperplane of $\mathbb{V}\oplus \mathbb{R}$ with a normal vector $(\mathbf{a},b)$.

1. The hyperplane is called horizontal if $\mathbf{a}=\mathbf{0}$.

2. The hyperplane is called vertical if $b=0$.

3. The hyperplane is called nonvertical if $b\ne 0$.

Let us see how these definitions can be interpreted.

9.4.1.2. Horizontal Hyperplanes

Example 9.2 (Horizontal hyperplanes)

Consider the case where $\mathbf{a}=\mathbf{0}$.

1. The hyperplane description reduces to

   $$H=\{(\mathbf{x},t)\in \mathbb{V}\oplus \mathbb{R}|tb=c\}.$$

2. It simplifies to

   $$H=\{(\mathbf{x},t)\in \mathbb{V}\oplus \mathbb{R}|t=\frac{c}{b}\}$$

   since $b$ must be nonzero.

3. Along the $\mathbb{V}$ axes, the points in set $H$ can take any value but along the vertical axis, they must take a fixed value given by $\frac{c}{b}$.

4. We can see that $H$ is a hyperplane which is parallel to $\mathbb{V}\times \{0\}$.

5. For the specific case where $c=0$, $H=\mathbb{V}\times \{0\}$.

6. Hence they are called horizontal hyperplanes.

7. Note that $H$ intersects with the vertical axis at the point $(\mathbf{0},\frac{c}{b})$.

9.4.1.3. Vertical Hyperplanes

Example 9.3 (Vertical hyperplanes)

Now consider the case where $b=0$.

1. The hyperplane description reduces to

   $$H=\{(\mathbf{x},t)\in \mathbb{V}\oplus \mathbb{R}|⟨\mathbf{x},\mathbf{a}⟩=c\}.$$

2. The set $H_v=\{\mathbf{x}\in \mathbb{V}|⟨\mathbf{x},\mathbf{a}⟩=c\}$ describes a hyperplane of $\mathbb{V}$.

3. $H$ is constructed by allowing $H_v$ to slide along the vertical axis as any value is allowed in the last coordinate (vertical axis).

4. Hence this is called a vertical hyperplane.

9.4.1.4. Nonvertical Hyperplanes

Observation 9.3 (Intersection of nonvertical hyperplane with vertical axis)

If a hyperplane $H$ with the normal vector $(\mathbf{a},b)$ is nonvertical (i.e., $b\ne 0$), then it intersects with the vertical axis at a unique point.

1. Indeed the vertical axis is identified with the set of points

   $$L=\{(\mathbf{x},t)\in \mathbb{V}\oplus \mathbb{R}|\mathbf{x}=\mathbf{0}\}.$$

2. The hyperplane is given by

   $$H=\{(\mathbf{x},t)\in \mathbb{V}\oplus \mathbb{R}|⟨\mathbf{x},\mathbf{a}⟩+tb=c\}.$$

3. Then the point of intersection is given by $(\mathbf{0},t)$ where

   $$t=\frac{c}{b}.$$

4. In particular, assume that $(\mathbf{x},s)\in H$.

5. Then by definition of $H$,

   $$c=⟨\mathbf{x},\mathbf{a}⟩+sb.$$

6. Hence

   $$t=\frac{1}{b}⟨\mathbf{x},\mathbf{a}⟩+s.$$

9.4.1.5. Vertical Lines

Definition 9.11 (Vertical line)

A vertical line in $\mathbb{V}\oplus \mathbb{R}$ is a set of the form $\{(\mathbf{x},t)|t\in \mathbb{R}\}$ where $\mathbf{x}\in \mathbb{V}$ is a fixed vector.

1. A vertical hyperplane is a union of vertical lines.

2. A vertical halfspace is also a union of vertical lines.

3. If $f$ is a proper function, then its epigraph doesn’t contain a vertical line.

It enables us to wonder if the epigraph of a proper function is contained entirely in a closed halfspace corresponding to some nonvertical hyperplane.

9.4.1.6. Nonvertical Supporting Hyperplanes

Theorem 9.30 (Convex sets and nonvertical supporting hyperplanes)

Let $C$ be a nonempty convex subset of $\mathbb{V}\oplus \mathbb{R}$ that contains no vertical lines. Then

1. $C$ is contained in a closed halfspace corresponding to a nonvertical hyperplane; i.e., there exists a vector $\mathbf{a}\in \mathbb{V}$, a nonzero scalar $b\in \mathbb{R}$, and a scalar $c\in \mathbb{R}$ such that

   $$⟨\mathbf{x},\mathbf{a}⟩+tb\ge c\mathrm{\forall }(\mathbf{x},t)\in C.$$

2. If a point $(\overline{\mathbf{x}},\overline{t})$ doesn’t belong to $\mathrm{cl}C$, there exists a nonvertical hyperplane strongly separating $(\overline{\mathbf{x}},\overline{t})$ and $C$.

Proof. (1) We prove this claim by contradiction.

1. Assume that every hyperplane such that $C$ is contained in one of its closed half-spaces is vertical.

2. Then every hyperplane such that $\mathrm{cl}C$ is contained in one of its closed half spaces is vertical.

3. By Theorem 8.170, $\mathrm{cl}C$ is the intersection of all closed half-spaces that contain it.

4. Hence, we have

   $$\mathrm{cl}C=\bigcap _{i\in I}\{(\mathbf{x},t)|⟨\mathbf{x},{\mathbf{a}}_i⟩\ge c_i\}$$

   where $I$ is an index set for the family of the hyperplanes that contain $\mathrm{cl}C$ in its closed half spaces above. Since the hyperplanes are vertical, hence $b_i=0$ for ever $i\in I$.

5. Let $(\tilde{\mathbf{x}},\tilde{t})\in \mathrm{cl}C$.

6. Then the vertical line $\{(\tilde{\mathbf{x}},t)|t\in \mathbb{R}\}$ also belongs to $\mathrm{cl}C$ as it satisfies the expression above.

7. Hence, the vector $(\mathbf{0},1)$ is a direction of recession for $\mathrm{cl}C$. In fact it belongs to its lineality space. In other words, $(\mathbf{0},-1)$ is also a direction of recession for $\mathrm{cl}C$.

8. By Theorem 8.150,

   $$\mathrm{ri}\mathrm{cl}C=\mathrm{ri}C$$

   since $C$ is a convex set.

9. By Theorem 8.182, the recession cones of $\mathrm{cl}C$ and $\mathrm{ri}C$ are equal.

10. Hence $(\mathbf{0},1)$ and $(\mathbf{0},-1)$ are also directions of recession for $\mathrm{ri}C$.

11. Hence for every $(\tilde{\mathbf{x}},\tilde{t})\in \mathrm{ri}C$, the vertical line $\{(\tilde{\mathbf{x}},t)|t\in \mathbb{R}\}$ also belongs to $\mathrm{ri}C$ and hence to $C$.

12. This contradicts the hypothesis that $C$ doesn’t contain a vertical line.

(2) This follows from strict separation theorem.

1. Since $(\overline{\mathbf{x}},\overline{t})\notin \mathrm{cl}C$, hence, due to Theorem 8.169, there exists a hyperplane strongly separating $\mathrm{cl}C$ and $(\overline{\mathbf{x}},\overline{t})$.

2. If this hyperplane is nonvertical, then there is nothing more to do.

3. We now consider the case where this strongly separating hyperplane is vertical.

4. Let this separating hyperplane be given by

   $$H=\{(\mathbf{x},t)\in \mathbb{V}\oplus \mathbb{R}|⟨\mathbf{x},\overline{\mathbf{a}}⟩=\overline{c}\}$$

   such that

   $$⟨\mathbf{x},\overline{\mathbf{a}}⟩>\overline{c}>⟨\overline{\mathbf{x}},\overline{\mathbf{a}}⟩\mathrm{\forall }(\mathbf{x},t)\in \mathrm{cl}C.$$

5. Our goal is to combine this vertical hyperplane with a suitably constructed nonvertical hyperplane so that the combined nonvertical hyperplane also strongly separates $C$ and $(\overline{\mathbf{x}},\overline{t})$.

6. By part (1), there exists a nonvertical hyperplane such that $C$ is totally contained in one of its closed half spaces.

7. Hence there exists $(\hat{\mathbf{a}},\hat{b})\in \mathbb{V}\oplus \mathbb{R}$ with $\hat{b}\ne 0$ and $\hat{c}\in \mathbb{R}$ such that

   $$⟨\mathbf{x},\hat{\mathbf{a}}⟩+t\hat{b}\ge \hat{c}\mathrm{\forall }(\mathbf{x},t)\in \mathrm{cl}C.$$

8. Multiply this inequality with some $ϵ>0$ and add with the previous inequality to get

   $$⟨\mathbf{x},\overline{\mathbf{a}}+ϵ\hat{\mathbf{a}}⟩+ϵt\hat{b}>\overline{c}+ϵ\hat{c}\mathrm{\forall }(\mathbf{x},t)\in \mathrm{cl}C,\mathrm{\forall }ϵ>0.$$

9. Since $\overline{c}>⟨\overline{\mathbf{x}},\overline{\mathbf{a}}⟩$, it is possible to select a small enough $ϵ>0$ such that

   $$\overline{c}+ϵ\hat{c}>⟨\overline{\mathbf{x}},\overline{\mathbf{a}}+ϵ\hat{\mathbf{a}}⟩+ϵ\overline{t}\hat{b}.$$

10. Thus, for the small enough $ϵ>0$, we have

    $$⟨\mathbf{x},\overline{\mathbf{a}}+ϵ\hat{\mathbf{a}}⟩+ϵt\hat{b}>\overline{c}+ϵ\hat{c}>⟨\overline{\mathbf{x}},\overline{\mathbf{a}}+ϵ\hat{\mathbf{a}}⟩+ϵ\overline{t}\hat{b}\mathrm{\forall }(\mathbf{x},t)\in \mathrm{cl}C.$$

11. Letting $\tilde{\mathbf{a}}=\overline{\mathbf{a}}+ϵ\hat{\mathbf{a}}$, $\tilde{b}=ϵ\hat{b}$ and $\tilde{c}=\overline{c}+ϵ\hat{c}$, we have

    $$⟨\mathbf{x},\tilde{\mathbf{a}}⟩+t\tilde{b}>\tilde{c}>⟨\overline{\mathbf{x}},\tilde{\mathbf{a}}⟩+\overline{t}\tilde{b}\mathrm{\forall }(\mathbf{x},t)\in \mathrm{cl}C.$$

12. This describes the strongly separating nonvertical hyperplane between $\mathrm{cl}C$ and $(\overline{\mathbf{x}},\overline{t})$.

Definition 9.12 (Upper closed halfspace)

Let $H$ be a nonvertical hyperplane. The closed halfspace of $H$ whose recession cone includes the vertical halfline $\{(\mathbf{0},t)|t\ge 0\}$ is known as its upper closed halfspace.

If you are in the upper closed halfspace and keep going up, you will stay in the upper closed halfspace. If you go down, you will hit the hyperplane.

Definition 9.13 (Lower closed halfspace)

Let $H$ be a nonvertical hyperplane. The closed halfspace of $H$ whose recession cone includes the vertical halfline $\{(\mathbf{0},t)|t\le 0\}$ is known as its lower closed halfspace.

If you are in the lower closed halfspace and keep going down, you will stay in the lower closed halfspace. If you go up, you will hit the hyperplane.

9.4.2. Min Common/Max Crossing Duality

We introduce two simple optimization problems.

1. Consider a set $M$ in $\mathbb{V}\oplus \mathbb{R}$.

2. Assume that $M$ intersects with the vertical axis; i.e., $R=\{(\mathbf{0},t)|t\in \mathbb{R}\}$.

3. The min common point problem attempts to find the point $\mathbf{x}\in M\cap R$ whose component along vertical axis is the minimum.

4. Now consider the set of nonvertical hyperplanes such that $M$ lies in their upper closed halfspaces.

5. Each such hyperplane intersects with the vertical axis.

6. Such points are called the crossing points between the nonvertical hyperplane and the vertical axis.

7. Consider the set of all such crossing points.

8. The max crossing point problem attempts to find the point whose vertical component is the largest (highest).

9. Let ${\mathbf{p}}^{\ast }$ be the minimum common point.

10. Let ${\mathbf{q}}^{\ast }$ be the maximum crossing point.

11. Let $p^{\ast }$ and $q^{\ast }$ denote the component along the vertical axis for ${\mathbf{p}}^{\ast }$ and ${\mathbf{q}}^{\ast }$ respectively.

12. In general, $p^{\ast }$ lies above $q^{\ast }$. We shall show this later formally.

13. We call $p^{\ast }$ as minimum common level and $q^{\ast }$ as maximum crossing level.

14. Then $p^{\ast }\ge q^{\ast }$. This is known as weak duality.

15. The gap $p^{\ast }-q^{\ast }$ which is a nonnegative quantity is known as the duality gap.

16. Under certain conditions $p^{\ast }=q^{\ast }$. In other words, if the set $M$ meets specific conditions, then the optimal value for the min common point problem (the primal problem) as well as the max crossing point problem (the dual problem) are identical.

17. When $p^{\ast }=q^{\ast }$, then the duality gap is $0$. This is known as strong duality.

18. When strong duality holds, then the min common point problem and the max crossing point problem are equivalent in the sense that they have the same solution.

We are now ready to define these problems formally.

9.4.2.1. Min Common Problem

Definition 9.14 (Min common problem)

Given a set $M\subseteq \mathbb{V}\oplus \mathbb{R}$, the min common problem is defined as

$$\begin{array}{rlrl}& \text{minimize }& & p\\ & \text{subject to }& & (\mathbf{0},p)\in M\end{array}$$

Its optimal value is denoted by $p^{\ast }$; i.e.,

$$p^{\ast }=\underset{(\mathbf{0},p)\in M}{inf}p.$$

9.4.2.2. Max Crossing Problem

Recall that a nonvertical hyperplane has a normal $(\mathbf{a},b)$ such that $b\ne 0$. Then $(\frac{\mathbf{a}}{b},1)$ is also a normal vector for this hyperplane. Hence one way to describe the set of nonvertical hyperplanes is the set of hyperplanes with normal vectors of the form $(\mathbf{a},1)$. Following Observation 9.3, if a nonvertical hyperplane $H$ intersects the vertical axis at some $(\mathbf{0},q)$, then

$$q=⟨\mathbf{x},\mathbf{a}⟩+t$$

where $(\mathbf{x},t)\in H$. Thus, the hyperplane can be characterized by $\mathbf{a}$ and $q$ as

$$H_{\mathbf{a},q}=\{(\mathbf{x},t)|⟨\mathbf{x},\mathbf{a}⟩+t=q\}.$$

The corresponding upper closed half halfspace is given by

$$H_{\mathbf{a},q}^u=\{(\mathbf{x},t)|⟨\mathbf{x},\mathbf{a}⟩+t\ge q\}$$

since $t\ge q$ for every point on the vertical axis in $H_{\mathbf{a},q}^u$. The coordinate along the vertical axis for all the points on the vertical axis in the upper half space must be more than or equal to $q$.

If the set $M$ lies in the upper closed half space of a hyperplane characterized by $\mathbf{a}$ and $q$, then

$$⟨\mathbf{x},\mathbf{a}⟩+t\ge q\mathrm{\forall }(\mathbf{x},t)\in M.$$

Hence, the maximum crossing level $q$ over all hyperplanes $H_{\mathbf{a},q}$ with the same normal $(\mathbf{a},1)$ is given by

$$q(\mathbf{a})=\underset{(\mathbf{x},t)\in M}{inf}\{⟨\mathbf{x},\mathbf{a}⟩+t\}.$$

The problem of maximizing the crossing level over all nonvertical hyperplanes is to maximize over all $\mathbf{a}\in \mathbb{V}$, the maximum crossing level corresponding to $\mathbf{a}$.

Definition 9.15 (Max crossing problem)

Given a set $M\subseteq \mathbb{V}\oplus \mathbb{R}$, the max crossing problem is defined as

$$\begin{array}{rlrl}& \text{maximize }& & q(\mathbf{a})\\ & \text{subject to }& & \mathbf{a}\in \mathbb{V}\end{array}$$

where $q(\mathbf{a})=\underset{(\mathbf{x},t)\in M}{inf}\{⟨\mathbf{x},\mathbf{a}⟩+t\}$. Its optimal value is denoted by $q^{\ast }$; i.e.,

$$q^{\ast }=\underset{\mathbf{a}\in \mathbb{V}}{sup}q(\mathbf{a}).$$

The function $q$ is the cost function (objective function) of the max crossing problem. It turns out that $q$ is concave and upper semicontinuous.

Theorem 9.31 (Concavity and upper semicontinuity of $q$)

The cost function $q$ of the max crossing problem is concave and upper semicontinuous over $\mathbb{V}$.

Proof. Concavity

1. For each $(\mathbf{x},t)$, the function $\mathbf{a}\mapsto ⟨\mathbf{x},\mathbf{a}⟩+t$ is an affine function.

2. Thus $q$ is an infimum of a family of affine functions over $(\mathbf{x},t)\in M$.

3. Hence $q$ is concave.

Upper semicontinuity

1. We note that $-q(\mathbf{a})=\underset{(\mathbf{x},t)\in M}{sup}\{-⟨\mathbf{x},\mathbf{a}⟩-t\}$.

2. Hence $-q$ is a supremum of affine functions.

3. Affine functions are closed (Theorem 8.86).

4. Pointwise supremum of closed functions is closed (Theorem 3.93).

5. Hence $-q$ is a closed function.

6. By Theorem 3.119, $-q$ is lower semicontinuous since it is closed.

7. Hence $q$ is upper semicontinuous.

9.4.2.3. Weak Duality

Theorem 9.32 (Weak duality theorem)

For the min common and max crossing problems we have

$$q^{\ast }\le p^{\ast }.$$

Proof. Recall that

$$q(\mathbf{a})=\underset{(\mathbf{x},t)\in M}{inf}\{⟨\mathbf{x},\mathbf{a}⟩+t\}.$$

Then

$$\underset{(\mathbf{x},t)\in M}{inf}\{⟨\mathbf{x},\mathbf{a}⟩+t\}\le \underset{(\mathbf{0},t)\in M}{inf}\{⟨\mathbf{0},\mathbf{a}⟩+t\}=\underset{(\mathbf{0},t)\in M}{inf}\{t\}=p^{\ast }.$$

Thus we have

$$q(\mathbf{a})\le p^{\ast }\mathrm{\forall }\mathbf{a}\in \mathbb{V}.$$

Taking the supremum over $\mathbf{a}\in \mathbb{V}$ on the L.H.S., we obtain

$$q^{\ast }=\underset{\mathbf{a}\in \mathbb{V}}{sup}q(\mathbf{a})\le p^{\ast }.$$

9.4.2.4. Strong Duality

We are now interested in conditions under which there is no duality gap and $p^{\ast }=q^{\ast }$. We shall assume in general that the min common problem is feasible and $p^{\ast }<\mathrm{\infty }$.

Remark 9.6 (Optimal point of min common problem is a closure point)

Assume that the min common problem is feasible and let $p^{\ast }<\mathrm{\infty }$. Then the point $(\mathbf{0},p^{\ast })$ is a closure point of $M$.

1. We have $p^{\ast }=\underset{(\mathbf{0},t)\in M}{inf}\{t\}$.

2. Thus for every $ϵ>0$ there exists $(\mathbf{0},t)\in M$ such that $t<p^{\ast }+ϵ$.

3. Thus for every $ϵ>0$, there exists a point $(\mathbf{0},t)\in M$ such that $\Vert (\mathbf{0},t)-(\mathbf{0},p^{\ast })\Vert <ϵ$.

4. Hence $(\mathbf{0},p^{\ast })$ is a closure point of $M$.

Observation 9.4 (Closed and convex $M$)

If $M$ is closed and convex and admits a nonvertical supporting hyperplane at $(\mathbf{0},p^{\ast })$, then the strong duality holds and $p^{\ast }=q^{\ast }$. Also, the optimal values of both the min common problem and max crossing problem are attained.

1. Since $M$ is closed, hence $(\mathbf{0},p^{\ast })\in M$ since $(\mathbf{0},p^{\ast })$ is a closure point of $M$.

2. Hence the optimal value of min common problem is attained at $(\mathbf{0},p^{\ast })$.

3. Let $H$ be the nonvertical supporting hyperplane at $(\mathbf{0},p^{\ast })$.

4. Then intersection of $H$ with the vertical axis is at $(\mathbf{0},p^{\ast })$.

5. Hence $q^{\ast }\ge p^{\ast }$.

6. But by weak duality $q^{\ast }\le p^{\ast }$.

7. Hence $q^{\ast }=p^{\ast }$.

8. Clearly the optimal value of max crossing problem is attained at $(\mathbf{0},p^{\ast })$ for the hyperplane $H$.

This is the most favorable case where strong duality holds as well as the optimal values of both problems are attained. We next provide a result that provides a necessary and sufficient condition for the strong duality however does not address the issue of attainment of the optimal values.

9.4.2.5. First Min Common / Max Crossing Theorem

Theorem 9.33 (Min common/max crossing theorem I)

Consider the min common and max crossing problems. Assume the following:

1. $p^{\ast }<\mathrm{\infty }$; i.e., the min common problem is feasible.

2. The set

   $$\bar{M}=\{(\mathbf{x},t)\in \mathbb{V}\oplus \mathbb{R}|\text{ there exists }\overline{t}\in \mathbb{R}\text{ with }\overline{t}\le t\text{ and }(\mathbf{x},\overline{t})\in M\}$$

   is convex.

Then we have $q^{\ast }=p^{\ast }$ if and only if for every sequence $\{({\mathbf{x}}_k,t_k)\}$ of $M$ with ${\mathbf{x}}_k\to \mathbf{0}$, there holds

$$p^{\ast }\le \underset{k\to \mathrm{\infty }}{lim inf}{t}_k.$$

The set $\bar{M}$ is an extension of the set $M$ going upwards along the vertical axis. In other words, all points above $M$ are included in $\bar{M}$. In other words, the direction $(\mathbf{0},1)$ is added to the recession cone. $\bar{M}$ is unbounded along the $(\mathbf{0},1)$ direction.

Proof. We first consider the trivial case where $p^{\ast }=-\mathrm{\infty }$.

1. By weak duality (Theorem 9.32), $q^{\ast }\le p^{\ast }$.

2. Hence $q^{\ast }=-\mathrm{\infty }$.

3. Hence $q(\mathbf{a})=-\mathrm{\infty }$ for every $\mathbf{a}\in \mathbb{V}$.

4. The conclusion follows trivially.

We now consider the general case where $p^{\ast }\in \mathbb{R}$. First assume that $p^{\ast }\le \underset{k\to \mathrm{\infty }}{lim inf}{t}_k$ holds for every sequence $\{({\mathbf{x}}_k,t_k)\}$ of $M$ with ${\mathbf{x}}_k\to \mathbf{0}$.

1. Since $M\subseteq \bar{M}$ and $(\mathbf{0},p^{\ast })$ is a closure point of $M$, hence $(\mathbf{0},p^{\ast })$ is also a closure point of $\bar{M}$.

2. We first claim that the set $\bar{M}$ doesn’t contain any vertical lines.

   1. For contradiction, assume that $\bar{M}$ contains a vertical line.

   2. The set $\mathrm{cl}\bar{M}$ also contains a vertical line then.

   3. Then $(\mathbf{0},-1)$ is a direction of recession of $\mathrm{cl}\bar{M}$.

   4. Hence $(\mathbf{0},-1)$ is also a direction of recession of $\mathrm{ri}\bar{M}$.

   5. Since $(\mathbf{0},p^{\ast })$ is a closure point of $\bar{M}$, hence it is also a closure point of $\mathrm{ri}\bar{M}$.

   6. Hence, there exists a sequence $\{({\mathbf{x}}_k,t_k)\}$ of $\mathrm{ri}\bar{M}$ converging to $(\mathbf{0},p^{\ast })$.

   7. Since $(\mathbf{0},-1)$ is a direction of recession of $\mathrm{ri}\bar{M}$, hence the sequence $\{({\mathbf{x}}_k,t_k-1)\}$ belongs to $\mathrm{ri}\bar{M}$.

   8. Hence its limit $(\mathbf{0},p^{\ast }-1)\in \mathrm{cl}\bar{M}$.

   9. By definition of $\bar{M}$, for every $k$, there exists a point $({\mathbf{x}}_k\overline{t_k})\in M$ such that $\overline{t_k}\le t_k-1$.

   10. Hence there exists a sequence $\{({\mathbf{x}}_k,\overline{t_k})\}$ of $M$ with $\overline{t_k}\le t_k-1$ for all $k$ so that $\underset{k\to \mathrm{\infty }}{lim inf}\overline{t_k}\le p^{\ast }-1$.

   11. This contradicts the assumption that $p^{\ast }\le \underset{k\to \mathrm{\infty }}{lim inf}{t}_k$ since ${\mathbf{x}}_k\to \mathbf{0}$.

3. We next show that the vector $(\mathbf{0},p^{\ast }-ϵ)$ does not belong to $\mathrm{cl}\bar{M}$ for any $ϵ>0$.

   1. Assume for contradiction that for some $ϵ>0$, the vector $(\mathbf{0},p^{\ast }-ϵ)\in \mathrm{cl}\bar{M}$.

   2. Then there is a sequence $\{({\mathbf{x}}_k,t_k)\}$ of $\bar{M}$ converging to $(\mathbf{0},p^{\ast }-ϵ)$.

   3. By definition of $\bar{M}$, for every $k$, there exists a point $({\mathbf{x}}_k\overline{t_k})\in M$ such that $\overline{t_k}\le t_k$.

   4. Hence there exists a sequence $\{({\mathbf{x}}_k,\overline{t_k})\}$ of $M$ with $\overline{t_k}\le t_k$ for all $k$ so that $\underset{k\to \mathrm{\infty }}{lim inf}\overline{t_k}\le p^{\ast }-ϵ$.

   5. This contradicts the assumption that $p^{\ast }\le \underset{k\to \mathrm{\infty }}{lim inf}{t}_k$ since ${\mathbf{x}}_k\to \mathbf{0}$.

4. Since $\bar{M}$ does not contain any vertical lines and the vector $(\mathbf{0},p^{\ast }-ϵ)$ doesn’t belong to $\mathrm{cl}\bar{M}$, hence, due to Theorem 9.30, there exists a nonvertical hyperplane strongly separating $(\mathbf{0},p^{\ast }-ϵ)$ and $\bar{M}$ for every $ϵ>0$.

5. This hyperplane crosses the vertical axis at a unique vector $(\mathbf{0},\xi )$ which must lie between $(\mathbf{0},p^{\ast }-ϵ)$ and $(\mathbf{0},p^{\ast })$; i.e., $p^{\ast }-ϵ\le \xi \le p^{\ast }$.

6. By definition of max crossing problem, $\xi \le q^{\ast }$.

7. Hence we have $p^{\ast }-ϵ\le q^{\ast }\le p^{\ast }$ for every $ϵ>0$.

8. Since $ϵ$ can be arbitrarily small, it follows that $p^{\ast }=q^{\ast }$.

Conversely, we assume that the strong duality holds.

1. Let $\{({\mathbf{x}}_k,t_k)\}$ be any sequence of $M$ such that ${\mathbf{x}}_k\to \mathbf{0}$.

2. By definition of $q(\mathbf{a})$,

   $$q(\mathbf{a})=\underset{(\mathbf{x},t)\in M}{inf}\{⟨\mathbf{x},\mathbf{a}⟩+t\}\le ⟨{\mathbf{x}}_k,\mathbf{a}⟩+t_k\mathrm{\forall }k,\mathrm{\forall }\mathbf{a}\in \mathbb{V}.$$

3. Taking the limit on R.H.S. to $k\to \mathrm{\infty }$, we obtain

   $$q(\mathbf{a})\le \underset{k\to \mathrm{\infty }}{lim inf}{t}_k\mathrm{\forall }\mathbf{a}\in \mathbb{V}.$$

4. Taking the supremum on the L.H.S. over $\mathbf{a}\in \mathbb{V}$, we have

   $$p^{\ast }=q^{\ast }=\underset{\mathbf{a}\in \mathbb{V}}{sup}q(\mathbf{a})\le \underset{k\to \mathrm{\infty }}{lim inf}{t}_k.$$

This result doesn’t guarantee the attainment of either the min common optimal point or the max crossing optimal point. The next result includes additional conditions which ensures that the optimal point of max crossing problem is attained.

9.4.2.6. Second Min Common / Max Crossing Theorem

Theorem 9.34 (Min common/max crossing theorem II)

Consider the min common and max crossing problems. Assume the following:

1. $-\mathrm{\infty }<p^{\ast }$.

2. The set

   $$\bar{M}=\{(\mathbf{x},t)\in \mathbb{V}\oplus \mathbb{R}|\text{ there exists }\overline{t}\in \mathbb{R}\text{ with }\overline{t}\le t\text{ and }(\mathbf{x},\overline{t})\in M\}$$

   is convex.

3. The set

   $$D=\{\mathbf{u}\in \mathbb{V}|\text{ there exists }t\in \mathbb{R}\text{ with }(\mathbf{u},t)\in \bar{M}\}$$

   contains the origin in its relative interior.

Then $q^{\ast }=p^{\ast }$ and the optimal solution set of the max crossing problem

$$Q^{\ast }=\{\mathbf{a}\in \mathbb{V}|q(\mathbf{a})=q^{\ast }\}$$

has the form

$$Q^{\ast }=(\mathrm{aff}D{)}^{\perp }+\tilde{Q}$$

where $\tilde{Q}$ is a nonempty, convex and compact set and $(\mathrm{aff}D{)}^{\perp }$ is the orthogonal complement of $\mathrm{aff}D$ (which is a subspace by assumption 3 since it contains the origin).

Furthermore, $Q^{\ast }$ is nonempty and compact if and only if $D$ contains the origin in its interior.

Note that $D$ is the set of all possible horizontal coordinates of points in $M$. $\mathbf{x}\in D$ if and only if there exists some $(\mathbf{x},t)\in \bar{M}$ if and only if there exists some $(\mathbf{x},s)\in M$ with $s\le t$. Since $\bar{M}$ is convex and $D$ is a projection of $\bar{M}$ on $\mathbb{V}$, hence $D$ is also convex.

Proof. We first show that the strong duality holds and $Q^{\ast }$ is nonempty, closed and convex.

1. Condition (3) implies that there exists some $(\mathbf{0},t)\in \bar{M}$.

2. By definition of $\bar{M}$, there exists some $(\mathbf{0},\bar{t})\in M$ such that $\bar{t}\le t$.

3. Hence $p^{\ast }<\mathrm{\infty }$.

4. Then, by condition (1), $p^{\ast }\in \mathbb{R}$; i.e., the min crossing level is a real number.

5. The vertical axis $\{(\mathbf{0},t)|t\in \mathbb{R}\}$ belongs to $\mathrm{aff}\bar{M}$.

6. $p^{\ast }$ is the optimal min common value.

7. Hence $(\mathbf{0},p^{\ast })$ is not a relative interior point of $\bar{M}$.

8. Accordingly, $(\mathbf{0},p^{\ast })\notin \mathrm{ri}\bar{M}$.

9. By Theorem 8.163, there exists a hyperplane that separates $\bar{M}$ and the point $(\mathbf{0},p^{\ast })$ properly; i.e., it contains the point $(\mathbf{0},p^{\ast })$, contains $\bar{M}$ in one of its half-spaces and doesn’t contain $\bar{M}$ fully.

10. Hence, there exists a vector $(\mathbf{a},r)$ such that

    $$⟨\mathbf{x},\mathbf{a}⟩+tr\ge p^{\ast }r\mathrm{\forall }(\mathbf{x},t)\in \bar{M}$$

    and

    $$\underset{(\mathbf{x},t)\in \bar{M}}{sup}⟨\mathbf{x},\mathbf{a}⟩+tr>p^{\ast }r.$$

    See Remark 8.10.

11. Since for every $(\bar{\mathbf{x}},\bar{t})\in M$, the set $\bar{M}$ contains the half-line $\{(\bar{\mathbf{x}},t)|\bar{t}\le t\}$, it follows from the first inequality that $r\ge 0$ must hold true.

12. $r=0$ leads to a contradiction.

    1. Assume that $r=0$.

    2. Then the first inequality reduces to

       $$⟨\mathbf{x},\mathbf{a}⟩\ge 0\mathrm{\forall }\mathbf{x}\in D.$$

    3. The linear functional $⟨\mathbf{x},\mathbf{a}⟩$ attains its minimum over the set $D$ at $\mathbf{0}\in D$ which is a relative interior point of $D$ by condition (3).

    4. Since $D$ is convex (projection of convex $\bar{M}$ on $\mathbb{V}$), and the linear functional $⟨\mathbf{x},\mathbf{a}⟩$ (a concave function) attains its minimum at a relative interior point, hence, due to Theorem 9.5, the function must be constant over $D$.

    5. Hence we have

       $$⟨\mathbf{x},\mathbf{a}⟩=0\mathrm{\forall }\mathbf{x}\in D.$$

    6. But this contradicts the second (strict) inequality of the proper separation result since $\bar{M}$ cannot be contained entirely inside the hyperplane.

    7. We arrive at a contradiction.

    8. Hence $r\ne 0$ and the separating hyperplane is nonvertical.

13. By appropriate normalization, if necessary, we can assume that $r=1$.

14. The proper separation inequalities simplify to

    $$⟨\mathbf{x},\mathbf{a}⟩+t\ge p^{\ast }\mathrm{\forall }(\mathbf{x},t)\in \bar{M}$$

    and

    $$\underset{(\mathbf{x},t)\in \bar{M}}{sup}⟨\mathbf{x},\mathbf{a}⟩+t>p^{\ast }.$$

15. We now note that

    $$\begin{array}{rl}{p}^{\ast }& \le \underset{(\mathbf{x},t)\in \bar{M}}{inf}⟨\mathbf{x},\mathbf{a}⟩+t\\ & \le \underset{(\mathbf{x},t)\in M}{inf}⟨\mathbf{x},\mathbf{a}⟩+t\\ & =q(\mathbf{a})\\ & \le q^{\ast }.\end{array}$$

16. Since by weak duality, we always have $q^{\ast }\le p^{\ast }$, hence all the inequalities must be equalities in the previous relation.

17. Thus we have

    $$q(\mathbf{a})=q^{\ast }=p^{\ast }.$$

18. Hence $Q^{\ast }$ is nonempty as $\mathbf{a}\in Q^{\ast }$.

19. We can also write $Q^{\ast }$ as

    $$Q^{\ast }=\{\mathbf{a}\in \mathbb{V}|q(\mathbf{a})\ge q^{\ast }\}.$$

20. Since $q$ is concave and upper semicontinuous, hence its superlevel sets are closed and convex.

21. Hence $Q^{\ast }$ being a superlevel set of $q$ is convex and closed.

We next show that $Q^{\ast }=(\mathrm{aff}D{)}^{\perp }+\tilde{Q}$.

TBD

9.4.3. Minimax and Maximin Problems

We consider functions of the form $\varphi :\mathbb{V}\oplus \mathbb{W}\to \mathbb{R}$ with $\mathrm{dom}\varphi =X\times Z$. $\mathbb{V}$ and $\mathbb{W}$ are real vector spaces. $X\subseteq \mathbb{V}$ and $Z\subseteq \mathbb{W}$ are nonempty sets.

Definition 9.16 (Minimax problem)

A minimax problem takes the form

$$\begin{array}{rlr}& \text{minimize }& \underset{\mathbf{z}\in Z}{sup}\varphi (\mathbf{x},\mathbf{z})\\ & \text{subject to }& \mathbf{x}\in X\end{array}$$

Definition 9.17 (Maximin problem)

A maximin problem takes the form

$$\begin{array}{rlr}& \text{maximize }& \underset{\mathbf{x}\in X}{inf}\varphi (\mathbf{x},\mathbf{z})\\ & \text{subject to }& \mathbf{z}\in Z.\end{array}$$

We next provide a few examples.

9.4.3.1. Zero Sum Games

Example 9.4 (Zero sum games)

We consider a two player game with the following design.

1. Player A can choose one out of $n$ possible moves.

2. Player B can choose one out of $m$ possible moves.

3. Both players make their moves simultaneously.

4. $\mathbf{A}\in {\mathbb{R}}^{n\times m}$ is a payoff matrix.

5. If move $i$ is selected by player A and move $j$ is selected by player B, then A gives the specified amount $a_{ij}$ to B.

6. Note that $a_{ij}\in \mathbb{R}$ can be zero, positive or negative.

7. The players use mixed strategy.

8. Player A selects a probability distribution $\mathbf{x}=(x_1,\dots ,x_n)$ over her $n$ possible moves.

9. Player B selects a probability distribution $\mathbf{z}=(z_1,\dots ,z_m)$ over her $m$ possible moves.

10. Since the probability of selecting move $i$ by player A and move $j$ by player B is $x_i{z}_j$, hence the expected amount to be paid by A to B is

    $$\sum _{ij}{x}_i{a}_{ij}{z}_j={\mathbf{x}}^T\mathbf{A}\mathbf{z}.$$

11. Each player adopts a worst case viewpoint, whereby she optimizes her choice against the worst possible selection by the other player.

12. Player A must minimize $\underset{\mathbf{z}}{max}{\mathbf{x}}^T\mathbf{A}\mathbf{z}$ so that she has to pay as low as possible to B.

    1. Suppose A selects the strategy $\mathbf{x}$.

    2. The amount she has to pay to B for B’s selection of strategy $\mathbf{z}$ is ${\mathbf{x}}^T\mathbf{A}\mathbf{z}$.

    3. The maximum amount she has to pay across all possible strategies chosen by B is $\underset{\mathbf{z}}{max}{\mathbf{x}}^T\mathbf{A}\mathbf{z}$.

    4. By selecting $\mathbf{x}$, her goal is to minimize the maximum payoff.

13. Player B must maximize $\underset{\mathbf{x}}{min}{\mathbf{x}}^T\mathbf{A}\mathbf{z}$.

    1. Suppose B selects a strategy $\mathbf{z}$.

    2. Then the payoff she gets by a strategy $\mathbf{x}$ of A is ${\mathbf{x}}^T\mathbf{A}\mathbf{z}$.

    3. The minimum she can get for her choice of $\mathbf{z}$ is $\underset{\mathbf{x}}{min}{\mathbf{x}}^T\mathbf{A}\mathbf{z}$.

    4. By selecting $\mathbf{z}$ her goal is to maximize the minimum payoff.

14. Here $X={\mathrm{\Delta }}_n\subseteq {\mathbb{R}}^n$, the unit simplex of ${\mathbb{R}}^n$.

15. Similarly, $Z={\mathrm{\Delta }}_m\subseteq {\mathbb{R}}^m$, the unit simplex of ${\mathbb{R}}^m$.

16. $\varphi (\mathbf{x},\mathbf{z})={\mathbf{x}}^T\mathbf{A}\mathbf{z}$.

17. The worst case pay off for player A is

    $$\underset{\mathbf{x}\in X}{inf}\underset{\mathbf{z}\in Z}{sup}{\mathbf{x}}^T\mathbf{A}\mathbf{z}.$$

18. The worst case pay off for player B is

    $$\underset{\mathbf{z}\in Z}{sup}\underset{\mathbf{x}\in X}{inf}{\mathbf{x}}^T\mathbf{A}\mathbf{z}.$$

19. Under suitable conditions, we can guarantee that

    $$\underset{\mathbf{z}\in Z}{sup}\underset{\mathbf{x}\in X}{inf}{\mathbf{x}}^T\mathbf{A}\mathbf{z}=\underset{\mathbf{x}\in X}{inf}\underset{\mathbf{z}\in Z}{sup}{\mathbf{x}}^T\mathbf{A}\mathbf{z}.$$

9.4.3.2. Lagrangian Functions

Example 9.5 (Lagrangian functions and duality theory)

Consider the optimization problem of the form

$$\begin{array}{rlr}& \text{minimize }& f(\mathbf{x})\\ & \text{subject to }& g_i(\mathbf{x})\le 0,& i=1,\dots ,m\end{array}$$

where $f,g_1,\dots ,g_m:\mathbb{V}\to \mathbb{R}$ are given objective and inequality constraint functions.

We construct the Lagrangian function

$$L(\mathbf{x},\mathbf{z})=f(\mathbf{x})+\sum _{i=1}^m{z}_i{g}_i(\mathbf{x})$$

with $\mathrm{dom}L=X\oplus Z$ where $X=\mathrm{dom}f\cap \mathrm{dom}{g}_1\cap \cdots \cap \mathrm{dom}{g}_m$ and $Z={\mathbb{R}}_{+}^m$ (the nonnegative orthant where $\mathbf{z}⪰\mathbf{0}$).

We construct the primal problem as below:

$$\begin{array}{rlr}& \text{minimize }& \underset{\mathbf{z}⪰\mathbf{0}}{sup}L(\mathbf{x},\mathbf{z})\\ & \text{subject to }& \mathbf{x}\in X.\end{array}$$

1. Choose any $\mathbf{x}\in X$.

2. If any of the constraints $g_i(\mathbf{x})\le 0$ is violated, then $g_i(\mathbf{x})>0$ and hence $\underset{\mathbf{z}⪰\mathbf{0}}{sup}L(\mathbf{x},\mathbf{z})=\mathrm{\infty }$. We can easily achieve this by taking $z_i\to \mathrm{\infty }$.

3. If none of the constraints are invalidated, then by picking $\mathbf{z}=\mathbf{0}$, we have $\underset{\mathbf{z}⪰\mathbf{0}}{sup}L(\mathbf{x},\mathbf{z})=f(\mathbf{x})$.

4. Hence the problem is equivalent to the original problem.

We can now construct the dual problem as below:

$$\begin{array}{rlr}& \text{maximize }& \underset{\mathbf{x}\in X}{inf}L(\mathbf{x},\mathbf{z})\\ & \text{subject to }& \mathbf{z}⪰\mathbf{0}.\end{array}$$

Thus the primal problem is a minimax problem and the dual problem is a maximin problem with the Lagrangian playing the role of $\varphi$.

Under suitable conditions, the two problems have equal optimal value.

9.4.3.3. Minimax Equality

In the following, we will explore conditions under which

(9.4)$$\underset{\mathbf{z}\in Z}{sup}\underset{\mathbf{x}\in X}{inf}\varphi (\mathbf{x},\mathbf{z})=\underset{\mathbf{x}\in X}{inf}\underset{\mathbf{z}\in Z}{sup}\varphi (\mathbf{x},\mathbf{z})$$

and the infimum and the supremum are attained.

The key result is the saddle point theorem which guarantees the equality in (9.4) as well as the attainment of the infimum/supremum assuming convexity/concavity on $\varphi$ and compactness on $X$ and $Z$.

The compactness assumptions are restrictive. For example, in the duality theory, the Lagrange multipliers $\mathbf{z}⪰\mathbf{0}$ belong to the nonnegative orthant which is not compact.

The minimax theorem gives conditions guaranteeing the minimax equality (9.4), although it need not guarantee the attainment of the infimum and the supremum.

9.4.3.4. Minimax Inequality

Observation 9.5 (Minimax inequality)

We always have

(9.5)$$\underset{\mathbf{z}\in Z}{sup}\underset{\mathbf{x}\in X}{inf}\varphi (\mathbf{x},\mathbf{z})\le \underset{\mathbf{x}\in X}{inf}\underset{\mathbf{z}\in Z}{sup}\varphi (\mathbf{x},\mathbf{z}).$$

In other words, the optimal value of the maximin problem is less than or equal to the optimum value of the minimax problem.

Proof. We note that for every $\mathbf{z}\in Z$, we have

$$\underset{\mathbf{x}\in X}{inf}\varphi (\mathbf{x},\mathbf{z})\le \underset{\mathbf{x}\in X}{inf}\underset{\mathbf{z}\in Z}{sup}\varphi (\mathbf{x},\mathbf{z}).$$

Taking the supremum on the L.H.S., we obtain the desired inequality.

Thus, in order to show (9.4), it is sufficient to show that the reverse inequality holds.

9.4.3.5. Saddle Points

Definition 9.18 (Saddle point)

A pair of vectors ${\mathbf{x}}^{\ast }\in X$ and ${\mathbf{z}}^{\ast }\in Z$ is called a saddle point of $\varphi$ if

$$\varphi ({\mathbf{x}}^{\ast },\mathbf{z})\le \varphi ({\mathbf{x}}^{\ast },{\mathbf{z}}^{\ast })\le \varphi (\mathbf{x},{\mathbf{z}}^{\ast }),\mathrm{\forall }\mathbf{x}\in X,\mathrm{\forall }\mathbf{z}\in Z.$$

Remark 9.7 (Saddle point inequalities)

The pair $({\mathbf{x}}^{\ast },{\mathbf{z}}^{\ast })\in \mathbb{V}\oplus \mathbb{W}$ is a saddle point if and only if ${\mathbf{x}}^{\ast }\in X$, ${\mathbf{z}}^{\ast }\in Z$ and

$$\underset{\mathbf{z}\in Z}{sup}\varphi ({\mathbf{x}}^{\ast },\mathbf{z})=\varphi ({\mathbf{x}}^{\ast },{\mathbf{z}}^{\ast })=\underset{\mathbf{x}\in X}{inf}\varphi (\mathbf{x},{\mathbf{z}}^{\ast }).$$

This equality further implies that

$$\begin{array}{rl}& \underset{\mathbf{x}\in X}{inf}\underset{\mathbf{z}\in Z}{sup}\varphi (\mathbf{x},\mathbf{z})\\ & \le \underset{\mathbf{z}\in Z}{sup}\varphi ({\mathbf{x}}^{\ast },\mathbf{z})=\varphi ({\mathbf{x}}^{\ast },{\mathbf{z}}^{\ast })=\underset{\mathbf{x}\in X}{inf}\varphi (\mathbf{x},{\mathbf{z}}^{\ast })\\ & \le \underset{\mathbf{z}\in Z}{sup}\underset{\mathbf{x}\in X}{inf}\varphi (\mathbf{x},\mathbf{z}).\end{array}$$

In short

$$\underset{\mathbf{x}\in X}{inf}\underset{\mathbf{z}\in Z}{sup}\varphi (\mathbf{x},\mathbf{z})\le \varphi ({\mathbf{x}}^{\ast },{\mathbf{z}}^{\ast })\le \underset{\mathbf{z}\in Z}{sup}\underset{\mathbf{x}\in X}{inf}\varphi (\mathbf{x},\mathbf{z}).$$

Combined with the minimax inequality (9.5), it shows that if a saddle point exists, then the minimax equality (9.4) holds.

Theorem 9.35 (Saddle point = minimax equality)

A pair $({\mathbf{x}}^{\ast },{\mathbf{z}}^{\ast })$ is a saddle point of $\varphi$ if and only if the minimax equality (9.4) holds and ${\mathbf{x}}^{\ast }$ is an optimal solution of the minimax problem

$$\begin{array}{rlr}& \text{minimize }& \underset{\mathbf{z}\in Z}{sup}\varphi (\mathbf{x},\mathbf{z})\\ & \text{subject to }& \mathbf{x}\in X\end{array}$$

while ${\mathbf{z}}^{\ast }$ is the optimal solution of the maximin problem

$$\begin{array}{rlr}& \text{maximize }& \underset{\mathbf{x}\in X}{inf}\varphi (\mathbf{x},\mathbf{z})\\ & \text{subject to }& \mathbf{z}\in Z.\end{array}$$

Proof. Suppose that ${\mathbf{x}}^{\ast }$ is the optimal solution of the minimax problem and ${\mathbf{z}}^{\ast }$ is the optimal solution of the maximin problem.

1. From the minimax problem we obtain

   $$\underset{\mathbf{x}\in X}{inf}\underset{\mathbf{z}\in Z}{sup}\varphi (\mathbf{x},\mathbf{z})=\underset{\mathbf{z}\in Z}{sup}\varphi ({\mathbf{x}}^{\ast },\mathbf{z})\ge \varphi ({\mathbf{x}}^{\ast },{\mathbf{z}}^{\ast }).$$

2. From the maximin problem we obtain

   $$\underset{\mathbf{z}\in Z}{sup}\underset{\mathbf{x}\in X}{inf}\varphi (\mathbf{x},\mathbf{z})=\underset{\mathbf{x}\in X}{inf}\varphi (\mathbf{x},{\mathbf{z}}^{\ast })\le \varphi ({\mathbf{x}}^{\ast },{\mathbf{z}}^{\ast }).$$

3. Combining these inequalities, we have

   $$\begin{array}{rl}& \underset{\mathbf{z}\in Z}{sup}\underset{\mathbf{x}\in X}{inf}\varphi (\mathbf{x},\mathbf{z})=\underset{\mathbf{x}\in X}{inf}\varphi (\mathbf{x},{\mathbf{z}}^{\ast })\\ & \le \varphi ({\mathbf{x}}^{\ast },{\mathbf{z}}^{\ast })\\ & \le \underset{\mathbf{z}\in Z}{sup}\varphi ({\mathbf{x}}^{\ast },\mathbf{z})=\underset{\mathbf{x}\in X}{inf}\underset{\mathbf{z}\in Z}{sup}\varphi (\mathbf{x},\mathbf{z}).\end{array}$$

4. If the minimax equality (9.4) holds, then equality holds throughout above giving us

   $$\underset{\mathbf{x}\in X}{inf}\varphi (\mathbf{x},{\mathbf{z}}^{\ast })=\varphi ({\mathbf{x}}^{\ast },{\mathbf{z}}^{\ast })=\underset{\mathbf{z}\in Z}{sup}\varphi ({\mathbf{x}}^{\ast },\mathbf{z}).$$

5. Hence $({\mathbf{x}}^{\ast },{\mathbf{z}}^{\ast })$ is a saddle point of $\varphi$ as per Remark 9.7.

Conversely, assume that $({\mathbf{x}}^{\ast },{\mathbf{z}}^{\ast })$ is a saddle point of $\varphi$.

1. From Remark 9.7, we have

   $$\begin{array}{rl}& \underset{\mathbf{x}\in X}{inf}\underset{\mathbf{z}\in Z}{sup}\varphi (\mathbf{x},\mathbf{z})\\ & \le \underset{\mathbf{z}\in Z}{sup}\varphi ({\mathbf{x}}^{\ast },\mathbf{z})=\varphi ({\mathbf{x}}^{\ast },{\mathbf{z}}^{\ast })=\underset{\mathbf{x}\in X}{inf}\varphi (\mathbf{x},{\mathbf{z}}^{\ast })\\ & \le \underset{\mathbf{z}\in Z}{sup}\underset{\mathbf{x}\in X}{inf}\varphi (\mathbf{x},\mathbf{z}).\end{array}$$

2. The minimax inequality (9.5) gives us

   $$\underset{\mathbf{z}\in Z}{sup}\underset{\mathbf{x}\in X}{inf}\varphi (\mathbf{x},\mathbf{z})\le \underset{\mathbf{x}\in X}{inf}\underset{\mathbf{z}\in Z}{sup}\varphi (\mathbf{x},\mathbf{z}).$$

3. Thus, all the inequalities in the previous relationship must be equalities. We have

   $$\begin{array}{rl}& \underset{\mathbf{x}\in X}{inf}\underset{\mathbf{z}\in Z}{sup}\varphi (\mathbf{x},\mathbf{z})\\ & =\underset{\mathbf{z}\in Z}{sup}\varphi ({\mathbf{x}}^{\ast },\mathbf{z})=\varphi ({\mathbf{x}}^{\ast },{\mathbf{z}}^{\ast })=\underset{\mathbf{x}\in X}{inf}\varphi (\mathbf{x},{\mathbf{z}}^{\ast })\\ & =\underset{\mathbf{z}\in Z}{sup}\underset{\mathbf{x}\in X}{inf}\varphi (\mathbf{x},\mathbf{z}).\end{array}$$

4. Hence the minimax equality holds.

5. It also implies that ${\mathbf{x}}^{\ast }$ is an optimal solution of the minimax problem and ${\mathbf{z}}^{\ast }$ is the optimal solution of the maximin problem.

Observation 9.6 (Saddle points as a Cartesian product)

When the set of saddle points is nonempty, it can be written as a Cartesian product $X^{\ast }\times Z^{\ast }$ where $X^{\ast }$ is the set of optimal solutions of the minimax problem and the $Z^{\ast }$ is the set of optimal solutions of the maximin problem.

In other words, ${\mathbf{x}}^{\ast }$ and ${\mathbf{z}}^{\ast }$ can be chosen independently from the sets $X^{\ast }$ and $Z^{\ast }$ respectively to form a saddle point. This is a direct consequence of Theorem 9.35.

If the minimax equality (9.4) does not hold, then there is no saddle point even if the minimax and maximin problems have optimal solutions.

9.4.4. Min Common/Max Crossing Framework for Minimax

Recall that the minimax problem is given by

$$\underset{\mathbf{x}\in X}{inf}\underset{\mathbf{z}\in Z}{sup}\varphi (\mathbf{x},\mathbf{z}).$$

We add a linear perturbation to $\varphi$ and introduce a function $\psi :\mathbb{W}\to \bar{\mathbb{R}}$ as

$$\psi (\mathbf{u})=\underset{\mathbf{x}\in X}{inf}\underset{\mathbf{z}\in Z}{sup}\{\varphi (\mathbf{x},\mathbf{z})-⟨\mathbf{u},\mathbf{z}⟩\}.$$

We can see that

$$\psi (\mathbf{0})=\underset{\mathbf{x}\in X}{inf}\underset{\mathbf{z}\in Z}{sup}\varphi (\mathbf{x},\mathbf{z}).$$

The linear perturbation term impacts the optimum value of the minimax problem. We shall show that if $\psi$ changes in a “regular” manner, then the minimax equality is guaranteed.

9.4.4.1. Framework Definition

Definition 9.19 (Min common / max crossing framework for minimax problem)

We define the set $M$ required for the min common/max crossing framework as

$$M=\mathrm{epi}\psi$$

where $\psi :\mathbb{W}\to \bar{\mathbb{R}}$ is given by

(9.6)$$\psi (\mathbf{u})=\underset{\mathbf{x}\in X}{inf}\underset{\mathbf{z}\in Z}{sup}\{\varphi (\mathbf{x},\mathbf{z})-⟨\mathbf{u},\mathbf{z}⟩\}.$$

1. Recall that min common value is given by

   $$p^{\ast }=\underset{(\mathbf{0},p)\in M}{inf}p.$$

2. Note that for $\mathbf{u}=\mathbf{0}$, $M$ contains all the points $(\mathbf{0},t)$ such that $\psi (\mathbf{0})\le t$.

3. In particular, $(\mathbf{0},\psi (\mathbf{0}))\in M$ and if $(\mathbf{0},t)\in M$ then $\psi (\mathbf{0})\le t$.

4. Hence $p^{\ast }$ is given by

   $$p^{\ast }=\psi (\mathbf{0})=\underset{\mathbf{x}\in X}{inf}\underset{\mathbf{z}\in Z}{sup}\varphi (\mathbf{x},\mathbf{z}).$$

5. Since $M$ is an epigraph, hence the sets $M$ and $\bar{M}$ are identical in the min common/max crossing framework.

6. If $\psi$ is convex, then $M=\mathrm{epi}\psi$ is convex as desired in several results of the min common/max crossing framework.

The corresponding max crossing problem is given by:

$$\begin{array}{rlrl}& \text{maximize }& & q(\mathbf{a})\\ & \text{subject to }& & \mathbf{a}\in \mathbb{W}\end{array}$$

1. We note that

   (9.7)$$\begin{array}{rl}q(\mathbf{a})& =\underset{(\mathbf{u},t)\in \mathrm{epi}\psi }{inf}\{⟨\mathbf{u},\mathbf{a}⟩+t\}\\ & =\underset{(\mathbf{u},t)\in \psi (\mathbf{u})\le t}{inf}\{⟨\mathbf{u},\mathbf{a}⟩+t\}\\ & =\underset{\mathbf{u}\in \mathbb{W}}{inf}\{\psi (\mathbf{u})+⟨\mathbf{u},\mathbf{a}⟩\}.\end{array}$$

2. Its optimal value is denoted by $q^{\ast }$; i.e.,

   $$q^{\ast }=\underset{\mathbf{a}\in \mathbb{W}}{sup}q(\mathbf{a}).$$

9.4.4.2. Connection

Observation 9.7 (Connection between minimax equality and min common/max crossing framework)

1. By putting the definition of $\psi (\mathbf{u})$ in the expression for $q(\mathbf{a})$, we obtain

   $$\begin{array}{rl}q(\mathbf{a})& =\underset{\mathbf{u}\in \mathbb{W}}{inf}\{\psi (\mathbf{u})+⟨\mathbf{u},\mathbf{a}⟩\}\\ & =\underset{\mathbf{u}\in \mathbb{W}}{inf}\{\underset{\mathbf{x}\in X}{inf}\underset{\mathbf{z}\in Z}{sup}\{\varphi (\mathbf{x},\mathbf{z})-⟨\mathbf{u},\mathbf{z}⟩\}+⟨\mathbf{u},\mathbf{a}⟩\}\\ & =\underset{\mathbf{u}\in \mathbb{W}}{inf}\underset{\mathbf{x}\in X}{inf}\underset{\mathbf{z}\in Z}{sup}\{\varphi (\mathbf{x},\mathbf{z})+⟨\mathbf{a}-\mathbf{z},\mathbf{u}⟩\}.\end{array}$$

2. In particular, for every $\mathbf{a}\in Z$, if we set $\mathbf{z}=\mathbf{a}$ in this relation, we can see that

   $$\underset{\mathbf{x}\in X}{inf}\varphi (\mathbf{x},\mathbf{a})\le q(\mathbf{a})\mathrm{\forall }\mathbf{a}\in Z.$$

3. From the weak duality principle, we have $q^{\ast }\le p^{\ast }$.

4. We have established that $p^{\ast }=\psi (\mathbf{0})$.

5. We can now see that

   $$\begin{array}{rl}\underset{\mathbf{z}\in Z}{sup}\underset{\mathbf{x}\in X}{inf}\varphi (\mathbf{x},\mathbf{z})& =\underset{\mathbf{a}\in Z}{sup}\underset{\mathbf{x}\in X}{inf}\varphi (\mathbf{x},\mathbf{a})\\ & \le \underset{\mathbf{a}\in Z}{sup}q(\mathbf{a})\\ & \le \underset{\mathbf{a}\in \mathbb{W}}{sup}q(\mathbf{a})\\ & =q^{\ast }\\ & \le p^{\ast }\\ & =\psi (\mathbf{0})\\ & =\underset{\mathbf{x}\in X}{inf}\underset{\mathbf{z}\in Z}{sup}\varphi (\mathbf{x},\mathbf{z}).\end{array}$$

6. This is nothing but the minimax inequality (9.5).

7. We can see that if the minimax equality (9.4) holds, then all inequalities in the previous relation turn into equalities and we have $q^{\ast }=p^{\ast }$.

8. In other words, if the minimax equality holds, then the optimal values of the min common and max crossing problems are equal.

9.4.4.3. Convexity of $\psi$

Lemma 9.2 (Convexity of $\varphi$ w.r.t. $\mathbf{x}$ and convexity of $\psi$)

Let $X$ be a nonempty convex subset of $\mathbb{V}$ and $Z$ be a nonempty subset of $\mathbb{W}$. Let $\varphi :\mathbb{V}\oplus \mathbb{W}\to \mathbb{R}$ be a function with $\mathrm{dom}\varphi =X\times Z$. Assume that for each $\mathbf{z}\in Z$, the function $\varphi (\cdot ,\mathbf{z}):\mathbb{V}\to \mathbb{R}$ is convex. Then the function $\psi$ as defined in (9.6) is convex.

Proof. Recall that

$$\psi (\mathbf{u})=\underset{\mathbf{x}\in X}{inf}\underset{\mathbf{z}\in Z}{sup}\{\varphi (\mathbf{x},\mathbf{z})-⟨\mathbf{u},\mathbf{z}⟩\}.$$

1. Fix some $\mathbf{z}\in Z$.

2. Consider the function $f_z(\mathbf{x},\mathbf{u})=\varphi (\mathbf{x},\mathbf{z})-⟨\mathbf{u},\mathbf{z}⟩$.

3. Clearly, $f_z$ is convex for each $\mathbf{z}\in Z$ by hypothesis.

4. Taking the pointwise supremum over $\mathbf{z}\in Z$, the function

   $$\begin{array}{r}F(\mathbf{x},\mathbf{u})=\{\begin{array}{ll}\underset{\mathbf{z}\in Z}{sup}\{\varphi (\mathbf{x},\mathbf{z})-⟨\mathbf{u},\mathbf{z}⟩\}& \mathbf{x}\in X;\\ \mathrm{\infty }& \mathbf{x}\notin X.\end{array}\end{array}$$

   is also convex (over $\mathbf{x}$ and $\mathbf{u}$).

5. We now have

   $$\psi (\mathbf{u})=\underset{\mathbf{x}\in \mathbb{V}}{inf}F(\mathbf{x},\mathbf{u}).$$

6. Since partial minimization preserves convexity, hence $\psi$ is convex.

9.4.4.4. Minimax Equality Strong Duality Equivalence Conditions

Lemma 9.3 (Closedness and convexity of $-\varphi$ w.r.t. $\mathbf{z}$ and minimax equality)

Let $X$ be a nonempty convex subset of $\mathbb{V}$ and $Z$ be a nonempty subset of $\mathbb{W}$. Let $\varphi :\mathbb{V}\oplus \mathbb{W}\to \mathbb{R}$ be a function with $\mathrm{dom}\varphi =X\times Z$. Assume that for each $\mathbf{x}\in X$, the function $-\varphi (\mathbf{x},\cdot )\to \mathbb{R}$ is closed and convex. Then the function $q:\mathbb{W}\to \bar{\mathbb{R}}$ given by

$$q(\mathbf{a})=\underset{(\mathbf{u},t)\in \mathrm{epi}\psi }{inf}\{⟨\mathbf{u},\mathbf{a}⟩+t\},\mathbf{a}\in \mathbb{W},$$

where $\psi$ as defined in (9.6), satisfies

$$\begin{array}{r}q(\mathbf{a})=\{\begin{array}{ll}\underset{\mathbf{x}\in X}{inf}\varphi (\mathbf{x},\mathbf{a})& \mathbf{a}\in Z;\\ -\mathrm{\infty }& \mathbf{a}\notin Z.\end{array}\end{array}$$

Furthermore, we have $q^{\ast }=p^{\ast }$ if and only if the minimax equality (9.4) holds.

Proof. We shall show the following one by one.

1. $q(\mathbf{a})\ge \underset{\mathbf{x}\in X}{inf}\varphi (\mathbf{x},\mathbf{a})\mathrm{\forall }\mathbf{a}\in Z$.

2. $q(\mathbf{a})\le \underset{\mathbf{x}\in X}{inf}\varphi (\mathbf{x},\mathbf{a})\mathrm{\forall }\mathbf{a}\in Z$.

3. $q(\mathbf{a})=-\mathrm{\infty }\mathrm{\forall }\mathbf{a}\notin Z$.

(1)

1. We have already established in (9.7) that

   $$q(\mathbf{a})=\underset{\mathbf{u}\in \mathbb{W}}{inf}\{\psi (\mathbf{u})+⟨\mathbf{u},\mathbf{a}⟩\}.$$

2. By using the definition of $\psi$, we further established that

   $$q(\mathbf{a})=\underset{\mathbf{u}\in \mathbb{W}}{inf}\underset{\mathbf{x}\in X}{inf}\underset{\mathbf{z}\in Z}{sup}\{\varphi (\mathbf{x},\mathbf{z})+⟨\mathbf{a}-\mathbf{z},\mathbf{u}⟩\}.$$

3. By rearranging the order of infimum operations, we have

   $$q(\mathbf{a})=\underset{\mathbf{x}\in X}{inf}\underset{\mathbf{u}\in \mathbb{W}}{inf}\underset{\mathbf{z}\in Z}{sup}\{\varphi (\mathbf{x},\mathbf{z})+⟨\mathbf{a}-\mathbf{z},\mathbf{u}⟩\}.$$

4. For any $\mathbf{a}\in Z$ we have

   $$\begin{array}{rl}\underset{\mathbf{z}\in Z}{sup}\{\varphi (\mathbf{x},\mathbf{z})+⟨\mathbf{a}-\mathbf{z},\mathbf{u}⟩\}& \ge \varphi (\mathbf{x},\mathbf{a})+⟨\mathbf{a}-\mathbf{a},\mathbf{u}⟩\\ & =\varphi (\mathbf{x},\mathbf{a})\mathrm{\forall }\mathbf{x}\in X,\mathrm{\forall }\mathbf{u}\in \mathbb{W}.\end{array}$$

5. This in turn implies that

   $$q(\mathbf{a})\ge \underset{\mathbf{x}\in X}{inf}\varphi (\mathbf{x},\mathbf{a})\mathrm{\forall }\mathbf{a}\in Z.$$

(2)

1. Let $r_x:\mathbb{W}\to \mathbb{R}$ be given by

   $$r_x(\mathbf{z})=-\varphi (\mathbf{x},\mathbf{z}).$$

2. By hypothesis $r_x$ is closed and convex.

3. Let $\mathbf{a}\in Z$.

4. Fix some $\mathbf{x}\in X$.

5. Since $r_x$ is a closed and convex function, hence $\mathrm{epi}{r}_x$ is a closed and convex set.

6. Since $\mathbf{a}\in Z$, hence the point $(\mathbf{a},r_x(\mathbf{a}))\in \mathrm{epi}{r}_x$.

7. For some $ϵ>0$, consider the point $(\mathbf{a},r_x(\mathbf{a})-ϵ)$.

8. Clearly $(\mathbf{a},r_x(\mathbf{a})-ϵ)\notin \mathrm{epi}{r}_x$.

9. By definition of $r_x$, $r_x(\mathbf{z})$ is finite for all $\mathbf{z}\in Z$, $Z$ is nonempty and $\mathrm{epi}{r}_x$ is closed.

10. Since $r_x(\mathbf{z})$ is finite for all $\mathbf{z}\in Z$, the epigraph doesn’t contain any vertical lines.

11. Hence, due to Theorem 9.30, there exists a nonvertical hyperplane that strongly separates the point $(\mathbf{a},r_x(\mathbf{a})-ϵ)$ from $\mathrm{epi}{r}_x$.

12. Hence there exists a normal vector $(\mathbf{u},1)$ and a scalar $c$ such that

    $$⟨\mathbf{a},\mathbf{u}⟩+(r_x(\mathbf{a})-ϵ)<c<⟨\mathbf{u},\mathbf{z}⟩+r_x(\mathbf{z})\mathrm{\forall }\mathbf{z}\in Z.$$

13. Substituting $r_x(\mathbf{z})=-\varphi (\mathbf{x},\mathbf{z})$, we get

    $$⟨\mathbf{a},\mathbf{u}⟩+(-\varphi (\mathbf{x},\mathbf{a})-ϵ)<⟨\mathbf{u},\mathbf{z}⟩-\varphi (\mathbf{x},\mathbf{z}).$$

14. Rearranging, we get

    $$\varphi (\mathbf{x},\mathbf{z})+⟨\mathbf{a}-\mathbf{z},\mathbf{u}⟩<\varphi (\mathbf{x},\mathbf{a})+ϵ\mathrm{\forall }\mathbf{z}\in Z.$$

15. Letting $ϵ\downarrow 0$, we have

    $$\varphi (\mathbf{x},\mathbf{z})+⟨\mathbf{a}-\mathbf{z},\mathbf{u}⟩\le \varphi (\mathbf{x},\mathbf{a})\mathrm{\forall }\mathbf{z}\in Z.$$

16. We further note that

    $$\underset{\mathbf{u}\in \mathbb{W}}{inf}\underset{\mathbf{z}\in Z}{sup}\{\varphi (\mathbf{x},\mathbf{z})+⟨\mathbf{a}-\mathbf{z},\mathbf{u}⟩\}\le \underset{\mathbf{z}\in Z}{sup}\{\varphi (\mathbf{x},\mathbf{z})+⟨\mathbf{a}-\mathbf{z},\mathbf{u}⟩\}\le \varphi (\mathbf{x},\mathbf{a}).$$

17. Taking infimum over $\mathbf{x}\in X$ on the L.H.S., we obtain

    $$q(\mathbf{a})=\underset{\mathbf{x}\in X}{inf}\underset{\mathbf{u}\in \mathbb{W}}{inf}\underset{\mathbf{z}\in Z}{sup}\{\varphi (\mathbf{x},\mathbf{z})+⟨\mathbf{a}-\mathbf{z},\mathbf{u}⟩\}\le \underset{\mathbf{x}\in X}{inf}\varphi (\mathbf{x},\mathbf{a})$$

    as desired.

(3)

1. Take any $\mathbf{a}\notin Z$.

2. Fix an arbitrary $\mathbf{x}\in X$.

3. Consider a sequence $\{t_k\}$ such that $t_k\to \mathrm{\infty }$.

4. Since $\mathbf{a}\notin Z$, hence $(\mathbf{a},t_k)\notin \mathrm{epi}{r}_x$ for every $k$.

5. Again applying Theorem 9.30, for each $k$, there exists a nonvertical hyperplane strongly separating $(\mathbf{a},t_k)$ from $\mathrm{epi}{r}_x$.

6. Hence for each $k$, there exists a normal vector $({\mathbf{u}}_k,1)$ such that

   $$⟨\mathbf{a},{\mathbf{u}}_k⟩+t_k<⟨\mathbf{z},{\mathbf{u}}_k⟩-\varphi (\mathbf{x},\mathbf{z})\mathrm{\forall }\mathbf{z}\in Z.$$

7. Rearranging, we have

   $$\varphi (\mathbf{x},\mathbf{z})+⟨\mathbf{a}-\mathbf{z},{\mathbf{u}}_k⟩<-t_k,\mathrm{\forall }\mathbf{z}\in Z,\mathrm{\forall }k.$$

8. Thus, we have

   $$\underset{\mathbf{u}\in \mathbb{W}}{inf}\underset{\mathbf{z}\in Z}{sup}\{\varphi (\mathbf{x},\mathbf{z})+⟨\mathbf{a}-\mathbf{z},\mathbf{u}⟩\}\le \underset{\mathbf{z}\in Z}{sup}\{\varphi (\mathbf{x},\mathbf{z})+⟨\mathbf{a}-\mathbf{z},{\mathbf{u}}_k⟩\}\le -t_k\mathrm{\forall }k.$$

9. Taking the limit on the R.H.S. as $k\to \mathrm{\infty }$, we can see that

   $$\underset{\mathbf{u}\in \mathbb{W}}{inf}\underset{\mathbf{z}\in Z}{sup}\{\varphi (\mathbf{x},\mathbf{z})+⟨\mathbf{a}-\mathbf{z},\mathbf{u}⟩\}=-\mathrm{\infty }\mathrm{\forall }\mathbf{x}\in X.$$

10. Finally, taking the infimum over $\mathbf{x}\in X$, we can see that

    $$q(\mathbf{a})=-\mathrm{\infty }.$$

By Observation 9.7, if minimax equality holds, then $q^{\ast }=p^{\ast }$. For the converse, we now assume that $q^{\ast }=p^{\ast }$. Then

$$\begin{array}{rl}& \underset{\mathbf{x}\in X}{inf}\underset{\mathbf{z}\in Z}{sup}\varphi (\mathbf{x},\mathbf{z})\\ & =\psi (\mathbf{0})=p^{\ast }=q^{\ast }\\ & =\underset{\mathbf{a}\in \mathbb{W}}{sup}q(\mathbf{a})=\underset{\mathbf{z}\in Z}{sup}q(\mathbf{z})\\ & =\underset{\mathbf{z}\in Z}{sup}\underset{\mathbf{x}\in X}{inf}\varphi (\mathbf{x},\mathbf{z}).\end{array}$$

Thus the minimax equality holds.

9.4.5. Minimax Theorems

9.4.5.1. First Theorem

Theorem 9.36 (Minimax theorem I)

Let $X$ be a nonempty convex subset of $\mathbb{V}$ and $Z$ be a nonempty subset of $\mathbb{W}$. Let $\varphi :\mathbb{V}\oplus \mathbb{W}\to \mathbb{R}$ be a function with $\mathrm{dom}\varphi =X\times Z$. Assume that for each $\mathbf{z}\in Z$, the function $\varphi (\cdot ,\mathbf{z}):\mathbb{V}\to \mathbb{R}$ is convex, and for each $\mathbf{x}\in X$, the function $-\varphi (\mathbf{x},\cdot ):\mathbb{W}\to \mathbb{R}$ is closed and convex. Assume further that

$$\underset{\mathbf{x}\in X}{inf}\underset{\mathbf{z}\in Z}{sup}\varphi (\mathbf{x},\mathbf{z})<\mathrm{\infty }.$$

Then, the minimax equality (9.4) holds; i.e.,

$$\underset{\mathbf{z}\in Z}{sup}\underset{\mathbf{x}\in X}{inf}\varphi (\mathbf{x},\mathbf{z})=\underset{\mathbf{x}\in X}{inf}\underset{\mathbf{z}\in Z}{sup}\varphi (\mathbf{x},\mathbf{z}),$$

if and only if the function $\psi$ as defined in (9.6) is lower semicontinuous at $\mathbf{u}=\mathbf{0}$; i.e.,

$$\psi (\mathbf{0})\le \underset{k\to \mathrm{\infty }}{lim inf}\psi ({\mathbf{u}}_k)$$

for every sequence $\{{\mathbf{u}}_k\}$ with ${\mathbf{u}}_k\to \mathbf{0}$.

Proof. The proof consists of establishing the correspondence between the conditions in this result and the conditions in the first min common/max crossing theorem (Theorem 9.33).

1. We choose the set $M$ as described in Definition 9.19, to be the epigraph of the function $\psi$.

   $$M=\bar{M}=\mathrm{epi}\psi =\{(\mathbf{u},t)\in \mathbb{W}\oplus \mathbb{R}|\psi (\mathbf{u})\le t\}.$$

2. We have shown in Definition 9.19 that $p^{\ast }=\psi (\mathbf{0})=\underset{\mathbf{x}\in X}{inf}\underset{\mathbf{z}\in Z}{sup}\varphi (\mathbf{x},\mathbf{z})$.

3. By hypothesis, $p^{\ast }<\mathrm{\infty }$.

4. Hence the first assumption of Theorem 9.33 is satisfied.

5. Following Lemma 9.2, $\psi$ is convex.

6. Hence $M=\mathrm{epi}\psi$ is also convex.

7. Hence the second assumption of Theorem 9.33 is satisfied.

8. Finally, the condition

   $$\psi (\mathbf{0})\le \underset{k\to \mathrm{\infty }}{lim inf}\psi ({\mathbf{u}}_k)$$

   is equivalent to the condition of Theorem 9.33 that for every sequence $\{({\mathbf{u}}_k,t_k)\}$ of $M$ with ${\mathbf{u}}_k\to \mathbf{0}$.

   $$p^{\ast }\le \underset{k\to \mathrm{\infty }}{lim inf}{t}_k$$

   holds true.

   1. We have $t_k\ge \psi ({\mathbf{u}}_k)$.

   2. Hence

      $$\underset{k\to \mathrm{\infty }}{lim inf}{t}_k\ge \underset{k\to \mathrm{\infty }}{lim inf}\psi ({\mathbf{u}}_k)\ge \psi (\mathbf{0})=p^{\ast }.$$

9. Following Theorem 9.33, this condition holds if and only if $p^{\ast }=q^{\ast }$.

10. Since $-\varphi (\mathbf{x},\cdot )$ is closed and convex, hence following Lemma 9.3, this condition holds if and only if minimax equality holds.

9.4.5.2. Second Theorem

We can adapt the argument of first minimax theorem to include conditions on the lines of the second min common/max crossing theorem Theorem 9.34.

Theorem 9.37 (Minimax theorem II)

Let $X$ be a nonempty convex subset of $\mathbb{V}$ and $Z$ be a nonempty subset of $\mathbb{W}$. Let $\varphi :\mathbb{V}\oplus \mathbb{W}\to \mathbb{R}$ be a function with $\mathrm{dom}\varphi =X\times Z$. Assume that for each $\mathbf{z}\in Z$, the function $\varphi (\cdot ,\mathbf{z}):\mathbb{V}\to \mathbb{R}$ is convex, and for each $\mathbf{x}\in X$, the function $-\varphi (\mathbf{x},\cdot ):\mathbb{W}\to \mathbb{R}$ is closed and convex. Assume further that

$$-\mathrm{\infty }<\underset{\mathbf{x}\in X}{inf}\underset{\mathbf{z}\in Z}{sup}\varphi (\mathbf{x},\mathbf{z})$$

and that $\mathbf{0}$ lies in the relative interior of the effective domain of the function $\psi$ as defined in (9.6). Then, the minimax equality (9.4) holds; i.e.,

$$\underset{\mathbf{z}\in Z}{sup}\underset{\mathbf{x}\in X}{inf}\varphi (\mathbf{x},\mathbf{z})=\underset{\mathbf{x}\in X}{inf}\underset{\mathbf{z}\in Z}{sup}\varphi (\mathbf{x},\mathbf{z}),$$

and the supremum over $Z$ in the left hand side is finite and is attained. Furthermore, the set of $\mathbf{z}\in Z$ attaining this supremum is compact if and only if $\mathbf{0}$ lies in the interior of the effective domain of $\psi$.

9.4.6. Saddle Point Theorems

1. From the first minimax theorem (Theorem 9.36), we can see that minimax equality is satisfied if and only if the function $\psi$ is lower semicontinuous at $\mathbf{u}=\mathbf{0}$.

2. If $\psi$ is closed, then it will be lower semicontinuous.

3. The proof of Lemma 9.2 shows that $\psi$ can be written as a partial minimization of $F$

   $$\psi (\mathbf{u})=\underset{\mathbf{x}\in \mathbb{V}}{inf}F(\mathbf{x},\mathbf{u}).$$

   where $F:\mathbb{V}\oplus \mathbb{W}\to (-\mathrm{\infty },\mathrm{\infty }]$ is given by

   $$\begin{array}{r}F(\mathbf{x},\mathbf{u})=\{\begin{array}{ll}\underset{\mathbf{z}\in Z}{sup}\{\varphi (\mathbf{x},\mathbf{z})-⟨\mathbf{u},\mathbf{z}⟩\}& \mathbf{x}\in X;\\ \mathrm{\infty }& \mathbf{x}\notin X.\end{array}\end{array}$$

4. The results in Partial Minimization and Closedness can be used to guarantee the closedness of $\psi$.

5. These results can also guarantee that the infimum of $F$ over $\mathbf{x}$ is attained.

6. In particular $\psi (\mathbf{0})$ will be finite and hence guaranteeing that the optimal value of the minimax problem is finite.

Definition 9.20 (Auxiliary functions for the minimax problem)

Let $X$ be a nonempty convex subset of $\mathbb{V}$ and $Z$ be a nonempty subset of $\mathbb{W}$. Let $\varphi :\mathbb{V}\oplus \mathbb{W}\to \mathbb{R}$ be a function with $\mathrm{dom}\varphi =X\times Z$.

For each $\mathbf{z}\in Z$, the function ${\eta }_z:\mathbb{V}\to (-\mathrm{\infty },\mathrm{\infty }]$ is defined as

$$\begin{array}{r}{\eta }_z(\mathbf{x})=\{\begin{array}{ll}\varphi (\mathbf{x},\mathbf{z})& \mathbf{x}\in X;\\ \mathrm{\infty }& \mathbf{x}\notin X.\end{array}\end{array}$$

For each $\mathbf{x}\in X$, the function ${\rho }_x:\mathbb{W}\to (-\mathrm{\infty },\mathrm{\infty }]$ is defined as

$$\begin{array}{r}{\rho }_x(\mathbf{z})=\{\begin{array}{ll}-\varphi (\mathbf{x},\mathbf{z})& \mathbf{z}\in Z;\\ \mathrm{\infty }& \mathbf{z}\notin Z.\end{array}\end{array}$$

The function $\eta :\mathbb{V}\to (-\mathrm{\infty },\mathrm{\infty }]$ is defined as

$$\eta (\mathbf{x})=\underset{\mathbf{z}\in Z}{sup}{\eta }_z(\mathbf{x}),\mathbf{x}\in \mathbb{V}.$$

The function $\rho :\mathbb{W}\to (-\mathrm{\infty },\mathrm{\infty }]$ is defined as

$$\rho (\mathbf{z})=\underset{\mathbf{x}\in X}{sup}{\rho }_x(\mathbf{z}),\mathbf{z}\in \mathbb{W}.$$

Following remarks are in order.

1. If ${\eta }_z$ is closed and convex for each $\mathbf{z}\in Z$, then $\eta$ is closed and convex due to Theorem 8.114.

2. If ${\rho }_x$ is closed and convex for each $\mathbf{x}\in X$, then $\rho$ is closed and convex due to Theorem 8.114.

3. By definition, $\eta (\mathbf{x})>-\mathrm{\infty }$ for every $\mathbf{x}\in X$.

4. $\eta$ can be proper only if $\eta (\mathbf{x})<\mathrm{\infty }$ for some $\mathbf{x}\in X$.

5. Equivalently, for the optimal minimax value

   $$\underset{\mathbf{x}\in X}{inf}\underset{\mathbf{z}\in Z}{sup}\varphi (\mathbf{x},\mathbf{z})<\mathrm{\infty }$$

   must hold for $\eta$ to be proper.

6. Similarly, $\rho (\mathbf{z})>-\mathrm{\infty }$ for every $\mathbf{z}\in Z$.

7. $\rho$ can be proper only if $\rho (\mathbf{z})<\mathrm{\infty }$ for some $\mathbf{z}\in Z$.

8. This is possible only if

   $$\underset{\mathbf{z}\in Z}{inf}\underset{\mathbf{x}\in X}{sup}(-\varphi (\mathbf{x},\mathbf{z}))<\mathrm{\infty }.$$

9. Equivalently, for the optimal maximin value

   $$-\mathrm{\infty }<\underset{\mathbf{z}\in Z}{sup}\underset{\mathbf{x}\in X}{inf}\varphi (\mathbf{x},\mathbf{z})$$

   must hold true.

10. The set of minimizers of $\eta$ are the optimal points for the minimax problem: $X^{\ast }$.

11. The set of minimizers of $\rho$ are the optimal points of the maximin problem: $Z^{\ast }$.

9.4.6.1. Minimax Equality and Attainment of Minimax Solution

In the following results, we provide conditions under which the minimax equality is attained and the the set of optimal solutions for the minimax problem is nonempty.

Theorem 9.38 (Compact sublevel sets of $\eta$)

Assume the following:

1. ${\eta }_z$ is closed and convex for every $\mathbf{z}\in Z$.

2. ${\rho }_x$ is closed and convex for every $\mathbf{x}\in X$.

3. The optimal minimax value is less than infinity

   $$\underset{\mathbf{x}\in X}{inf}\underset{\mathbf{z}\in Z}{sup}\varphi (\mathbf{x},\mathbf{z})<\mathrm{\infty }.$$

4. The sublevel sets of $\eta$ are compact.

Then the minimax equality (9.4) holds and the set of optimal points for the minimax problem $X^{\ast }$ is nonempty and compact.

Proof. .

1. Under the assumptions above, the function $\eta$ is proper, closed and convex.

2. By definition $F(\mathbf{x},\mathbf{u})>-\mathrm{\infty }$ for every $\mathbf{x},\mathbf{u}$.

3. Note that $F(\mathbf{x},\mathbf{0})=\eta (\mathbf{x})$.

4. Since $\eta$ is proper, hence there exists $\mathbf{x}\in X$ such that $F(\mathbf{x},\mathbf{0})<\mathrm{\infty }$.

5. Hence $F$ is also proper.

6. $F$ is also closed and convex.

   1. Fix some $\mathbf{z}\in Z$.

   2. Consider the function $f_z(\mathbf{x},\mathbf{u})={\eta }_z(\mathbf{x})-⟨\mathbf{u},\mathbf{z}⟩$.

   3. ${\eta }_z$ is closed and convex for every $\mathbf{z}$ by hypothesis.

   4. Hence $f_z$ is closed and convex for every $\mathbf{z}$.

   5. Taking the pointwise supremum over $\mathbf{z}\in Z$, $F$ is closed and convex.

7. The sets

   $$\{\mathbf{x}|F(\mathbf{x},\mathbf{0})\le t\}=\{\mathbf{x}|\eta (\mathbf{x})\le t\}$$

   are the sublevel sets of $\eta$ which are compact for every $t$ by hypothesis.

8. We can easily select a scalar for which the sublevel set of $\eta$ is also nonempty since $\eta$ is proper.

9. Hence, due to Theorem 8.120, the function $\psi$ which is a partial minimization of $F$ over $\mathbf{x}$ is proper, closed and convex.

10. Since $\psi$ is closed, hence it is lower semicontinuous.

11. In particular, $\psi$ is l.s.c. at $\mathbf{u}=\mathbf{0}$.

12. Hence due to Theorem 9.36, the minimax equality holds.

13. Since $X^{\ast }$ is the set of minimizers of $\eta$, $\eta$ is proper and closed, and the sublevel sets of $\eta$ are compact, hence $X^{\ast }$ is nonempty and compact due to Weierstrass’ theorem (Theorem 7.9).

Theorem 9.39 (Recession and constancy space of $\eta$)

Assume the following:

1. ${\eta }_z$ is closed and convex for every $\mathbf{z}\in Z$.

2. ${\rho }_x$ is closed and convex for every $\mathbf{x}\in X$.

3. The optimal minimax value is less than infinity

   $$\underset{\mathbf{x}\in X}{inf}\underset{\mathbf{z}\in Z}{sup}\varphi (\mathbf{x},\mathbf{z})<\mathrm{\infty }.$$

4. The recession cone and constancy space of the function $\eta$ are equal.

Then the minimax equality (9.4) holds and the set of optimal points for the minimax problem $X^{\ast }$ is nonempty.

Theorem 9.40 ($F$ domain as a set of linear inequalities)

Assume the following:

1. ${\eta }_z$ is closed and convex for every $\mathbf{z}\in Z$.

2. ${\rho }_x$ is closed and convex for every $\mathbf{x}\in X$.

3. The optimal minimax value is less than infinity

   $$\underset{\mathbf{x}\in X}{inf}\underset{\mathbf{z}\in Z}{sup}\varphi (\mathbf{x},\mathbf{z})<\mathrm{\infty }.$$

4. The function

   $$\begin{array}{r}F(\mathbf{x},\mathbf{u})=\{\begin{array}{ll}\underset{\mathbf{z}\in Z}{sup}\{\varphi (\mathbf{x},\mathbf{z})-⟨\mathbf{u},\mathbf{z}⟩\}& \mathbf{x}\in X;\\ \mathrm{\infty }& \mathbf{x}\notin X\end{array}\end{array}$$

   has the form

   $$\begin{array}{r}F(\mathbf{x},\mathbf{u})=\{\begin{array}{ll}\bar{F}(\mathbf{x},\mathbf{u})& (\mathbf{x},\mathbf{u})\in C;\\ \mathrm{\infty }& (\mathbf{x},\mathbf{u})\notin C\end{array}\end{array}$$

   where $\bar{F}$ is a proper, closed, and convex function on $\mathbb{V}\oplus \mathbb{W}$ and $C$ is specified by linear inequalities; i.e,

   $$C=\{(\mathbf{x},\mathbf{u})|\mathbf{A}\mathbf{x}+\mathbf{B}\mathbf{u}⪯\mathbf{b}\},$$

   where $\mathbf{A},\mathbf{B}$ are matrices and $\mathbf{b}$ is a vector.

5. Every common direction of recession of $C$ and $\bar{F}$ is a direction along which $\bar{F}$ is constant.

Then the minimax equality (9.4) holds and the set of optimal points for the minimax problem $X^{\ast }$ is nonempty.

Theorem 9.41 (Quadratic form $\varphi$)

Assume the following:

1. $\mathbb{V}={\mathbb{R}}^n$ and $\mathbb{W}={\mathbb{R}}^m$.

2. The function $\varphi$ has a quadratic form

   $$\varphi (\mathbf{x},\mathbf{z})={\mathbf{x}}^T\mathbf{Q}\mathbf{x}+{\mathbf{c}}^T\mathbf{x}+{\mathbf{z}}^T\mathbf{M}\mathbf{x}-{\mathbf{z}}^T\mathbf{R}\mathbf{z}-{\mathbf{d}}^T\mathbf{z}$$

   where $\mathbf{Q}$ and $\mathbf{R}$ are symmetric matrices, $\mathbf{M}$ is a matrix, and $c$ and $d$ are vectors.

3. $Z={\mathbb{R}}^m$.

4. $X$ is a set of the form

   $$X=\{\mathbf{x}|{\mathbf{x}}^T{\mathbf{Q}}_j\mathbf{x}+{\mathbf{a}}_j^T\mathbf{x}+b_j\le 0,j=1,\dots ,r\}$$

   where ${\mathbf{Q}}_j$ are symmetric positive semidefinite matrices, ${\mathbf{a}}_j$ are vectors and $b_j$ are scalars.

5. ${\eta }_z$ is closed and convex for every $\mathbf{z}\in Z$.

6. ${\rho }_x$ is closed and convex for every $\mathbf{x}\in X$.

7. The optimal minimax value satisfies

   $$-\mathrm{\infty }<\underset{\mathbf{x}\in X}{inf}\underset{\mathbf{z}\in Z}{sup}\varphi (\mathbf{x},\mathbf{z})<\mathrm{\infty }.$$

Then the minimax equality (9.4) holds and the set of optimal points for the minimax problem $X^{\ast }$ is nonempty.

9.4.6.2. Existence of Saddle Points

Theorem 9.42 (Compact sublevel sets of $\eta$ and $\rho$)

Assume the following:

1. ${\eta }_z$ is closed and convex for every $\mathbf{z}\in Z$.

2. ${\rho }_x$ is closed and convex for every $\mathbf{x}\in X$.

3. Assume that either

   $$\underset{\mathbf{x}\in X}{inf}\underset{\mathbf{z}\in Z}{sup}\varphi (\mathbf{x},\mathbf{z})<\mathrm{\infty }$$

   or

   $$-\mathrm{\infty }<\underset{\mathbf{z}\in Z}{sup}\underset{\mathbf{x}\in X}{inf}\varphi (\mathbf{x},\mathbf{z})$$

   holds true.

4. The sublevel sets of $\eta$ and $\rho$ are compact.

Then the set of saddle points of $\varphi$ is nonempty and compact.

Proof. First assume that $\underset{\mathbf{x}\in X}{inf}\underset{\mathbf{z}\in Z}{sup}\varphi (\mathbf{x},\mathbf{z})<\mathrm{\infty }$.

1. By applying Theorem 9.38, minimax equality holds and $X^{\ast }$ is nonempty.

2. Hence $\underset{\mathbf{x}\in X}{inf}\underset{\mathbf{z}\in Z}{sup}\varphi (\mathbf{x},\mathbf{z})$ is finite.

3. Due to minimax equality:

   $$-\mathrm{\infty }<\underset{\mathbf{z}\in Z}{sup}\underset{\mathbf{x}\in X}{inf}\varphi (\mathbf{x},\mathbf{z})=\underset{\mathbf{x}\in X}{inf}\underset{\mathbf{z}\in Z}{sup}\varphi (\mathbf{x},\mathbf{z})<\mathrm{\infty }.$$

4. We reverse the roles of $\mathbf{x}$ and $\mathbf{z}$ and the sign of $\varphi$ and apply Theorem 9.38 again to show that $Z^{\ast }$ is nonempty and compact set.

5. The set of saddle points is a Cartesian product of $X^{\ast }$ and $Z^{\ast }$.

6. Since both $X^{\ast }$ and $Z^{\ast }$ are nonempty and compact, hence $X^{\ast }\times Z^{\ast }$ is also nonempty and compact.

Now assume that $-\mathrm{\infty }<\underset{\mathbf{z}\in Z}{sup}\underset{\mathbf{x}\in X}{inf}\varphi (\mathbf{x},\mathbf{z})$.

1. Then $\underset{\mathbf{z}\in Z}{inf}\underset{\mathbf{x}\in X}{sup}(-\varphi (\mathbf{x},\mathbf{z}))<\mathrm{\infty }$.

2. we can then reverse the role of $\mathbf{x}$ and $\mathbf{z}$ in the preceding argument.

Theorem 9.43 (Recession cones and constancy spaces of $\eta$ and $\rho$)

Assume the following:

1. ${\eta }_z$ is closed and convex for every $\mathbf{z}\in Z$.

2. ${\rho }_x$ is closed and convex for every $\mathbf{x}\in X$.

3. Assume that either

   $$\underset{\mathbf{x}\in X}{inf}\underset{\mathbf{z}\in Z}{sup}\varphi (\mathbf{x},\mathbf{z})<\mathrm{\infty }$$

   or

   $$-\mathrm{\infty }<\underset{\mathbf{z}\in Z}{sup}\underset{\mathbf{x}\in X}{inf}\varphi (\mathbf{x},\mathbf{z})$$

   holds true.

4. The recession cones and constancy spaces of $\eta$ and $\rho$ are equal to each other:

   $$R_{\eta }=L_{\eta }\text{ and }{R}_{\rho }=L_{\rho }.$$

Then the set of saddle points of $\varphi$ is nonempty.

9.4.6.3. Saddle Point Theorem

The analysis in this section culminates into the following result.

Theorem 9.44 (Saddle point theorem)

Assume that ${\eta }_z$ is closed and convex for every $\mathbf{z}\in Z$ and ${\rho }_x$ is closed and convex for every $\mathbf{x}\in X$. Then the set of saddle points of $\varphi$ is nonempty and compact under any of the following conditions.

1. $X$ and $Z$ are compact.

2. $Z$ is compact and there exists a vector $\bar{\mathbf{z}}\in Z$ and a scalar $c$ such that the sublevel set

   $$\{\mathbf{x}\in X|\varphi (\mathbf{x},\bar{\mathbf{z}})\le c\}$$

   is nonempty and compact.

3. $X$ is compact and there exists a vector $\bar{\mathbf{x}}\in X$ and a scalar $c$ such that the superlevel set

   $$\{\mathbf{z}\in Z|\varphi (\bar{\mathbf{x}},\mathbf{z})\ge c\}$$

   is nonempty and compact.

4. There exist vectors $\bar{\mathbf{x}}\in X$ and $\bar{\mathbf{z}}\in Z$ and a scalar $c$ such that the sets

   $$\{\mathbf{x}\in X|\varphi (\mathbf{x},\bar{\mathbf{z}})\le c\}\text{ and }\{\mathbf{z}\in Z|\varphi (\bar{\mathbf{x}},\mathbf{z})\ge c\}$$

   are nonempty and compact.

previous

9.3. Directions of Recession

next

9.5. Constrained Optimization I