Max function on a closed compact convex set.

Question

Consider a closed convex compact subset $\mathbb{S}$ of $\mathbb{R}^N$ while we denote any of its point by $x=[x_1,x_2,\ldots,x_N]^T$. Define the function \begin{align} f(x)=max(x_1,x_2,\ldots,x_N) \end{align} Now consider the optimization problem \begin{align} \min_{x~\in~\mathbb{S}}~f(x) \end{align} For instance, in the 2-Dimensional, it can be proved that that the global optimizers should be one of three points, 1) left most point 2) down most point 3) the south west point which lies on the line $x_1=x_2$. Also see this problem in MSE. Any general comments or help or hint is welcome. UPDATE--What I am looking for is a general comment on this problem. $\mathbb{S}$ can be any closed convex compact set. For this problem in 2-D, for any closed convex set $\mathbb{S}$, one can make comments on the global minimizers. The question is how is this generalized to the $N$ dimensional case.

Answer 1

Perhaps the question is about visualizing the solution of a fairly abstract type of minimax problem.

We can give an approach that generalizes what the OP recites about 2D cases to higher dimensions, and in doing so demonstrate that the possibilities increase in combinatorial fashion.

First let's arrange that the compact convex subset $\mathbb{S}$ lies in the first orthant (positive cone) of $\mathbb{R}^n$ by adding a sufficiently large constant $M$ to all coordinates. The translation $\mathbb{S} + (M,\ldots,M)$ will then also be a compact convex set (with positive coordinates at all points), and the solution of the minimax problem there will give a solution to the original problem by subtracting $M$.

Now consider the family of boxes (hypercubes) $C_t$ with opposing vertices at the origin $(0,\ldots,0)$ and $(t,\ldots,t)$ parameterized by $t > 0$. For sufficiently small $t$ these boxes are disjoint from the (translated) set $\mathbb{S}$, and for sufficiently large $t$ the boxes will intersect (or even contain) the set $\mathbb{S}$. What we're looking for is the least $t$ for which the intersection is nonempty.

In 2D we start out with a small square $[0,t]\times[0,t]$ that misses $\mathbb{S}$, and we drag the corner $(t,t)$ up the diagonal line $x=y$ until the square touches $\mathbb{S}$. This first point of contact is where the minimax solution is attained. If it occurs at the corner of the square $(t,t)$, then that's a solution where coordinates are equal. However first contact might be reached at the upper edge of the square ($y$ exceeds $x$) or at the right hand edge ($x$ exceeds $y$). These three possibilities are to be identified with the three outlined in the Question.

In higher dimensions the possibilities for locating the first contact increase combinatorially. The solution may be reached at a corner $(t,\ldots,t)$ where all coordinates are equal, or at a "face" where one coordinate exceeds all the others. But intermediate combinations are possible as well. Indeed "edges" and other "leading" portions of the box's boundary can be identified by choosing a subset of the coordinates and requiring a solution where those chosen coordinates are equal and in turn exceed all the other (unchosen) coordinates.

It's not hard to construct a simple set $\mathbb{S}$ which realizes a solution at any of these locations. For example we can construct a point with the required mix of equal coordinates and lesser coordinates, and define $\mathbb{S}$ to be the singleton set containing that point. Trivially the minimax solution is then attained there.