# a convex function on a 2 dimensional closed convex set

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

-

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