Связь между максимизацией гиперобъема и аппроксимацией Парето-фронта — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Основные определения)
Строка 3: Строка 3:
 
|definition=Множество <tex>X^* \subseteq \mathbb{X}</tex> называется Парето-оптимальным, если:
 
|definition=Множество <tex>X^* \subseteq \mathbb{X}</tex> называется Парето-оптимальным, если:
 
<tex>\mathrm{\forall x^* \subset X^* \not \exists x \subset \mathbb{X} : x \succ x^*}</tex>,
 
<tex>\mathrm{\forall x^* \subset X^* \not \exists x \subset \mathbb{X} : x \succ x^*}</tex>,
где <tex> x \succ x^* </tex>(<tex>x</tex> доминирует <tex>x^*</tex>)<tex> \leftrightarrow \left( \forall i \in 1 \ldots d: f_i(x) \geq f_i(x^*) \right) \bigwedge \left( \exists i \in 1 \ldots d: f_i(x) > f_i(x^*)\right)</tex>  
+
где <tex> x \succ x^* </tex> (<tex>x</tex> доминирует <tex>x^*</tex>) <tex> \leftrightarrow \left( \forall i \in 1 \ldots d: f_i(x) \geq f_i(x^*) \right) \bigwedge \left( \exists i \in 1 \ldots d: f_i(x) > f_i(x^*)\right)</tex>  
  
 
<math>P(X^*)</math> - множество оптимальных по Парето решений, его также называют Парето-фронтом. Парето-фронт не может быть вычислен за полиномиальное время.
 
<math>P(X^*)</math> - множество оптимальных по Парето решений, его также называют Парето-фронтом. Парето-фронт не может быть вычислен за полиномиальное время.
Строка 10: Строка 10:
 
|id=definition6
 
|id=definition6
 
|about=6
 
|about=6
|definition=Пусть <tex>f \in \mathbb{F}, n \geq 3</tex> и <tex>X = \{x_1, \ldots, x_n\} \in \mathbb{X}</tex>. Наименьшим вкладом этого множества называется <tex>MinCon(X)= \min \limits_{2 \leq i \leq n-1} (x_i-x_{i-1})(f(x_i)- f(x_{i-1}))</tex>.
+
|definition=Пусть <tex>f \in \mathbb{F}, n \geq 3</tex> и <tex>X = \{x_1, \ldots, x_n\} \in \mathbb{X}</tex>. Наименьшим вкладом этого множества называется <tex>MinCon(X) = \min \limits_{2 \leq i \leq n - 1} (x_i-x_{i - 1})(f(x_i) - f(x_{i - 1}))</tex>.
 
}}
 
}}
  
 
=Связь между максимизацией гиперобъема и аппроксимацией Парето-фронта=
 
=Связь между максимизацией гиперобъема и аппроксимацией Парето-фронта=
Множество функций вида: <tex>f:[a,A] \rightarrow [b,B]</tex>, где <tex>f</tex> убывает и <tex>f(a)=B, f(A)=b</tex> обозначим через <tex>\mathbb{F}</tex>.
+
Множество функций вида: <tex>f:[a, A] \rightarrow [b, B]</tex>, где <tex>f</tex> убывает и <tex>f(a) = B, f(A) = b</tex> обозначим через <tex>\mathbb{F}</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> [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|чтобы существовало множество решение, максимизирующее индикатор гиперобъема]].
 
