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.

Consider a closed convex compact subset $\mathbb{S}$ of $\mathbb{R}^N$ while we denote any of its point by $x=[x_1,x_2,\ldots,x_N]^T$. Define the function \begin{align} f(x)=max(x_1,x_2,\ldots,x_N) \end{align} Now consider the optimization problem \begin{align} \min_{x~\in~\mathbb{S}}~f(x) \end{align} For instance, in the 2-Dimensional, it can be proved that that the global optimizers should be one of three points, 1) left most point 2) down most point 3) the south west point which lies on the line $x_1=x_2$. Also see this problem in MSE. Any general comments or help or hint is welcome. UPDATE--What I am looking for is a general comment on this problem. $\mathbb{S}$ can be any closed convex compact set. For this problem in 2-D, for any closed convex set $\mathbb{S}$, one can make comments on the global minimizers. The question is how is this generalized to the $N$ dimensional case.

share|improve this question
    
What is the question here? Generally something more specific than a request for "comments or help or hint" is needed to make a question that can be answered. For example, how is the convex subset $\mathbb{S}$ defined for the purpose of solving the optimization problem? –  hardmath Dec 9 '12 at 4:50
    
@hardmath I was looking for any general comment on the solution of this problem. $\mathbb{S}$ can be any closed convex compact set. For the 2-dimensional case, one can make the comments I have made. Since it is the $max$ function, I was wondering if one can make any general comment. –  dineshdileep Dec 9 '12 at 6:06
    
@hardmath please see the edit –  dineshdileep Dec 9 '12 at 6:11
add comment

1 Answer

up vote 1 down vote accepted

Perhaps the question is about visualizing the solution of a fairly abstract type of minimax problem.

We can give an approach that generalizes what the OP recites about 2D cases to higher dimensions, and in doing so demonstrate that the possibilities increase in combinatorial fashion.

First let's arrange that the compact convex subset $\mathbb{S}$ lies in the first orthant (positive cone) of $\mathbb{R}^n$ by adding a sufficiently large constant $M$ to all coordinates. The translation $\mathbb{S} + (M,\ldots,M)$ will then also be a compact convex set (with positive coordinates at all points), and the solution of the minimax problem there will give a solution to the original problem by subtracting $M$.

Now consider the family of boxes (hypercubes) $C_t$ with opposing vertices at the origin $(0,\ldots,0)$ and $(t,\ldots,t)$ parameterized by $t > 0$. For sufficiently small $t$ these boxes are disjoint from the (translated) set $\mathbb{S}$, and for sufficiently large $t$ the boxes will intersect (or even contain) the set $\mathbb{S}$. What we're looking for is the least $t$ for which the intersection is nonempty.

In 2D we start out with a small square $[0,t]\times[0,t]$ that misses $\mathbb{S}$, and we drag the corner $(t,t)$ up the diagonal line $x=y$ until the square touches $\mathbb{S}$. This first point of contact is where the minimax solution is attained. If it occurs at the corner of the square $(t,t)$, then that's a solution where coordinates are equal. However first contact might be reached at the upper edge of the square ($y$ exceeds $x$) or at the right hand edge ($x$ exceeds $y$). These three possibilities are to be identified with the three outlined in the Question.

In higher dimensions the possibilities for locating the first contact increase combinatorially. The solution may be reached at a corner $(t,\ldots,t)$ where all coordinates are equal, or at a "face" where one coordinate exceeds all the others. But intermediate combinations are possible as well. Indeed "edges" and other "leading" portions of the box's boundary can be identified by choosing a subset of the coordinates and requiring a solution where those chosen coordinates are equal and in turn exceed all the other (unchosen) coordinates.

It's not hard to construct a simple set $\mathbb{S}$ which realizes a solution at any of these locations. For example we can construct a point with the required mix of equal coordinates and lesser coordinates, and define $\mathbb{S}$ to be the singleton set containing that point. Trivially the minimax solution is then attained there.

share|improve this answer
    
I am not able to think a better explanation to it ( i was actually hoping for an algorithm, its impossible i guess) after this much time, thanks for the insight, the idea was really cool. –  dineshdileep Dec 11 '12 at 18:44
    
To attempt an algorithm we would need a way in which the convex compact set $\mathbb{S}$ can be defined. For example, giving points in $\mathbb{R}^n$ and taking their convex closure. –  hardmath Dec 11 '12 at 18:53
add comment

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.