[[Эволюционные алгоритмы многокритериальной оптимизации, основанные на индикаторах. Гиперобъем#Коэффициент апроксимации|Коэффициент апроксимации]] монотонно убывающих функций не зависит от масштабов отрезков <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>.
Далее будем рассматривать только монотонно убывающие, полунепрерывные Парето-фронты. Условие полунепрерывности необходимо для того, [[Эволюционные алгоритмы многокритериальной оптимизации, основанные на индикаторах. Гиперобъем#Индикатор Гиперобъемаstatement1|чтобы существовало множество решение, максимизирующее индикатор гиперобъема]].
Рассмотрим оптимальный коэффициент апроксимации для данного Парето-фронта из n (<tex> \alpha _{OPT}</tex>) и верхнюю границу коэффициента аппроксимации для множества из n точек, максимизирующего значение индикатора гиперобъема (<tex> \alpha _{HYP}</tex>) и докажем, что для количества точек <tex> n </tex> они одинаковы, а именно <math> 1 + \Theta ( \frac{1}{n}) </math>.
==Индикатор гиперобъема==
{{Утверждение
|id=statement1
|about=1
|statement=Пусть <tex>f \in \mathbb{F}, n \in \mathbb{N}</tex>.
Тогда существует, не обязятельно единственное, множество решения <tex>X \in \mathbb{X}</tex>, которое максимизирует значение [[Эволюционные алгоритмы многокритериальной оптимизации, основанные на индикаторах. Гиперобъем#Индикатор Гиперобъема|гиперобъема]] (<tex>HYP(X)</tex>) на <tex>\mathbb{X}</tex>
|proof= Доказательство представлено в статье [[Эволюционные алгоритмы многокритериальной оптимизации, основанные на индикаторах. Гиперобъем#Индикатор Гиперобъема|Эволюционные алгоритмы многокритериальной оптимизации, основанные на индикаторах. Гиперобъем]]
}}
==Нахождение лучшего коэффициента аппроксимации==
[[Эволюционные алгоритмы многокритериальной оптимизации, основанные на индикаторах. Гиперобъем#Индикатор ГиперобъемаКоэффициент аппроксимации#statement5statement3| Утверждение(3)]] ограничивает значение оптимального коэффицента апроксимации сверху: <tex>1 + \frac{\log (\min ( \frac{A}{a}, \frac{B}{b}))}{n}</tex> = <math> 1 + \Theta ( \frac{1}{n}) </math>.
==Нахождение коэффициента аппроксимации множества решения максимизируюшего гиперобъем==
{{Утверждение
|about=2
|statement=Пусть <tex>f \in \mathbb{F}, n \geq 3</tex> и <tex>X= \{x_1, x_2, \ldots, x_d \} \in X </tex>.
Тогда [[http://neerc.ifmo.ru/wiki/index.php?title=Сложность_задачи_вычисления_Least_Hypervolume_Contributor_и_задачи_его_аппроксимации| MINCON]] минимальный вклад данного множество решения:
<tex>MINCONMinCon(X) \leq \frac{(x_n - x_1)(f(x_1) - f(x_n))}{(n-2)^2}</tex>
|proof=
Исходя из определения минимальный вклад в гиперобъем множества равен минимуму из всевозможных площадей прямоугольников, образующихся между соседними точками множества решения и их значениями.
Пусть <tex>a_i, b_i</tex> - длины сторон соответствующего прямоугольника, тогда:
<tex> a_i \geq MINCON(X)/b_i</tex>, для любого <tex>2 \leq forall i \leq in [2, n - 1]</tex>
Это означает:
Так как среднее гармоническое не больше среднего арифметического:
<tex> MinCon(X) \leq \frac{n x_n- 2x_1}{\sum\limits_{i=2}^{n-1}1/b_i} \leq \frac{(x_n-x_1)\sum\limits_{i=2}^{n-1}1/b_i}{(n-2)^2} \leq \frac{(x_n-x_1)(f(x_1)-f(x_n))}{(n - 2)^2}</tex> Преобразуя, получаем искомое.
}}
|about=1
|id=theorem1
|statement=Пусть <tex>f \in \mathbb{F}, n > 4</tex>. Любое множество решение <tex>\{x_1, x_2, \ldots, x_d\} \in X_\mathbb{HYPX}^f </tex> достигает \alpha = <tex>1 + \frac{ \sqrt{A/a} + \sqrt{B/b} }{n - 4}</tex> мультипликативной аппроксимации всех внутренних точек.
|proof=
Доказательство производится от противного, принимая предположениеДопустим, что существует такой <tex> x</tex>, для которого бы который не выполнялось условие аппроксимации аппроксимируется <tex>\alpha = 1 + \frac{\sqrt{A/a} + \sqrt{B/b}}{n-4}</tex>.Пусть <tex>x_i < x < x_i+1</tex>, тогда <tex>x > \alpha x_i, f(x) > \alpha f(x_{i+1})</tex>. Известно, что <tex>MinCon(X) \geq (x-x_i)(f(x)-f(x_{i+1}))</tex>. После подстановки получим <tex>MinCon(X) > (\alpha - 1)^2 x_i f(x_{i+1})</tex> (1). Применив [[#statement5|утверждение(5)]], получим: <tex>\forall i \in [3, n-1]</tex> <tex>MinCon(X) \leq (x_i-x_1)(f(x_1)-f(x_i))/(i-2)^2 \leq x_iB/(i-2)^2</tex> (2) <tex>\forall i \in [1, n-3]</tex> <tex>MinCon(X) \leq (x_n-x_{i+1})(f(x_{i+1})-f(x_n))/(n-i-2)^2 \leq A f(x_{i+1})/(n-i-2)^2</tex> (3) Таким образом, <tex>(\alpha - 1)^2 x_i f(x_{i+1}) < \min \{\frac{x_iB}{(i-2)^2} ,\frac{A f(x_{i+1})}{(n-i-2)^2}\} \Leftrightarrow</tex> <tex>\alpha < 1 + \min \{\frac{\sqrt{x_iB}}{i-2} ,\frac{\sqrt{A f(x_{i+1})}}{n-i-2}\}</tex>. Т.к. <tex>\frac{\sqrt{x_iB}}{i-2}</tex> монотонно убывает, а <tex>\frac{\sqrt{A f(x_{i+1})}}{n-i-2}\}</tex> монотонно возрастает, то максимальное значение <tex>\min \{\frac{\sqrt{x_iB}}{i-2} ,\frac{\sqrt{A f(x_{i+1})}}{n-i-2}\}</tex> достигается при данном коэффициентеравенстве обоих членов: <tex>\frac{\sqrt{x_iB}}{i-2} = \frac{\sqrt{A f(x_{i+1})}}{n-i-2}\} \Leftrightarrow i = 2 + \frac{(n-4)\sqrt{B/b}}{\sqrt{A/a} + \sqrt{B/b}}</tex>. Получим верхнюю оценку для <tex>\alpha</tex>: <tex>\alpha < 1 + \frac{\sqrt{A/a} + \sqrt{B/b}}{n-4}</tex>. Вышесказанное верно для <tex>3 \leq i \leq n-3</tex>. Для <tex>i = 1, 2</tex> из (1) и (3) следует, что <tex>\alpha < 1 + \frac{\sqrt{A/a}}{n-i-2} \leq 1 + \frac{\sqrt{A/a}}{n-4}</tex>, что невозможно по условию теоремы. Для <tex>i = n-2, n-1</tex> по (1) и (2) <tex>\alpha < 1 + \frac{ \sqrt{B/b} } {i-2} \leq 1 + \frac {\sqrt {B/b} } {n-4}</tex>, что тоже невозможно по условию теоремы.
}}
|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=
Доказательство производится c использованием ранее доказанного утверждения о MINCON<tex>MinCon</tex>.
}}
что и требовалось доказать.
{{Утверждение
|id=statement5
|about=5
|statement=Пусть <tex>f \in \mathbb{F}, n \geq 3</tex> и <tex>X = \{x_1, \ldots, x_n\} \in \mathbb{X}</tex>, тогда
<tex>MinCon(X) \leq \frac{(x_n-x_1)(f(x_1)-f(x_n))}{(n-2)^2}</tex>.
|proof=
Пусть <tex>a_i=x_i-x_{i-1}</tex> <tex>\forall i \in [2,n]</tex> и <tex>b_i=f(x_i)-f(x_{i-1})</tex> <tex>\forall i \in [1,n-1]</tex>.
Подставив в [[#definition6|определение(6)]], получим:
<tex>MinCon(X)= \min \limits_{2 \leq i \leq n-1} a_i b_i \Leftrightarrow a_i \geq MinCon(X) / b_i \forall i \in [2, n-1]</tex>
<tex>\sum \limits_{i=2}^{n-1} MinCon(X) / b_i \leq \sum \limits_{i=2}^{n-1} a_i \leq \sum \limits_{i=2}^{n} a_i = \sum \limits_{i=2}^{n}x_i - \sum \limits_{i=1}^{n-1}x_i=x_n-x_1 </tex>
Тогда <tex>MinCon(X) \leq \frac{x_n-x_1}{\sum \limits_{i=2}^{n-1}1/b_i}</tex>.
Cреднее гармоническое меньше среднего арифметического, поэтому
<tex>MinCon(X) \leq \frac{x_n-x_1}{\sum \limits_{i=2}^{n-1}1/b_i} \leq \frac{(x_n-x_1)\sum \limits_{i=2}^{n-1}b_i}{(n-2)^2} \leq \frac{(x_n-x_1)(f(x_1)-f(x_n))}{(n-2)^2}</tex>.
}}
{{Теорема
|statement=Пусть <tex>f \in \mathbb{F}, n > 4</tex> и <tex>X = \{ x_1, \ldots, x_n \} \in \mathbb{X}</tex>. Тогда
<tex>\alpha = 1 + \frac{\sqrt{A/a} + \sqrt{B/b}}{n-4}</tex>.
|proof=
Допустим, что существует <tex>x</tex>, который не аппроксимируется <tex>\alpha = 1 + \frac{\sqrt{A/a} + \sqrt{B/b}}{n-4}</tex>.
Пусть <tex>x_i < x < x_i+1</tex>, тогда <tex>x > \alpha x_i, f(x) > \alpha f(x_{i+1})</tex>.
Известно, что <tex>MinCon(X) \geq (x-x_i)(f(x)-f(x_{i+1}))</tex>.
После подстановки получим <tex>MinCon(X) > (\alpha - 1)^2 x_i f(x_{i+1})</tex> (1).
Применив [[#statement5|утверждение(5)]], получим:
<tex>\forall i \in [3, n-1]</tex> <tex>MinCon(X) \leq (x_i-x_1)(f(x_1)-f(x_i))/(i-2)^2 \leq x_iB/(i-2)^2</tex> (2)
<tex>\forall i \in [1, n-3]</tex> <tex>MinCon(X) \leq (x_n-x_{i+1})(f(x_{i+1})-f(x_n))/(n-i-2)^2 \leq A f(x_{i+1})/(n-i-2)^2</tex> (3)
Таким образом, <tex>(\alpha - 1)^2 x_i f(x_{i+1}) < \min \{\frac{x_iB}{(i-2)^2} ,\frac{A f(x_{i+1})}{(n-i-2)^2}\} \Leftrightarrow</tex> <tex>\alpha < 1 + \min \{\frac{\sqrt{x_iB}}{i-2} ,\frac{\sqrt{A f(x_{i+1})}}{n-i-2}\}</tex>.
Т.к. <tex>\frac{\sqrt{x_iB}}{i-2}</tex> монотонно убывает, а <tex>\frac{\sqrt{A f(x_{i+1})}}{n-i-2}\}</tex> монотонно возрастает, то максимальное значение <tex>\min \{\frac{\sqrt{x_iB}}{i-2} ,\frac{\sqrt{A f(x_{i+1})}}{n-i-2}\}</tex> достигается при равенстве обоих членов:
<tex>\frac{\sqrt{x_iB}}{i-2} = \frac{\sqrt{A f(x_{i+1})}}{n-i-2}\} \Leftrightarrow i = 2 + \frac{(n-4)\sqrt{B/b}}{\sqrt{A/a} + \sqrt{B/b}}</tex>.
Получим верхнюю оценку для <tex>\alpha</tex>: <tex>\alpha < 1 + \frac{\sqrt{A/a} + \sqrt{B/b}}{n-4}</tex>.
Вышесказанное верно для <tex>3 \leq i \leq n-3</tex>.
Для <tex>i = 1, 2</tex> из (1) и (3) следует, что <tex>\alpha < 1 + \frac{\sqrt{A/a}}{n-i-2} \leq 1 + \frac{\sqrt{A/a}}{n-4}</tex>, что невозможно по условию теоремы.
Для <tex>i = n-2, n-1</tex> по (1) и (2) <tex>\alpha < 1 + \frac{ \sqrt{B/b} } {i-2} \leq 1 + \frac {\sqrt {B/b} } {n-4}</tex>, что тоже невозможно по условию теоремы.
}}
=Примечание=