Далее будем рассматривать только монотонно убывающие, полунепрерывные Парето-фронты. Условие полунепрерывности необходимо для того, [[#statement1|чтобы существовало множество решение, максимизирующее индикатор гиперобъема]].
Строка 32: Строка 32:
  
 
==Нахождение лучшего коэффициента аппроксимации==
 
==Нахождение лучшего коэффициента аппроксимации==
[[Эволюционные алгоритмы многокритериальной оптимизации, основанные на индикаторах. Гиперобъем#Коэффициент аппроксимации| Утверждение(3)]] ограничивает значение оптимального коэффицента апроксимации сверху: <tex>1 + \frac{\log (\min ( \frac{A}{a}, \frac{B}{b}))}{n}</tex> = <math> 1 + \Theta ( \frac{1}{n}) </math>.
+
[[Эволюционные алгоритмы многокритериальной оптимизации, основанные на индикаторах. Гиперобъем#Коэффициент аппроксимации| Утверждение(3)]] ограничивает значение оптимального коэффицента апроксимации сверху: <tex>1 + \frac{ \log (\min ( \frac{A}{a}, \frac{B}{b}))}{n}</tex> = <math> 1 + \Theta ( \frac{1}{n}) </math>.
  
 
==Нахождение коэффициента аппроксимации множества решения максимизируюшего гиперобъем==
 
==Нахождение коэффициента аппроксимации множества решения максимизируюшего гиперобъем==
Строка 41: Строка 41:
 
Тогда минимальный вклад данного множество решения:
 
Тогда минимальный вклад данного множество решения:
  
<tex>MinCon(X) \leq \frac{(x_n - x_1)(f(x_1) - f(x_n))}{(n-2)^2}</tex>
+
<tex>MinCon(X) \leq \frac{(x_n - x_1)(f(x_1) - f(x_n))}{(n - 2)^2}</tex>
 
|proof=
 
|proof=
 
Исходя из определения минимальный вклад в гиперобъем множества равен минимуму из всевозможных площадей прямоугольников, образующихся между соседними точками множества решения и их значениями.
 
Исходя из определения минимальный вклад в гиперобъем множества равен минимуму из всевозможных площадей прямоугольников, образующихся между соседними точками множества решения и их значениями.
 
Пусть <tex>a_i, b_i </tex> — длины сторон соответствующего прямоугольника, тогда:
 
Пусть <tex>a_i, b_i </tex> — длины сторон соответствующего прямоугольника, тогда:
  
<tex> a_i \geq MINCON(X)/b_i \forall i \in [2, n-1]</tex>
+
<tex> 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> \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>
+
<tex>MINCON(X) \leq \frac{(x_n - x_1)}{\sum\limits_{i = 2}^{n - 1}1/b_i}</tex>
  
 
Так как среднее гармоническое не больше среднего арифметического:
 
Так как среднее гармоническое не больше среднего арифметического:
  
<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>
+
<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>
 
}}
 
}}
  
Строка 67: Строка 67:
 
|statement=Пусть <tex>f \in \mathbb{F}, n > 4</tex>. Любое множество решение <tex>\{x_1, x_2, \ldots, x_d\} \in \mathbb{X}</tex> достигает <tex>\alpha = 1 + \frac{ \sqrt{A/a} + \sqrt{B/b} }{n - 4}</tex> аппроксимации всех внутренних точек.
 
|statement=Пусть <tex>f \in \mathbb{F}, n > 4</tex>. Любое множество решение <tex>\{x_1, x_2, \ldots, x_d\} \in \mathbb{X}</tex> достигает <tex>\alpha = 1 + \frac{ \sqrt{A/a} + \sqrt{B/b} }{n - 4}</tex> аппроксимации всех внутренних точек.
 
|proof=
 
|proof=
Допустим, что существует <tex>x</tex>, который не аппроксимируется <tex>\alpha = 1 + \frac{\sqrt{A/a} + \sqrt{B/b}}{n-4}</tex>.
+
Допустим, что существует <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>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) \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).
+
После подстановки получим <tex>MinCon(X) > (\alpha - 1)^2 x_i f(x_{i + 1})</tex> (1).
  
 
Применив [[#statement2|утверждение(2)]], получим:
 
Применив [[#statement2|утверждение(2)]], получим:
  
<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 [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>\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>(\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}</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>\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>\alpha</tex>: <tex>\alpha < 1 + \frac{\sqrt{A/a} + \sqrt{B/b}}{n - 4}</tex>.
  
Вышесказанное верно для <tex>3 \leq i \leq n-3</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 = 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>, что тоже невозможно по условию теоремы.
+
Для <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>, что тоже невозможно по условию теоремы.
 
}}
 
}}
  
Строка 133: Строка 133:
  
 
=Примечание=
 
=Примечание=
Конечно, зависимость от <tex> [a,A]</tex> и <tex>[b,B] </tex> в аппроксимационном коэффициенте оптимального множества решения меньше чем в аппроксимационном коэффициенте для множества, максимизирующего гиперобъем. Однако, полученная граница для коэффициента аппроксимации является верхней. На рисунке ниже можно увидеть пример поведения данных значений для определенного класса функций.
+
Конечно, зависимость от <tex> [a, A]</tex> и <tex>[b, B] </tex> в аппроксимационном коэффициенте оптимального множества решения меньше чем в аппроксимационном коэффициенте для множества, максимизирующего гиперобъем. Однако, полученная граница для коэффициента аппроксимации является верхней. На рисунке ниже можно увидеть пример поведения данных значений для определенного класса функций.
  
 
[[Файл:Untitled.jpg]]
 
[[Файл:Untitled.jpg]]

Версия 22:11, 19 июня 2012

Основные определения

Определение:
Множество [math]X^* \subseteq \mathbb{X}[/math] называется Парето-оптимальным, если:

[math]\mathrm{\forall x^* \subset X^* \not \exists x \subset \mathbb{X} : x \succ x^*}[/math], где [math] x \succ x^* [/math] ([math]x[/math] доминирует [math]x^*[/math]) [math] \leftrightarrow \left( \forall i \in 1 \ldots d: f_i(x) \geq f_i(x^*) \right) \bigwedge \left( \exists i \in 1 \ldots d: f_i(x) \gt f_i(x^*)\right)[/math]

[math]P(X^*)[/math] - множество оптимальных по Парето решений, его также называют Парето-фронтом. Парето-фронт не может быть вычислен за полиномиальное время.


Определение:
Пусть [math]f \in \mathbb{F}, n \geq 3[/math] и [math]X = \{x_1, \ldots, x_n\} \in \mathbb{X}[/math]. Наименьшим вкладом этого множества называется [math]MinCon(X) = \min \limits_{2 \leq i \leq n - 1} (x_i-x_{i - 1})(f(x_i) - f(x_{i - 1}))[/math].


Связь между максимизацией гиперобъема и аппроксимацией Парето-фронта

Множество функций вида: [math]f:[a, A] \rightarrow [b, B][/math], где [math]f[/math] убывает и [math]f(a) = B, f(A) = b[/math] обозначим через [math]\mathbb{F}[/math].

Коэффициент апроксимации монотонно убывающих функций не зависит от масштабов отрезков [math] [a, A][/math] и [math][b, B] [/math]. Так как для фиксированных констант [math] \mu , \nu [/math] функция [math] f^*:[ \mu a , \mu A ] \rightarrow [ \nu b , \nu B ][/math] и [math] f^*= \nu f(x/ \mu ) [/math] имеет тот же коэффициент аппроксимации. Однако, коэффициент аппроксимации зависит от значений [math]A/a[/math] и [math]B/b[/math].

Далее будем рассматривать только монотонно убывающие, полунепрерывные Парето-фронты. Условие полунепрерывности необходимо для того, чтобы существовало множество решение, максимизирующее индикатор гиперобъема.

Рассмотрим оптимальный коэффициент апроксимации для данного Парето-фронта из n ([math] \alpha _{OPT}[/math]) и верхнюю границу коэффициента аппроксимации для множества из n точек, максимизирующего значение индикатора гиперобъема ([math] \alpha _{HYP}[/math]) и докажем, что для количества точек [math] n [/math] они одинаковы, а именно [math] 1 + \Theta ( \frac{1}{n}) [/math].

Индикатор гиперобъема

Утверждение (1):
Пусть [math]f \in \mathbb{F}, n \in \mathbb{N}[/math]. Тогда существует, не обязятельно единственное, множество решения [math]X \in \mathbb{X}[/math], которое максимизирует значение гиперобъема ([math]HYP(X)[/math]) на [math]\mathbb{X}[/math]
[math]\triangleright[/math]
Доказательство представлено в статье Эволюционные алгоритмы многокритериальной оптимизации, основанные на индикаторах. Гиперобъем
[math]\triangleleft[/math]

Нахождение лучшего коэффициента аппроксимации

Утверждение(3) ограничивает значение оптимального коэффицента апроксимации сверху: [math]1 + \frac{ \log (\min ( \frac{A}{a}, \frac{B}{b}))}{n}[/math] = [math] 1 + \Theta ( \frac{1}{n}) [/math].

Нахождение коэффициента аппроксимации множества решения максимизируюшего гиперобъем

Утверждение (2):
Пусть [math]f \in \mathbb{F}, n \geq 3[/math] и [math]X= \{x_1, x_2, \ldots, x_d \} \in X [/math].

Тогда минимальный вклад данного множество решения:

[math]MinCon(X) \leq \frac{(x_n - x_1)(f(x_1) - f(x_n))}{(n - 2)^2}[/math]
[math]\triangleright[/math]

Исходя из определения минимальный вклад в гиперобъем множества равен минимуму из всевозможных площадей прямоугольников, образующихся между соседними точками множества решения и их значениями. Пусть [math]a_i, b_i [/math] — длины сторон соответствующего прямоугольника, тогда:

[math] a_i \geq MinCon(X)/b_i \forall i \in [2, n - 1][/math]

Это означает:

[math] \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 [/math]

и поэтому: [math]MINCON(X) \leq \frac{(x_n - x_1)}{\sum\limits_{i = 2}^{n - 1}1/b_i}[/math]

Так как среднее гармоническое не больше среднего арифметического:

[math]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}[/math]
[math]\triangleleft[/math]

