Связь между максимизацией гиперобъема и аппроксимацией Парето-фронта — различия между версиями
(→Нахождение коэффициента аппроксимации множества решения максимизируюшего гиперобъем) |
|||
Строка 66: | Строка 66: | ||
}} | }} | ||
− | Далее необходимо посчитать коэффициент аппроксимации для внутренних и внешних точек | + | Далее необходимо посчитать коэффициент аппроксимации для "внутренних" (<tex>x \in [x_1, x_n]</tex>) и "внешних" точек <tex>x < x_1</tex> или <tex>x > x_n</tex>. |
− | {{ | + | {{Теорема (1) |
− | |statement=Пусть <tex>f \in \mathbb{F}, n | + | |statement=Пусть <tex>f \in \mathbb{F}, n > 4</tex>. Любое множество ррешение <tex>(x_1, x_2, \ldots, x_d \right) \in X_{HYP}^f </tex> достигает <tex>1 + \frac{ \sqrt{A/a} + \sqrt{B/b} }{n - 4}</tex> мультипликативной аппроксимации всех внутренних точек. |
− | + | |proof= | |
+ | Доказательство производится от противного, принимая предположение, что существует такой <tex> x</tex>, для которого бы не не выполнялось условие аппроксимации при данном коэффициенте. | ||
+ | }} | ||
− | <tex> | + | {{Теорема (2) |
+ | |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 \right) \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= | ||
− | + | Доказательство производится c использованием ранее доказонного утверждения о MINCON. | |
− | + | }} | |
− | + | Совместно Теоремы 1 и 2 приводят к следующим следствиям: | |
− | + | {{Следствие | |
+ | |statement=Пусть <tex>f \in \mathbb{F}, n > 4</tex>. И <tex> R = (R_x, R_y) \leq (0, 0) </tex> является точкой отсчета. Тогда: | ||
− | <tex> \ | + | <tex> \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}}</tex> |
− | + | |proof= | |
− | + | Доказательство производится c использованием ранее доказонного утверждения о MINCON. | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
}} | }} | ||
− | |||
В статье [1], п. 4 приведено доказательство того, что для данного вида функций всегда существует множество решение, максимизирующее значение индикатора гиперобъема, а также устанавливает значение коэффициент аппроксимации значением: <tex>1 + \frac{ \sqrt{ \frac{A}{a}} + \sqrt{ \frac{B}{b}}}{n - 4}</tex> = <math> 1 + \Theta ( \frac{1}{n}) </math>. | В статье [1], п. 4 приведено доказательство того, что для данного вида функций всегда существует множество решение, максимизирующее значение индикатора гиперобъема, а также устанавливает значение коэффициент аппроксимации значением: <tex>1 + \frac{ \sqrt{ \frac{A}{a}} + \sqrt{ \frac{B}{b}}}{n - 4}</tex> = <math> 1 + \Theta ( \frac{1}{n}) </math>. |
Версия 05:14, 19 июня 2012
Содержание
Основные определения
Определение: |
Множество , где ( доминирует ) - множество оптимальных по Парето решений, его также называют Парето-фронтом. Парето-фронт не может быть вычислен за полиномиальное время. | называется Парето оптимальным, если:
Определение: |
Множество решений
Коэффицент аппроксимации функции Оптимальный коэффицент аппроксимации на равен: аппроксимация | называется -аппроксимацией функции , если:
Свзяь между максимизацией гиперобъема и аппроксимацией Парето-фронта
Рассмотрим функции вида:
, где убывает и . Коэффициент апроксимации монотонно убывающих функций не зависит от масштабов отрезков и . Так как для фиксированных констант функция и имеет тот же коэффициент аппроксимации. Однако, коэффициент аппроксимации зависит от значений и .Множество всех таких функций обозначим через чтобы существовало множество решение, максимизирующее индикатор гиперобъема.
. Далее будем рассматривать только монотонно убывающие, полунепрерывные Парето-фронты. Условие полунепрерывности необходимо для того,Рассмотрим оптимальный коэффициент апроксимации для данного Парето-фронта из n (
) и верхнюю границу коэффициента аппроксимации для множества из n точек, максимизирующего значение индикатора гиперобъема ( ) и докажем, что для количества точек они одинаковы, а именно .Индикатор гиперобъема
Определение: |
Пусть дано множество решения Гиперобъем является единственным унарным индикатором эластичным по Парето(Pareto-compliant). , где через обозначена мера множества | . Пусть также множество всех решений усечено некоторой точкой . Тогда:
Утверждение: |
Пусть .
Тогда существует, не обязятельно единственное, множество решения , которое максимизирует значение на |
См. [Гиперобъем] |
Нахождение лучшего коэффициента аппроксимации
[Доказательство] ограничивает значение оптимального коэффицента апроксимации сверху: = .
Нахождение коэффициента аппроксимации множества решения максимизируюшего гиперобъем
Утверждение: |
Пусть и .
Тогда [MINCON] данного множество решения: |
Исходя из определения минимальный вклад в гиперобъем множества равен минимуму из всевозможных площадей прямоугольников, образующихся между соседними точками множества решения и их значенияями. Пусть - длины сторон соответствующего прямоугольника, тогда:
Это означает:
и поэтому: Так как среднее гармоническое меньше чем среднее арифметическое: Преобразуя, получаем искомое. |
Далее необходимо посчитать коэффициент аппроксимации для "внутренних" (
) и "внешних" точек или .Теорема (Автор утверждения (необязательно), О чем утверждение (необязательно)): |
утверждение |
Доказательство: |
доказательство (необязательно) |
Теорема (Автор утверждения (необязательно), О чем утверждение (необязательно)): |
утверждение |
Доказательство: |
доказательство (необязательно) |
Совместно Теоремы 1 и 2 приводят к следующим следствиям:
{{Следствие |id=идентификатор (необязательно), пример: proposal1. |author=Автор утверждения (необязательно) |about=О чем утверждение (необязательно) |statement=утверждение |proof=доказательство (необязательно) }}
В статье [1], п. 4 приведено доказательство того, что для данного вида функций всегда существует множество решение, максимизирующее значение индикатора гиперобъема, а также устанавливает значение коэффициент аппроксимации значением:
= .Примечание
Конечно, зависимость от
и в аппроксимационном коэффициенте оптимального множества решения меньше чем в аппроксимационном коэффициенте для множества, максимизирующего гиперобъем. Однако, полученная граница для коэффициента аппроксимации является верхней. На рисунке ниже Вы можете увидеть пример поведения данных значений для определенного класса функций.