23
правки
Изменения
Нет описания правки
Введем несколько понятий:
{{Определение
|id=definition1
|about=1
|definition=Множество решений <tex>\mathrm{X=(x_1,x_2, \ldots , x_n)}</tex> называется <tex>\alpha</tex>-аппроксимацией функции <tex>f \in \mathbb{F}</tex>, если:
<tex>\mathrm{\forall x \in [a,A] \exists x_i \in X : (x \leq \alpha x_i) \bigwedge (f(x) \leq \alpha f(x_i))}</tex>
{{Определение
|id=definition2
|about=2
|definition=Коэффицентом аппроксимации функции <tex>f</tex> на <tex>X</tex> равен:
<tex>\mathrm{\alpha (f, X) = inf \{\alpha | X} - \alpha</tex> аппроксимация <tex>f \}</tex>
{{Определение
|id=definition3
|about=3
|definition=Оптимальный коэффицент аппроксимации <tex>\alpha_{opt} = \sup \limits_{f \in \mathbb{F}} \inf \limits_{x \in \mathbb{X}} \alpha (f, X)</tex>
}}
{{Утверждение
|id=statement3
|about=3
|statement=
<tex>\forall n \geq \log (\min ( \frac{A}{a}, \frac{B}{b})) / \varepsilon </tex>, где <tex>\varepsilon \in (0,1)</tex>, выполняется:
Существует много различных индикаторов, с помощью которых численно оценивают качество решений. Но широко используется только один.
{{Определение
|id=definition4|about=4|definition=Индикатор называется эластичным по Парето(Pareto-compliant), если для любых двух множеств решения <tex>A</tex> и <tex>B</tex> значение индикатора для <tex>A</tex> больше значения для <tex>B</tex> тогда и только тогда, когда <tex>A</tex> [[Задача_многокритериальной_оптимизации._Multiobjectivization#section=3|доминирует ]] <tex>B</tex>.
}}
Дадим определение индикатора гиперобъема<tex>\left(HYP\right)</tex>.
{{Определение
|id=definition5
|about=5
|definition=Пусть дано множество решения <tex>\mathrm{X \in \mathbb{R}^d}</tex>. Пусть также множество всех решений усечено некоторой точкой <tex>\mathrm{r = \left(r_1, r_2, \ldots, r_d \right)}</tex>. Тогда:
<tex>\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)}</tex>, где через <tex>VOL(X)</tex> обозначена мера множества <tex>X</tex> [[Мера_Лебега_в_R%5En|по Лебегу]].
{{Утверждение
|id=statement4
|about=4
|statement=Пусть <tex>f \in \mathbb{F}, n \in \mathbb{N}</tex>.
Тогда существует, не обязятельно единственное, множество решения <tex>X \in \mathbb{X}</tex>, которое максимизирует значение <tex>HYP(X)</tex> на <tex>\mathbb{X}</tex>
</tex>
Получается, что <tex>HYP(X)</tex> - верхняя полунепрерывная, следовательно экстремум <tex>HYP</tex> достикается на компакте.
}}
{{Определение
|id=definition6
|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>.
}}
{{Утверждение
|id=statement5
|about=5
|statement=Пусть <tex>f \in \mathbb{F}, n \geq 3</tex> и <tex>X = (x_1, \ldots, x_n) \in \mathbb{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=x_i-x_{i-1}</tex> <tex>\forall i \in [2,n]</tex> и <tex>b_i=f(x_i)-f(x_{i-1})</tex> <tex>\forall i \in [1,n-1]</tex>.
Подставив в [[#definition6|определние(6)]], получим:
<tex>MinCon(X)= \min \limits_{2 \leq i \leq n-1} a_i b_i \Leftrightarrow 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>MinCon(X) \leq \frac{x_n-x_1}{\sum \limits_{i=2}^{n-1}1/b_i}</tex>
Cреднее гармоническое меньше среднего арифметического, тогда:
<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>
}}
{{Теорема
|statement=Пусть <tex>f \in \mathbb{F}, n > 4</tex> и <tex>X = (x_1, \ldots, x_n) \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>.
Пусть <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) > (\alpha - 1)^2 x_i f(x_{i+1})</tex> (1).
Применив [[#statement5|утверждение(5)]], получим:
<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>(\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} = \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>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 = n-2, n-2</tex> из (1) и (2) получим:
<tex>\alpha < 1 + \frac{ \sqrt{B/b} } {i-2} \leq 1 + \frac {\sqrt {B/b} } {n-4}</tex>
что тоже невозможно по условию теоремы.
}}
