How to minimize the maximum?

For example, how to decide what 'a' is, in order to minimize the following:

max | 1-a \sigma_i^2|

where

\sigma_i

is sequence of numbers, or entries of a n-by-1 matrix. Suppose

\sigma_n

and

\sigma_1

are the smallest and the largest elements in that matrix.

I don't even know how to start. Can anyone help me?

Reply 1

Smaug123

Original post by Jundong

For example, how to decide what 'a' is, in order to minimize the following:

max | 1-a \sigma_i^2|

where

\sigma_i

is sequence of numbers, or entries of a n-by-1 matrix. Suppose

\sigma_n

and

\sigma_1

are the smallest and the largest elements in that matrix.

I don't even know how to start. Can anyone help me?

Under what circumstances will

|1-a \sigma_i^2|

be large? (Never mind "largest" for the moment.)

Reply 2

Jundong

Original post by Smaug123

Under what circumstances will

|1-a \sigma_i^2|

be large? (Never mind "largest" for the moment.)

Sorry to reply you so late.
When I consider this minimax question (never done that before), I am more worried about the minimum.
I think the limit of the whole thing must be less that 1. In order to do that, I think I need to choose

a

to be something like

\frac{1}{\sigma_1 ^2}

, where

\sigma_1^2

is the largest element of

\sigma_i

? Then maximum of that thing would be

|1-a \sigma_n^2|

where

\sigma_n

is the smallest element. So I need to choose something between

\frac{1}{\sigma_1^2}

and

\frac{1}{\sigma_n^2}

.

That is what I have got so far.

Reply 3

Smaug123

Original post by Jundong

Sorry to reply you so late.
When I consider this minimax question (never done that before), I am more worried about the minimum.

Quite right: I was just trying to get you to play with the problem a bit. Don't worry about that, then.

I think the limit of the whole thing must be less that 1. In order to do that, I think I need to choose

a

to be something like

\frac{1}{\sigma_1 ^2}

, where

\sigma_1^2

is the largest element of

\sigma_i

? Then maximum of that thing would be

|1-a \sigma_n^2|

where

\sigma_n

is the smallest element. So I need to choose something between

\frac{1}{\sigma_1^2}

and

\frac{1}{\sigma_n^2}

.

That is what I have got so far.

If you chose

a=\frac{1}{\sigma_1^2}

, let's suppose

\sigma_n = 1

and

\sigma_1 = \frac{1}{10}

. What, then, is

\text{max}(|1-a \sigma_i^2|)

?
(I think I've understood your working so far, but I might be wrong. Let me know if my question makes no sense in the light of your current working.)

(edited 9 years ago)

Reply 4

Jundong

Original post by Smaug123

Quite right: I was just trying to get you to play with the problem a bit. Don't worry about that, then.

If you chose

a=\frac{1}{\sigma_1^2}

, let's suppose

\sigma_n = 1

and

\sigma_1 = \frac{1}{10}

. What, then, is

\text{max}(|1-a \sigma_i^2|)

?
(I think I've understood your working so far, but I might be wrong. Let me know if my question makes no sense in the light of your current working.)

Yes, your question makes sense to me. So I need to choose something between

\frac{1}{\sigma_1^2}

and

\frac{1}{\sigma_n^2}

, right? For example,

\frac{1}{\sigma_1^2+\sigma_n^2}

But so far, we only discussed the logical behind the question. How can I come up with an algebraic answer?

Reply 5

Jundong

And, even I know the correct answer, how can I prove it is the minimax?

Reply 6

DFranklin

Original post by Jundong

Yes, your question makes sense to me. So I need to choose something between

\frac{1}{\sigma_1^2}

and

\frac{1}{\sigma_n^2}

, right? For example,

\frac{1}{\sigma_1^2+\sigma_n^2}

But so far, we only discussed the logical behind the question. How can I come up with an algebraic answer?

I don't think you're going to come up with an algebraic answer without talking about the logic of the situation.

(And the logic of the situation should explain to you how to justify your answer).

A heuristic I will offer you: If you have two functions f(x), g(x) and f is decreasing and g is increasing, then if x minimizes max{f(x), g(x)} then f(x) = g(x).