11.17.08

Решение нелинейных минимаксных задач с помощью r-алгоритмов

Рубрика: Math, memory tagged Шор, Math, mathematics, numerical methods, чисельні методи, численные методы, r-algorithm, r-алгоритм в 21:08 от Engraver

Цитата из книги Н. З. Шора «Методы минимизации недифференцируемых функций и их приложения», К., «Наукова думка» 1979.

Глава4, §5. Использование r-алгоритмов для решения нелинейных минимаксных задач.

Рассмотрим вопросы минимизации функций вида $f(x) = \max\limits_{1 \le i \le m} \phi_i(x)$ , где $\phi_i(x)$ — гладкие функции, $x \in E_n$ . Если $\phi_i(x)$ — выпуклые функции, $i = 1,\ldots, m$ , то в качестве обобщенного градиента можно брать субградиент $g_{\phi_{i^*}}(x)$ , где $i^*$ — индекс функции $\phi_{i^*}$ для которой $f(x) = \phi_{i^*}$ .

В связи с важностью минимаксных задач большое внимание в настоящее время уделяется разработке методов их решения. Ряд таких методов для определенных классов задач предложен в работах В. М. Демьянова, Б. Н. Пшеничного, Е. Г. Евтушенко и др.

В принципе задача отыскания минимакса может быть сведена к решению следующей задачи выпуклого программирования: найти $\min y$ при ограничениях $f_i(x) - y \le 0$ , $i = 1,2,\ldots,m$ .

Для решения этой задач могут быть использованы итеративные методы возможных направлений. Однако такой путь решения задач связан с опредленными вычислительными трудностями: во-первых, нахождение минимума при данных ограничениях методами возможных направлений связано с необходимостью решения на каждой итерации ряда воспомогательных задач линейного или квадратичного программирования; во-вторых, для обеспечения сходимости методов возможных направлений нужно использовать меры предосторожности против зигзагообразного движения; в-третьих, на каждом шаге метода возможных направлений нужно определять минимум по направлению — довольно трудоемкая процедура, так как приходится определять минимум негладкой функции в условиях, когда определение значения функции требует значительной вычислительной работы, и, наконец, скорость сходимости этих методов слабо изучена как теоретически, так и экспериментально.

Более простым с вычислительной точки знения является метод обобщенного градиентного спуска, который в принципе позволяет решать выпуклые минимаксные задачи. Однако скорость сходимости этого метода недостаточно высока, особенно при решении задач овражного типа, которые характерны при отыскании минимаксов. В этом случае минимум, как правило, достигается при равенстве значений нескольких функций, при чем их число в регулярном случае определяет размерность оврага, равную $(n - m_1 + 1)$ , где $m_1$ — число функций, на которых достигается минимаксное значение.

Ускорение сходимости метода обобщенного градиентного спуска может быть достигнуто за счет растяжения пространства в направлении обобщенного градиента или в направлении разности обобщенных градиентов, вычисленных в двух последовательных точках. При использовании обобщенного градиентного спуска с растяжением пространства определение минимизирующей последовательости связано с вычислением обобщенного градиента функции $f(x)$ в каждой точке последовательности и применением оператора растяжения пространства. Обычно при анализе эффективности вычислительных алогритмов предполагается, что вычисление градиента функции $n$ переменных требует примеро столько же времени, сколько $(n+1)$ -кратное вычисление функции. Если считать, что каждая из функций $\phi_i(x)$ непрерывно дифференцируема, затраты на ее вычисление не зависят от индекса $i$ , а сложность вычисления градиента в $(n+1)$ раз превосходят сложность вычисления функции, то сложность вычисления функции $f(x)$ будет составлять $\left( \dfrac{m}{1+n} \right)$ -ю часть сложности вычисления ее субградиента. Таким образом, с ростом $m$ уменьшяется относительная сложность вычисления субградиента $g_f(x)$ по сравнению со сложностью вычисления функции $f(x)$ . Поэтоу для обеспечения высокой эффективности разрабатываемых алогритмов решения минимаксных задач нужно особенно стремиться к упрощению процедур нахождения минимума по направлению, связанных с вычислением значений функции максимума. Исходя из этого, Л. П. Шабашова и автор предложили и экспериментально исследовали несколько модификаций r-алоритмов решения минимаксных задач, различающихся способом регулировки шагового множителя и точностью поиска минимума по направлению.

