peculiar min-max question

Discussion in 'Math Research' started by Peter Scheffler, Aug 17, 2011.

  1. 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 inner-product.

    The brute-force 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 Scheffler, Aug 17, 2011
    1. Advertisements

  2. Consider the following problem:
    Given x_1,..., x_n as stated, compute

    W_n = max_{\theta \in P} <\theta, \theta>


    P = \{ \theta \in R^d | |<\theta, x_i>| \leq 1 , 1 \leq i \leq n \} .

    If I am not mistaken, if V_n > 0 then W_n is finite and V_n = 1/W_n;
    whereas if V_n = 0 then W_n is infinite.

    The problem of finding W_n is a case of quadratic programming. There is
    a treatment of it in G. B. Dantzig, _Linear Programming and Extensions_,
    2d edn., 1968. This problem (linear constraints, quadratic objective)
    can be solved by a variant of the simplex algorithm.
    Christopher Henrich, Aug 18, 2011
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.