Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question

1 Answer 1

up vote 1 down vote accepted
+50

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

 
discard

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.