Изменения
Нет описания правки
Рассмотрим функции вида: <tex>f:[a,A] \rightarrow [b,B]</tex>, где <tex>f</tex> убывает и <tex>f(a)=B, f(A)=b</tex>. Коэффициент апроксимации монотонно убывающих функций не зависит от масштабов отрезков <tex> [a,A]</tex> и <tex>[b,B] </tex>. Так как для фиксированных констант <tex> \mu , \nu </tex> функция <tex> f^*:[ \mu a , \mu A ] \rightarrow [ \nu b , \nu B ]</tex> и <tex> f^*= \nu f(x/ \mu ) </tex> имеет тот же коэффициент аппроксимации. Однако, коэффициент аппроксимации зависит от значений <tex>A/a</tex> и <tex>B/b</tex>.
Множество всех таких функций обозначим через <tex>\mathbb{F}</tex>. Далее будем рассматривать только монотонно убывающие, полунепрерывные Парето-фронты. Условие полунепрерывности необходимо для того, [http://neerc.ifmo.ru/wiki/index.php?title=Эволюционные_алгоритмы_многокритериальной_оптимизации[Эволюционные алгоритмы многокритериальной оптимизации,_основанные_на_индикаторахоснованные на индикаторах._ГиперобъемГиперобъем#Индикатор Гиперобъема| чтобы существовало множество решение, максимизирующее индикатор гиперобъема]].
Рассмотрим оптимальный коэффициент апроксимации для данного Парето-фронта из n (<tex> \alpha _{OPT}</tex>) и верхнюю границу коэффициента аппроксимации для множества из n точек, максимизирующего значение индикатора гиперобъема (<tex> \alpha _{HYP}</tex>) и докажем, что для количества точек <tex> n </tex> они одинаковы, а именно <math> 1 + \Theta ( \frac{1}{n}) </math>.
Тогда существует, не обязятельно единственное, множество решения <tex>X \in \mathbb{X}</tex>, которое максимизирует значение <tex>HYP(X)</tex> на <tex>\mathbb{X}</tex>
|proof=
См. [[http://neerc.ifmo.ru/wiki/index.php?title=Эволюционные_алгоритмы_многокритериальной_оптимизацииЭволюционные алгоритмы многокритериальной оптимизации,_основанные_на_индикаторахоснованные на индикаторах._ГиперобъемГиперобъем#Индикатор Гиперобъема|статью Гиперобъем]]
}}
==Нахождение лучшего коэффициента аппроксимации==
[[http://neerc.ifmo.ru/wiki/index.php?title=Эволюционные_алгоритмы_многокритериальной_оптимизацииЭволюционные алгоритмы многокритериальной оптимизации,_основанные_на_индикаторахоснованные на индикаторах._ГиперобъемГиперобъем#Индикатор Гиперобъема| Доказательство]] ограничивает значение оптимального коэффицента апроксимации сверху: <tex>1 + \frac{\log (\min ( \frac{A}{a}, \frac{B}{b}))}{n}</tex> = <math> 1 + \Theta ( \frac{1}{n}) </math>.
==Нахождение коэффициента аппроксимации множества решения максимизируюшего гиперобъем==
{{Теорема
|about=1
|id=theorem1
|statement=Пусть <tex>f \in \mathbb{F}, n > 4</tex>. Любое множество решение <tex>\{x_1, x_2, \ldots, x_d\} \in X_{HYP}^f </tex> достигает <tex>1 + \frac{ \sqrt{A/a} + \sqrt{B/b} }{n - 4}</tex> мультипликативной аппроксимации всех внутренних точек.
|proof=
{{Теорема
|about=2
|id=theorem2
|statement=Пусть <tex>f \in \mathbb{F}, n > 3</tex>. И <tex> R = (R_x, R_y) \leq (0, 0) </tex> является точкой отсчета. Каждое множество решение <tex>\{x_1, x_2, \ldots, x_d\} \in X_{HYP}^f </tex> достигает <tex>1 + \frac{A}{(a - R_x)(n - 2)^2}</tex> мультипликативной аппроксимации всех точек с <tex>x < x_1</tex>, и достигает <tex>1 + \frac{B}{(b - R_y)(n - 2)^2}</tex> мультипликативной аппроксимации всех точек с <tex>x > x_n</tex>.
|proof=
Совместно теоремы [[#theorem1|теорема(1 )]] и [[#theorem2|теорема(2 )]] приводят к следующим следствиям:
'''Следствие 1:''' <tex>\alpha_{opt} = 1 + \Theta(1/n)</tex>
