Solution in general for a seemingly simple problem

Question

Let $\mathbb{S}$ be a closed, bounded, convex set in $\mathbb{R}^N$. Let $\mathbb{x}=[x_1,\dots,x_N]$ be any arbitrary vector in $\mathbb{S}$. Then what can we comment on the problem \begin{align} \min_{t\in \mathbb{R},\mathbf{x}\in \mathbb{S}}&~~t\\\ \mbox{s.t.}~~&x_i\leq t,~~i=1,\dots,N \end{align}

Answer 1

I am not sure what you are looking for exactly. Here is another way of looking at the problem (basically the dual).

$\Sigma = \{ x \in \mathbb{R}^N | x_i \ge 0, \sum_i x_i = 1 \}$, and $\sigma_S$ is the support function of $S$.

The interchange of the $\max$, $\min$ is justified by a version of von Neumann's minimax theorem.

\begin{eqnarray} \min_{t, x\in S} \{ t | x_i \le t\} &=& \min_{x \in S} \max_i x_i \\ &=& \min_{x \in S} \max_{\mu \in \Sigma} \langle \mu, x \rangle \\ &=& \max_{\mu \in \Sigma} \min_{x \in S} \langle \mu, x \rangle \\ &=& \max_{\mu \in \Sigma} ( -\max_{x \in S} \langle -\mu, x \rangle ) \\ &=& -\min_{\mu \in \Sigma} \max_{x \in S} \langle -\mu, x \rangle \\ &=& -\min_{\mu \in \Sigma} \sigma_S(-\mu) \\ \end{eqnarray}

Answer 2

The problem reminded me of some type of epigraph form. For example, for the following problem (P1)

$\qquad\,\,\,\,\,\min_x f_0(x)\\ \text{subject to } f_i(x)\le0,\,i=1,\ldots,n\\ \qquad \qquad \,\,\,h_i(x)=0,\,i=1,\ldots,m$

The epigraph form is

$\qquad\,\,\,\,\,\min_{x,t} t\\ \text{subject to } f_0(x)\le t\\ \qquad \qquad \,\,\,f_i(x)\le0,\,i=1,\ldots,n\\ \qquad \qquad \,\,\,h_i(x)=0,\,i=1,\ldots,m$

Which is equivalent to (P1); $(x,t)$ is optimal for the epigraph form if and only if $x$ is optimal for (P1) and $t=f_0(x)$. A geometrical interpretation can be seen below (from Boyd)

However, in your problem it seems as though we wish to find the smallest scalar $t$ which defines some orthant (not epigraph), such that all $x_i$ live in this orthant and the set $\mathbb{S}$. In hindsight, the epigraph form may not be of much use here, but hopefully provides some intuition.