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

Существует класс эволюционных алгоритмов, основывающихся на индикаторах для решения задачи многокритериальной оптимизации. В данной статье приводится доказательство правомерности использования индикатора гиперобъема в качестве максимизируемого значения. Это проблема впервые приведена в работе .

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

Определение:

Множество функций вида: [math]f:[a, A] \rightarrow [b, B][/math], где [math]f[/math] убывает и [math]f(a) = B, f(A) = b[/math] обозначим через [math]\mathbb{F}[/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]n[/math]. Для фиксированного отрезка [math] [a, A][/math] будем называть кортеж [math] X = (x_1, \ldots, x_n)[/math], такой что [math]a \leq x_1 \leq \ldots \leq x_n \leq A[/math] — множеством-решением. Множество таких решений будем обозначать [math]\mathbb{X}[/math].

Определение:

Пусть [math]f \in \mathbb{F}, n \geq 3[/math] и [math]X = (x_1, \ldots, x_n) \in \mathbb{X}[/math]. Тогда вкладом [math]i[/math]-й точки в гиперобъем решения называется [math]Con(i, X) = (x_i-x_{i - 1})(f(x_i) - f(x_{i + 1}))[/math]. Минимальным вкладом в гиперобъем множества-решения называется [math]MinCon(X) = \min \limits_{2 \leq i \leq n - 1} (x_i-x_{i - 1})(f(x_i) - f(x_{i + 1}))[/math].

Далее будем рассматривать только монотонно убывающие, полунепрерывные Парето-фронты. Условие полунепрерывности необходимо для того, чтобы существовало множество-решение, максимизирующее индикатор гиперобъема.

Рассмотрим оптимальный коэффициент апроксимации для данного Парето-фронта из [math]n[/math] точек [math] \alpha _{OPT}[/math] и верхнюю границу коэффициента аппроксимации для множества из [math]n[/math] точек, максимизирующего значение индикатора гиперобъема [math] \alpha _{HYP}[/math], и докажем, что для количества точек [math] n [/math] они одинаковы, а именно равны [math] 1 + \Theta ( \frac{1}{n}) [/math].

Индикатор гиперобъема

Утверждение (1):

Пусть [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]1 + \frac{ \log (\min ( \frac{A}{a}, \frac{B}{b}))}{n}[/math] = [math] 1 + \Theta ( \frac{1}{n}) [/math].

Нахождение коэффициента аппроксимации множества-решения максимизируюшего гиперобъем

Утверждение (2):

Пусть [math]f \in \mathbb{F}, n \geq 3[/math] и [math]X= (x_1, x_2, \ldots, x_n ) \in X [/math]. Тогда минимальный вклад данного множества-решения: [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]i \in [2, 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]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}[/math]

[math]\triangleleft[/math]

Далее необходимо посчитать коэффициент аппроксимации для «внутренних» ([math]x \in [x_1, x_n][/math]) и «внешних» точек ([math]x \lt x_1[/math] или [math]x \gt x_n[/math]).

Теорема (1):

Пусть [math]f \in \mathbb{F}, n \gt 4[/math]. Любое множество-решение [math](x_1, x_2, \ldots, x_d) \in \mathbb{X}[/math] достигает [math]\alpha = 1 + \frac{ \sqrt{A/a} + \sqrt{B/b} }{n - 4}[/math] аппроксимации всех внутренних точек.

Доказательство:

[math]\triangleright[/math]

Допустим, что существует [math]x[/math], который не аппроксимируется [math]\alpha = 1 + \frac{\sqrt{A/a} + \sqrt{B/b}}{n - 4}[/math]. Пусть [math]x_i \lt x \lt x_i + 1[/math], тогда [math]x \gt \alpha x_i, f(x) \gt \alpha f(x_{i + 1})[/math]. Известно, что [math]MinCon(X) \geq (x - x_i)(f(x) - f(x_{i + 1}))[/math]. После подстановки получим [math]MinCon(X) \gt (\alpha - 1)^2 x_i f(x_{i + 1})[/math] (1). Применив утверждение (2), получим: [math]MinCon(X) \leq (x_i - x_1)(f(x_1) - f(x_i))/(i - 2)^2 \leq x_iB/(i - 2)^2[/math] для всех [math]i \in [3, n - 1][/math] (2) [math]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[/math] для всех [math]i \in [1, n - 3][/math] (3) Таким образом, [math](\alpha - 1)^2 x_i f(x_{i + 1}) \lt \min \{\frac{x_iB}{(i - 2)^2} ,\frac{A f(x_{i + 1})}{(n - i - 2)^2}\} \Leftrightarrow[/math] [math]\alpha \lt 1 + \min \{\frac{\sqrt{x_iB}}{i - 2} ,\frac{\sqrt{A f(x_{i + 1})}}{n - i - 2}\}[/math]. Т.к. [math]\frac{\sqrt{x_iB}}{i - 2}[/math] монотонно убывает, а [math]\frac{\sqrt{A f(x_{i + 1})}}{n - i - 2}[/math] монотонно возрастает, то максимальное значение [math]\min \{\frac{\sqrt{x_iB}}{i - 2} ,\frac{\sqrt{A f(x_{i + 1})}}{n - i - 2}\}[/math] достигается при равенстве обоих членов: [math]\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}}[/math]. Получим верхнюю оценку для [math]\alpha[/math]: [math]\alpha \lt 1 + \frac{\sqrt{A/a} + \sqrt{B/b}}{n - 4}[/math]. Вышесказанное верно для [math]3 \leq i \leq n - 3[/math]. Для [math]i = 1, 2[/math] из (1) и (3) следует, что [math]\alpha \lt 1 + \frac{\sqrt{A/a}}{n - i - 2} \leq 1 + \frac{\sqrt{A/a}}{n - 4}[/math], что невозможно по условию теоремы. Для [math]i = n - 2, n - 1[/math] по (1) и (2) [math]\alpha \lt 1 + \frac{ \sqrt{B/b} } {i - 2} \leq 1 + \frac {\sqrt {B/b} } {n - 4}[/math], что тоже невозможно по условию теоремы.

[math]\triangleleft[/math]

Теорема (2):

Пусть [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_n) \in \mathbb{X} [/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 использованием ранее доказанного утверждения о [math]MinCon[/math].

[math]\triangleleft[/math]

Из теоремы (1) и теоремы (2) выводятся следующие следствия:

Утверждение (Следствие 1):

Пусть [math]f \in \mathbb{F}, n \gt 4[/math], и [math] R = (R_x, R_y) \leq (0, 0) [/math] является точкой отсчета. Тогда: [math] \alpha_{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]

Утверждение (Следствие 2):

Пусть [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] в аппроксимационном коэффициенте оптимального множества решения меньше, чем в аппроксимационном коэффициенте для множества, максимизирующего гиперобъем. Однако, полученная граница для коэффициента аппроксимации является верхней. На рисунке ниже можно увидеть пример поведения данных значений для класса функций [math]f \in \mathbb{F}[/math], [math] f:[1, 100] \rightarrow [1, 100][/math].

Источники

1. Friedrich T., Bringmann K. - The Maximum Hypervolume Set Yields Near-optimal Approximation
2. Friedrich T., Bringmann K. - The Maximum Hypervolume Set Yields Near-optimal Approximation