Далее необходимо посчитать коэффициент аппроксимации для "внутренних" ([math]x \in [x_1, x_n][/math]) и "внешних" точек ([math]x \lt x_1[/math] или [math]x \gt x_n[/math]).

Теорема (1):
Пусть [math]f \in \mathbb{F}, n \gt 4[/math]. Любое множество решение [math]\{x_1, x_2, \ldots, x_d\} \in \mathbb{X}[/math] достигает [math]\alpha = 1 + \frac{ \sqrt{A/a} + \sqrt{B/b} }{n - 4}[/math] аппроксимации всех внутренних точек.
Доказательство:
[math]\triangleright[/math]

Допустим, что существует [math]x[/math], который не аппроксимируется [math]\alpha = 1 + \frac{\sqrt{A/a} + \sqrt{B/b}}{n - 4}[/math]. Пусть [math]x_i \lt x \lt x_i + 1[/math], тогда [math]x \gt \alpha x_i, f(x) \gt \alpha f(x_{i + 1})[/math].

Известно, что [math]MinCon(X) \geq (x - x_i)(f(x) - f(x_{i + 1}))[/math].

После подстановки получим [math]MinCon(X) \gt (\alpha - 1)^2 x_i f(x_{i + 1})[/math] (1).

Применив утверждение(2), получим:

[math]\forall i \in [3, n - 1][/math] [math]MinCon(X) \leq (x_i - x_1)(f(x_1) - f(x_i))/(i - 2)^2 \leq x_iB/(i - 2)^2[/math] (2)

[math]\forall i \in [1, n - 3][/math] [math]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[/math] (3)

Таким образом, [math](\alpha - 1)^2 x_i f(x_{i + 1}) \lt \min \{\frac{x_iB}{(i - 2)^2} ,\frac{A f(x_{i + 1})}{(n - i - 2)^2}\} \Leftrightarrow[/math] [math]\alpha \lt 1 + \min \{\frac{\sqrt{x_iB}}{i - 2} ,\frac{\sqrt{A f(x_{i + 1})}}{n - i - 2}\}[/math].

Т.к. [math]\frac{\sqrt{x_iB}}{i - 2}[/math] монотонно убывает, а [math]\frac{\sqrt{A f(x_{i + 1})}}{n - i - 2}\}[/math] монотонно возрастает, то максимальное значение [math]\min \{\frac{\sqrt{x_iB}}{i - 2} ,\frac{\sqrt{A f(x_{i + 1})}}{n - i - 2}\}[/math] достигается при равенстве обоих членов:

[math]\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}}[/math].

Получим верхнюю оценку для [math]\alpha[/math]: [math]\alpha \lt 1 + \frac{\sqrt{A/a} + \sqrt{B/b}}{n - 4}[/math].