Рассмотрим одну из модификаций. Движение начинаем из произвольной точки $x_0 \in E_n$ . При этом полагаем $\tilde g_0 = 0 \in E_n$ , $B_0 = I_n$ , где $I_n$ — единичная матрица размерности $n\times n$ . Предположим, что выполнено $k$ итераций ( $k = 1,2,\ldots$ ), в результате чего определены точки $x_1,x_2,\ldots,x_k$ , а так же вектор $\tilde g_k$ и матрица $B_k$ . Для определения точки $x_{k+1}$ производим следующие действия.

Определяем значение функции в $k$ -й токе последовательности
$f(x_k) = \max\limits_{i \in \overline{1,m}} \phi_i(x_k) = \phi_{i^*} (x_k).$
Вычисляем обобщенный градиент функции $f(x)$ в точке
$x_k$ $g_f(x_k) = g_{\phi_{i^*}} (x_k).$
Находим обобщенный градиент $\tilde g_k$ функции $\psi_k(y)$ в точке $y_k$ в преобразованном пространстве по формуле
$\tilde g_k = g_{\psi_k} (y_k) = B^*_k g_f(x_k),$
где
$\psi_k(y) = f(A^{-1}_ky) = f(B_ky);$
$A_k$ — оператор преобразования пространства; $B_k$ — оператор, обратный оператору $A_k$ ; $B_k^*$ — оператор, сопряженный оператору $B_k$ .
Определяем разность обобщенных градиентов $r_k = \tilde g_k - \tilde g_{k-1}$ .
Находим отношение норм векторов $r_k$ и $\tilde g_k$
$\beta_k = \frac{\|r_k \|}{\|\tilde g_k \|},$
которое характеризует изменение направления обобщенного градиента в точке $x_{k-1}$ относительно направления обобщенного градиента в точке $x_k$ в растянутом пространстве.
Сравниваем $\beta_k$ с заданной величиной $q_1$ : а) если $\beta_k \le q_1$ , то определяем следующую точку минимизирующей последовательности
$x_{k+1} = x_k - h_k B_k \frac{\tilde g_k}{\| \tilde g_k \|},$
соответствующую перемещению в растянутом пространстве точки $y$ в том же направлении и с той же величиной шага, что и на $k$ -й итерации, после чего переходим к выполнению $(k+2)$ -й итерации; б) если $\beta_k > q_1$ , т. е. при значительном изменении направления обобщенного градиента, переходим к выполнению следующих этапов.
Определяем вектор $\xi_{k+1}$ , в направлении которого будет производиться растяжение пространства, $\xi_{k+1} = r_k / \| r_k \|$ .
Находим оператор $B_{k+1}$ , обратный оператору $A_{k+1}$ , по формуле $B_{k+1} = B_k R_{\frac{1}{\alpha}}(\xi_{k+1})$ .
Определяем обобщенный градиент функции $\psi_{k+1}(y)$ в точке $y_k$ , соответствующей точке $x_k$ , с учетом $(k+1)$ -го оператора растяжения простанства
$\tilde g_{k+1} = B^*_{k+1}g_f(x_k);$
в направлении антиградиента осуществляется движение на данной итерации.
Изменяем длину шага $h_{k+1} = h_k q_2$ , где $ 0 < q_2 \le 1 $.
Определяем очередную точку минимизирующей последовательности
$x_{k+1} = x_k - h_{k+1} B_{k+1} \frac{\tilde g_{k+1}}{\| \tilde g_{k+1} \|},$
которая соответствует точке перемещения в растянутом пространстве в направлении $- \frac{\tilde g_{k+1}}{\| \tilde g_{k+1} \|}$ на величину $h_{k+1}$ из точки $y_k = A_kx_k$ . После этого переходим к выполнению $k+2$ -й итерации.