64
правки
Изменения
→Основные определения
|about=2
|definition=
Фиксируем <tex>n</tex>. Для фиксированного отрезка <tex> [a, A]</tex> будем называть кортеж <tex> X = (x_1, \ldots, x_n)</tex>, такой что <tex>a \leq x_1 \leq \ldots \leq x_n \leq A</tex> - множеством-решением. И множество таких решений будем обозначать через <tex>\mathbb{X}</tex>.
}}
{{Определение
|id=definition3
|about=3
|definition=Пусть <tex>f \in \mathbb{F}, n \geq 3</tex> и <tex>X = \{(x_1, \ldots, x_n\} ) \in \mathbb{X}</tex>. Вкладом этого множества -решения называется <tex>Con(X) = x_i-x_{i - 1})(f(x_i) - f(x_{i - 1})</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>.
}}
Далее будем рассматривать только монотонно убывающие, полунепрерывные [[Задача многокритериальной оптимизации. Multiobjectivization#Множество Парето оптимальных значений|Парето-фронты]]. Условие полунепрерывности необходимо для того, [[#statement1|чтобы существовало множество -решение, максимизирующее индикатор гиперобъема]].
Рассмотрим оптимальный коэффициент апроксимации для данного Парето-фронта из n (<tex> \alpha _{OPT}</tex>) и верхнюю границу коэффициента аппроксимации для множества из n точек, максимизирующего значение индикатора гиперобъема (<tex> \alpha _{HYP}</tex>) и докажем, что для количества точек <tex> n </tex> они одинаковы, а именно <math> 1 + \Theta ( \frac{1}{n}) </math>.
|about=2
|id=statement2
|statement=Пусть <tex>f \in \mathbb{F}, n \geq 3</tex> и <tex>X= \{(x_1, x_2, \ldots, x_d \} ) \in 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, b_i </tex> — длины сторон соответствующего прямоугольника, тогда:
|about=1
|id=theorem1
|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=
Допустим, что существует <tex>x</tex>, который не аппроксимируется <tex>\alpha = 1 + \frac{\sqrt{A/a} + \sqrt{B/b}}{n - 4}</tex>.
|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 \mathbb{X} </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 использованием [[#statement2|ранее доказанного утверждения]] о <tex>MinCon</tex>.
