1
$\begingroup$

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}\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, then $c^{\star}=x_{sw}$

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

1 Answers 1

1

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'. 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, meaning that $f(\mathbf{x})=x_i, which is a contradiction. Hence $u_i=\min_{{\mathbf x}\in\mathbb{S}}x_i$.
  • 0
    @dineshdileep Your first bullet point can be generalized as "$x_w\ge y_w,z_w\,\Rightarrow\,(x_w,y_w,z_w)$ is a global minimum". Similarly for the extreme points with the least $y$- or $z$-coordinates. Your third bullet point, however, can't be generalized to the 3D case, because $\mathbb{S}$ may not intersect the line $x=y=z$ in the first place. For example, let $\mathbb{S}$ be the triangle with vertices $(0,2,1),(2,0,1),(1,1,0)$. The three vertices do satisfy the condition analogous to your third bullet point, but $\mathbb{S}\cap\{x=y=z\}$ is empty.2013-01-30