Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.



peculiar minmax question
Posted:
Aug 17, 2011 7:00 AM


Hallo:
In research work on a certain statistical problem the following min/max problem and the question of a fast algorithm came up:
Given n vectors x_1,...,x_n in R^d and denote by \\theta\ the Euclidian norm of \theta\in R^d. I would like to efficiently compute (or at least approximate)
V_n=min_{\\theta\=1} \max_{1\leq i\leq n}<x_i,\theta>
where <x_i,\theta> denotes the ususal innerproduct.
The bruteforce approach works, sort of.... Here is what I tried: Sample m independend and uniformly distributed \theta_j on the sphere, compute the m\times n matrix of <x_i,\theta_j> and then find the min/max of that matrix. This is easily done in MATLAB. However, n and the dimension d (to have m small enough) have to be reasonable small...
Therefore I am looking for a different approach. For me it look's like a problem in convex geometry or optimization....
Since I am not an expert in these fields of mathematics (me working mostly in probability theory) I would appreciate any suggestions or remarks.
Many thanks!
Peter



