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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Нахождение коэффициента аппроксимации множества решения максимизируюшего гиперобъем)
Строка 20: Строка 20:
 
Рассмотрим функции вида: <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>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=Эволюционные_алгоритмы_многокритериальной_оптимизации,_основанные_на_индикаторах._Гиперобъем| чтобы существовало множество решение, максимизирующее индикатор гиперобъема].
+
Множество всех таких функций обозначим через <tex>\mathbb{F}</tex>. Далее будем рассматривать только монотонно убывающие, полунепрерывные Парето-фронты. Условие полунепрерывности необходимо для того, [[Эволюционные алгоритмы многокритериальной оптимизации, основанные на индикаторах. Гиперобъем#Индикатор Гиперобъема|чтобы существовало множество решение, максимизирующее индикатор гиперобъема]].
  
 
Рассмотрим оптимальный коэффициент апроксимации для данного Парето-фронта из n (<tex> \alpha _{OPT}</tex>) и верхнюю границу коэффициента аппроксимации для множества из n точек, максимизирующего значение индикатора гиперобъема (<tex> \alpha _{HYP}</tex>) и докажем, что для количества точек <tex> n </tex> они одинаковы, а именно <math> 1 + \Theta ( \frac{1}{n}) </math>.
 
Рассмотрим оптимальный коэффициент апроксимации для данного Парето-фронта из n (<tex> \alpha _{OPT}</tex>) и верхнюю границу коэффициента аппроксимации для множества из n точек, максимизирующего значение индикатора гиперобъема (<tex> \alpha _{HYP}</tex>) и докажем, что для количества точек <tex> n </tex> они одинаковы, а именно <math> 1 + \Theta ( \frac{1}{n}) </math>.
Строка 34: Строка 34:
 
Тогда существует, не обязятельно единственное, множество решения <tex>X \in \mathbb{X}</tex>, которое максимизирует значение <tex>HYP(X)</tex> на <tex>\mathbb{X}</tex>
 
Тогда существует, не обязятельно единственное, множество решения <tex>X \in \mathbb{X}</tex>, которое максимизирует значение <tex>HYP(X)</tex> на <tex>\mathbb{X}</tex>
 
|proof=
 
|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>.  
+
[[Эволюционные алгоритмы многокритериальной оптимизации, основанные на индикаторах. Гиперобъем#Индикатор Гиперобъема| Доказательство]] ограничивает значение оптимального коэффицента апроксимации сверху: <tex>1 + \frac{\log (\min ( \frac{A}{a}, \frac{B}{b}))}{n}</tex> = <math> 1 + \Theta ( \frac{1}{n}) </math>.  
  
 
==Нахождение коэффициента аппроксимации множества решения максимизируюшего гиперобъем==
 
==Нахождение коэффициента аппроксимации множества решения максимизируюшего гиперобъем==
Строка 70: Строка 70:
 
{{Теорема
 
{{Теорема
 
|about=1
 
|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> мультипликативной аппроксимации всех внутренних точек.
 
|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=
 
|proof=
Строка 77: Строка 78:
 
{{Теорема
 
{{Теорема
 
|about=2
 
|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>.
 
|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=
 
|proof=
Строка 83: Строка 85:
  
  
Совместно теоремы 1 и 2 приводят к следующим следствиям:
+
Совместно [[#theorem1|теорема(1)]] и [[#theorem2|теорема(2)]] приводят к следующим следствиям:
  
 
'''Следствие 1:''' <tex>\alpha_{opt} = 1 + \Theta(1/n)</tex>
 
'''Следствие 1:''' <tex>\alpha_{opt} = 1 + \Theta(1/n)</tex>

Версия 18:34, 19 июня 2012

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

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

[math]\mathrm{\forall x^* \subset X^* \not \exists x \subset 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]\mathrm{X=\{x_1,x_2, \ldots , x_n\}}[/math] называется [math]\alpha[/math]-аппроксимацией функции [math]f \in \mathbb{F}[/math], если:

[math]\mathrm{\forall x \in [a,A] \exists x_i \in X : (x \leq \alpha x_i) \bigwedge (f(x) \leq \alpha f(x_i))}[/math]

Коэффицент аппроксимации функции [math]f[/math] на [math]X[/math] равен: [math]\mathrm{\alpha (f, X) = inf \{\alpha | X} - \alpha[/math] аппроксимация [math]f \}[/math]

Оптимальный коэффицент аппроксимации [math]\alpha_{opt} = \sup \limits_{f \in \mathbb{F}} \inf \limits_{x \in \mathbb{X}} \alpha (f, X)[/math]


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

Рассмотрим функции вида: [math]f:[a,A] \rightarrow [b,B][/math], где [math]f[/math] убывает и [math]f(a)=B, f(A)=b[/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].

Множество всех таких функций обозначим через [math]\mathbb{F}[/math]. Далее будем рассматривать только монотонно убывающие, полунепрерывные Парето-фронты. Условие полунепрерывности необходимо для того, чтобы существовало множество решение, максимизирующее индикатор гиперобъема.

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

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

Определение:
Пусть дано множество решения [math]\mathrm{X \in \mathbb{R}^d}[/math]. Пусть также множество всех решений усечено некоторой точкой [math]\mathrm{r = \left(r_1, r_2, \ldots, r_d \right)}[/math]. Тогда:

[math]\mathrm{HYP\left(X\right)=VOL\left( \bigcup\limits_{\left(x_1, x_2, \ldots, x_d \right) \in X} \left[ r_1, x_1\right] \times \left[ r_2, x_2\right] \times \cdots \times \left[ r_d, x_d\right] \right)}[/math], где через [math]VOL(X)[/math] обозначена мера множества [math]X[/math] по Лебегу.

Гиперобъем является единственным унарным индикатором эластичным по Парето(Pareto-compliant).
Утверждение:
Пусть [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]

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

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

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

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

Тогда [MINCON] данного множество решения:

[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[/math], для любого [math]2 \leq i \leq 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] \frac{n - 2}{\sum\limits_{i=2}^{n-1}1/b_i} \leq \frac{\sum\limits_{i=2}^{n-1}1/b_i}{n - 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 X_{HYP}^f [/math] достигает [math]1 + \frac{ \sqrt{A/a} + \sqrt{B/b} }{n - 4}[/math] мультипликативной аппроксимации всех внутренних точек.
Доказательство:
[math]\triangleright[/math]
Доказательство производится от противного, принимая предположение, что существует такой [math] x[/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 X_{HYP}^f [/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 использованием ранее доказанного утверждения о MINCON.
[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