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$.

  • $\begingroup$ $\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. $\endgroup$ – dineshdileep Sep 26 '13 at 10:11
  • $\begingroup$ @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). $\endgroup$ – copper.hat Sep 26 '13 at 16:21
  • $\begingroup$ I am sorry, but what is $S=\operatorname{co} \{ (1,-1),(2,-1),(0,1) \}$? $\endgroup$ – dineshdileep Sep 27 '13 at 3:28
  • $\begingroup$ 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. $\endgroup$ – dineshdileep Sep 27 '13 at 3:30
  • $\begingroup$ 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. $\endgroup$ – copper.hat Sep 27 '13 at 3:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.