23
правки
Изменения
Нет описания правки
|about=2
|definition=Коэффициентом аппроксимации функции <tex>f</tex> на <tex>X</tex> называется
<tex>\mathrm{\alpha (f, X) = inf \{\alpha | X} - — \alpha</tex>-аппроксимация <tex>f \}</tex>.
}}
|proof=
Рассмотрим <tex>\alpha = (\frac{A}{a})^{\frac{1}{n}}</tex>, тогда <tex>x_i=a \alpha^i(i=1 \ldots n)</tex>.
<tex>\{x_i\}</tex> - — <tex>\alpha</tex>-аппроксимация, т.к. <tex>\forall x \in [x_i, x_{i+1}]: f(x) \leq \alpha f(x_i)</tex>.
Следовательно, <tex>\alpha_{opt} \leq \alpha</tex>.
}}
Тогда <tex>f(x_i) \geq B \alpha^{-i}</tex>.
Следовательно, <tex>\not \exists x: f(x_i)>f(x)>B \alpha^{-1}</tex>.
Таким образом, <tex>\{x_i\}</tex> - — <tex>\alpha</tex>-аппроксимация, так как <tex>B \alpha^{-i} \leq f(x) \leq B \alpha^{-i+1}</tex>.
}}
Пусть <tex>\forall i \in \{0, 1, \ldots, n\} f(x)=B(B/b)^{-i/n}</tex> на интервале <tex>(a(A/a)^{(i-1)/n}, a(A/a)^{i/n}]</tex>.
Теперь <tex>f</tex> - — это фронт Парето из <tex>n+1</tex> слоя. Предложим, множество решений <tex>\{x_1,x_2, \ldots , x_n\}</tex> из <tex>n</tex> точек. По принципу Дирихле получается, что хотя бы на одном уровне нет ни одного решения. Это означает, что верхняя граница этого уровня аппроксимируется значением <tex>\min ( \frac{A}{a}, \frac{B}{b})^{\frac{1}{n}}</tex>.
}}
<tex>= \sum\limits_{i = 1}^{n} (x_i-x_{i-1})(\lim\limits_{i \rightarrow \infty} f(x_i^j) - r) = \sum\limits_{i = 1}^{n} (x_i-x_{i-1})(f(x_i) - r) = HYP(X)</tex>
Получается, что <tex>HYP(X)</tex> - — верхняя полунепрерывная, следовательно, экстремум <tex>HYP</tex> достигается на компакте.
}}
= Источники =
# [http://rain.ifmo.ru/~tsarev/teaching/ea-2012/lectures/4/2010GECCO_Hyp.pdf Friedrich T., Bringmann K. - — The Maximum Hypervolume Set Yields Near-optimal Approximation]# [http://rain.ifmo.ru/~tsarev/teaching/ea-2012/lectures/3/multiobjectivization.pdf Corne D., Knowles J., Watson R. - — Reducing Local Optima in Single-Objective Problems by Multi-objectivization]# [http://www.mpi-inf.mpg.de/~tfried/paper/2009GECCO.pdf Friedrich T., Horoba C., Neumann F. - — Multiplicative Approximations and the Hypervolume Indicator]# [ftp://ife.ee.ethz.ch/pub/people/zitzler/ZK2004a.pdf Kunzli S., Zitzle E. - — Indicator-Based Selection in Multiobjective Search]
