# Solution for a optimization of $\max$ function

Let $\mathbb{S}^m$ be an arbitrary closed, compact, convex set in $\mathbb{R}^m$. Let $\mathbf{x}=(x_1,\dots,x_m)$ denote a point in $\mathbb{S}^m$. Then, I define the function \begin{align} f(\mathbf{x})=\max_{i}\{x_i\},~~\mathbf{x}\in \mathbf{S}^m \end{align} on the set $\mathbb{S}^m$. Consider the optimization problem \begin{align} \min_{\mathbf{x}\in \mathbb{S}^m}~f(\mathbf{x}) \end{align}

My question is

1. Is the optimization problem above a convex optimization problem?
2. In general, what can one comment about its solution.

Since the function $f(x) = \max \{x_1,...,x_n\}$ is convex, the problem is a convex problem.

Without knowing more about $S^m$, it is hard to comment on the solution. It may not have a solution, for example, if $S^m = \mathbb{R}^m$, or if $S^m$ is open.

Note: Let $I(x) = \{ i | x_i = \max_j x_j \}$ (the 'active' indices), and suppose $\hat{x}$ is a solution, then for some neighborhood of $\hat{x}$, we have $I(x) \subset I(\hat{x})$, and for $x$ in this neighborhood we can write $\max_i x_i = \max_{i \in I(\hat{x})} x_i$, and we have $\min_{x \in S^m} \max_i x_i = \min_{x \in S^m} \max_{i \in I_{\hat{x}}} x_i$.

If $|I(\hat{x})| =1$, then the solution lies on the left/bottom/whatever-the-right-term-is most part of $S^m$. If $|I(\hat{x})| =m$, then the solution lies on the line $x_1 = ... = x_m$.

The issues with this approach is that you hit some combinatorial issue that doesn't really surface in $\mathbb{R}^2$.

• $\mathbb{S}^m$ is a closed, compact convex body. For instance, consider $\mathbb{S}^2$ (i.e. in 2-D). It is not that difficult to prove that the $\mathbf{x}$ in $\mathbb{S}^2$ which solves that problem is either 1) Left most point in $\mathbb{S}^2$ 2) Bottom most point in $\mathbb{S}^2$ 3) left-bottom most point in $\mathbb{S}^2$ on the line $x=y$. I was kind of looking for a solution which generalizes that. – dineshdileep Sep 26 '13 at 10:11
• @dineshdileep: Your 1-3) is not correct. Take $S=\operatorname{co} \{ (1,-1),(2,-1),(0,1) \}$. The unique minimizer is at $(1,-1)$ which does not satisfy 1-3). – copper.hat Sep 26 '13 at 16:21
• I am sorry, but what is $S=\operatorname{co} \{ (1,-1),(2,-1),(0,1) \}$? – dineshdileep Sep 27 '13 at 3:28
• Oh, sorry!!, I didn't add the condition that $\mathbb{S}^m$ has always a non-zero intersection with the all-co-ordinate negative quadrant. – dineshdileep Sep 27 '13 at 3:30
• The symbol $\operatorname{co}$ means the convex hull of the three points. My counter example was slight off. Try the convex hull of the points $(-1,-5), (-3,-4), (-4,-2)$. Note that the value of $f$ for each of the points is $-1, -3, -2$ respectively, so the unique minimizer is $(-3,-4)$, which is none of 1-3) above, and this set is entirely contained in the 'all-negative' quadrant. – copper.hat Sep 27 '13 at 3:48