Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let us say I have a closed compact convex set $\mathbb{S}$ on the 2-D plane (eg: a circle). Let any point $p$ in the 2-D plane be represented by $p=(x,y)$. I define the max function over 2-D plane \begin{align} f(p)&=\max{(x,y)} \\ &= \begin{cases}x & \text{if $x\geq y$} \\ y & \text{if $x<y$}\end{cases} \end{align} Eg: At $(2,3)$,it will be evaluated as $f(2,3)=3$. I consider the optimization problem \begin{align} c^{\star}=\min_{p\in \mathbb{S}}\quad f(p) \end{align} MY ATTEMPT-2

Let us say, the corner points of this convex body in the all-negative quadrant are known. i.e. Let $P_w=(x_w,y_w)$ be the west-most point, $P_{sw}=(x_{sw},y_{sw})$ , the most south-west point such that it lies on $x=y$, and let $P_{s}=(x_s,y_s)$ be the south-most point. Then

  • if $x_w>y_w$, then $c^{\star}=x_w$
  • if $y_s>x_s$, then $c^{\star}=y_s$
  • if $y_w >x_w$ and $y_s<x_s$, then $c^{\star}=x_{sw}$

How do I extend this to 3-Dimensional given the corner points of this body

share|cite|improve this question
up vote 1 down vote accepted

Edit: Let us consider the $n$-dimensional case. There are only two possible types of global minimizers ${\mathbf u}$:

  1. ${\mathbf u}=(u_1,\ldots,u_n)$ with $u_i=u_k=\max_j u_j$ for some $i\not=k$, i.e. ${\mathbf u}$ has at least two maximum coordinates. Note that it is not necessarily true that $u_1=u_2=\ldots=u_n$ when $n\ge3$. For example, consider the cylinder $\mathbb{S}=\{(x,y): (x-4)^2+(y-4)^2\le4\}\times[0,1]\subset\mathbb{R}^3$, where the set of global minimizers of $f$ over $S$ is $\{(2,2,z): 0\le z\le 1\}$.
  2. ${\mathbf u}=(u_1,\ldots,u_n)$ with $u_i>\max_{j\not=i}u_j$, i.e. ${\mathbf u}$ has a unique maximum coordinate. In this case, we claim that $u_i=\min_{{\mathbf x}\in\mathbb{S}}x_i$. Suppose the contrary. Then there exists some ${\mathbf x}'\in\mathbb{S}$ such that $x_i'<u_i$. But then when $\theta>0$ is small enough and $\mathbf{x}=\theta\mathbf{x}'+(1-\theta)\mathbf{u}$, we would have $\max_{j\not=i}x_j<x_i<u_i$, meaning that $f(\mathbf{x})=x_i<u_i$, which is a contradiction. Hence $u_i=\min_{{\mathbf x}\in\mathbb{S}}x_i$.
share|cite|improve this answer
sorry for such a late reply, I was just looking back at this answer, how does the left-most vertical "edge" come into picture here? Is it in the case $a>b$? – dineshdileep Jan 24 '13 at 11:48
@dineshdileep Yes. If $a>b$, $(a,b)$ will be lying on the leftmost vertical edge. Actually the proof can be greatly simplified. See my new edit. – user1551 Jan 24 '13 at 22:58
interesting, any thoughts on the 3-dimensional case? – dineshdileep Jan 25 '13 at 4:48
@dineshdileep Done. See my new edit. – user1551 Jan 25 '13 at 20:01
I don't know how to thank you. This forms a part of my work, and this proof was the missing part. I would like to know more about you. If you are not offended by it, please drop a mail at myusername_at_gmail_ – dineshdileep Jan 26 '13 at 9:25

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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