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

Материал из Викиконспекты
Версия от 16:46, 19 июня 2012; 84.204.86.204 (обсуждение) (Нахождение коэффициента аппроксимации множества решения максимизируюшего гиперобъем)
Перейти к: навигация, поиск

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

Определение:
Множество [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]).

Теорема:
Пусть [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]
Теорема:
Пусть [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 приводят к следующим следствиям:

Следствие: [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]


Следствие: [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


Источники