0

I have this optimization problem:

$$\max_{a} \min_{\alpha} \ \sum_{i,j} w_{ij} (s_i - s_j)^2 I $$ $$I = 1 \text{ if } w_{ij} \ge \alpha \text{, and } (s_i - s_j)^2 \le a \ ; 0 \text{ otherwise} $$

Notes: $w_{ij} \text{ is normalized between }[0,1].$ $\text{It would be ok if the restriction }(s_i - s_j)^2 \le a \text{ was replaced by } |s_i - s_j| \le a$

I am not entirely sure where to start to solve this problem. But I would start by asking the questions: How to relax this optimization problem? And whether it fits well-known optimization problems.

Kenta S
  • 16,151
  • 15
  • 26
  • 53
rando
  • 313
  • @user762914 Each $w_{ij}$ has $s_i \text{and} s_j$ associated with. Not sure I understood your last question, but are you saying this can be turned into a simple min. problem?$ – rando Jul 07 '20 at 18:14
  • the solution is trivial: since each term is nonnegative, the optimal $\alpha$ is any number as least as large as the largest $w_{ij}$, so all terms are 0. – LinAlg Jul 08 '20 at 00:38
  • @LinAlg but that wouldn't max $a$ – rando Jul 08 '20 at 13:19
  • You seem to have a misunderstanding of the meaning of "max min". It means $\max_a g(a)$ with $g(a) = \min_\alpha \sum_{i,j} w_{wij} (s_i - s_j)^2 I$. In your example, $g(a) = 0$ for all $a$, so the outer problem is $\max_a 0$. – LinAlg Jul 08 '20 at 16:31

0 Answers0