К какому классу относится задача оптимизации?

[pierrevanstulov]

Есть множество ограничений $Q(x,y)$ и такая вот задача оптимизации $\max_{y \in Q}(\max_{x \in Q}f_1(x)-\max_{x \in Q}f_2(x))$.

Иначе говоря, нужно найти такое $y$ при котором разница между оптимумами двух критериев, зависящих от $x$ максимальна, при этом $y$ и $x$ связывают ограничения $Q(x,y)$.

Наверняка ведь эта задача относится к какому-нибудь хорошо изученному классу, но я никак не пойму к какому. Что это за класс задач?

[mserg]

Что-то все знатоки всех учебников молчат… Ну, тогда я.

Если $f_2(x)=0$, то это обычная задача оптимизации

Если $f_1(x)=0$, то это задача на минимакс, точнее, максимин (минус можно затащить под максимум, и оно станет минимумом, а функция под ним - с минусом (пардон мой французский)). Другими словами, в этой задаче как бы имеет место быть противодействие по x, т.е. весьма вероятно, что ответ следует искать где-нибудь в теории игр.

[pierrevanstulov]

Спасибо за внимание, mserg. Эта задача фактически и возникла из игровой модели. Я бы решил ее каким-нибудь методом частиц в стае, если бы не одно "но": мне нужна оценка оптимума сверху (ну а в идеале - точное решение). Думал, может есть какие-нибудь теоремы для задач такого типа.

[mserg]

Честно говоря, я знаю только один метод решения подобных задач с небольшим числом переменных – это интервальный анализ. В этой книжке
http://www.ozon.ru/context/detail/id/2423729/
есть раздел «5.6 Минимаксная оптимизация». Там же есть ссылки на библиотеки (кажется C, или C++).
Гарантированная точность решения - до округления процессора (да, да, эта штука управляет округлением процессора туда или сюда)

Припоминаю, у нас в Новосибирске была (есть) группа интервального анализа - может им подкинуть?

[pierrevanstulov]

Спасибо за ссылку на книгу! Мне очень в тему.

Вообще эта задача должна быть довольно хорошо изучена, т.к. (в трансформированном виде) она имеет прозрачную интерпретацию - это задача о поиске упущенной выгоды. А именно:

У меня есть задача оптимизации $F(x, y) \to \max_{x \in X}$, целевая функция которой зависят от параметра $y \in Y$. Какое конкретно значение из множества $Y$ примет параметр - неизвестно. Я решаю задачу при некотором $y' \in Y$ и получаю некоторое оптимальное решение $x^*$. Теперь мне интересно посмотреть, каков будет максимальный размер упущенной выгоды, для чего, очевидно, необходимо решить задачу $\max_{y \in Y}(|\max_{x \in X}(F(x,y))-F(x^*,y)|)$. Желательно получить точное решение или близкую к точному решению оценку сверху (оценка снизу, очевидно, не годится).

Если сможете подкинуть кому-нибудь, кто сможет еще что-нибудь подсказать - буду очень признателен.