Вышесказанное верно для [math]3 \leq i \leq n - 3[/math].

Для [math]i = 1, 2[/math] из (1) и (3) следует, что [math]\alpha \lt 1 + \frac{\sqrt{A/a}}{n - i - 2} \leq 1 + \frac{\sqrt{A/a}}{n - 4}[/math], что невозможно по условию теоремы.

Для [math]i = n - 2, n - 1[/math] по (1) и (2) [math]\alpha \lt 1 + \frac{ \sqrt{B/b} } {i - 2} \leq 1 + \frac {\sqrt {B/b} } {n - 4}[/math], что тоже невозможно по условию теоремы.
[math]\triangleleft[/math]
Теорема (2):
Пусть [math]f \in \mathbb{F}, n \gt 3[/math]. И [math] R = (R_x, R_y) \leq (0, 0) [/math] является точкой отсчета. Каждое множество решение [math]\{x_1, x_2, \ldots, x_d\} \in \mathbb{X} [/math] достигает [math]1 + \frac{A}{(a - R_x)(n - 2)^2}[/math] аппроксимации всех точек с [math]x \lt x_1[/math] и [math]1 + \frac{B}{(b - R_y)(n - 2)^2}[/math] аппроксимации всех точек с [math]x \gt x_n[/math].
Доказательство:
[math]\triangleright[/math]
Доказательство производится c использованием ранее доказанного утверждения о [math]MinCon[/math].
[math]\triangleleft[/math]


Из теоремы(1) и теоремы(2) выводятся следующие следствия:

Следствие 1: [math]\alpha_{opt} = 1 + \Theta(1/n)[/math]

Пусть [math]f \in \mathbb{F}, n \gt 4[/math], и [math] R = (R_x, R_y) \leq (0, 0) [/math] является точкой отсчета. Тогда:

[math] \lambda_{HYP} \leq 1 + \max{ \frac{ \sqrt{A/a} + \sqrt{B/b} }{n - 4}}{\frac{A}{(a - R_x)(n - 2)^2}}{\frac{B}{(b - R_y)(n - 2)^2}}[/math]


Следствие 2: [math]\alpha_{opt} = 1 + \Theta(1/n)[/math]

Пусть [math]f \in \mathbb{F}, n \gt 4[/math]. И [math] R = (R_x, R_y) \leq (0, 0) [/math] является точкой отсчета. Тогда если

[math] n \geq 2 + \max{\sqrt{A/a}}{\sqrt{B/b}}[/math]

или

[math]R_x \leq - \sqrt{Aa}/n, R_y \leq - \sqrt{Bb}/n[/math], выполняется следующее неравенство

[math] \alpha _{HYP} \leq 1 + \frac{ \sqrt{ \frac{A}{a}} + \sqrt{ \frac{B}{b}}}{n - 4}[/math] = [math] 1 + \Theta ( \frac{1}{n}) [/math],

то есть

[math] \alpha _{HYP} [/math] = [math] 1 + \Theta ( \frac{1}{n}) [/math],

что и требовалось доказать.

Примечание

Конечно, зависимость от [math] [a, A][/math] и [math][b, B] [/math] в аппроксимационном коэффициенте оптимального множества решения меньше чем в аппроксимационном коэффициенте для множества, максимизирующего гиперобъем. Однако, полученная граница для коэффициента аппроксимации является верхней. На рисунке ниже можно увидеть пример поведения данных значений для определенного класса функций.

Untitled.jpg

Источники

  1. Friedrich T., Bringmann K. - The Maximum Hypervolume Set Yields Near-optimal Approximation