Метки

, , , , , , ,

Цитата из книги Н. З. Шора «Методы минимизации недифференцируемых функций и их приложения», К., «Наукова думка» 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} производим следующие действия.

  1. Определяем значение функции в k-й токе последовательности
    f(x_k) = \max\limits_{i \in \overline{1,m}} \phi_i(x_k) = \phi_{i^*} (x_k).
  2. Вычисляем обобщенный градиент функции f(x) в точке
    x_k g_f(x_k) = g_{\phi_{i^*}} (x_k).
  3. Находим обобщенный градиент \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.
  4. Определяем разность обобщенных градиентов r_k = \tilde g_k - \tilde g_{k-1}.
  5. Находим отношение норм векторов r_k и \tilde g_k
    \beta_k = \frac{\|r_k \|}{\|\tilde g_k \|},
    которое характеризует изменение направления обобщенного градиента в точке x_{k-1} относительно направления обобщенного градиента в точке x_k в растянутом пространстве.
  6. Сравниваем \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, т. е. при значительном изменении направления обобщенного градиента, переходим к выполнению следующих этапов.
  7. Определяем вектор \xi_{k+1}, в направлении которого будет производиться растяжение пространства, \xi_{k+1} = r_k / \| r_k \|.
  8. Находим оператор B_{k+1}, обратный оператору A_{k+1}, по формуле B_{k+1} = B_k R_{\frac{1}{\alpha}}(\xi_{k+1}).
  9. Определяем обобщенный градиент функции \psi_{k+1}(y) в точке y_k, соответствующей точке x_k, с учетом (k+1)-го оператора растяжения простанства
    \tilde g_{k+1} = B^*_{k+1}g_f(x_k);
    в направлении антиградиента осуществляется движение на данной итерации.
  10. Изменяем длину шага h_{k+1} = h_k q_2, где $ 0 < q_2 \le 1 $.
  11. Определяем очередную точку минимизирующей последовательности
    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-й итерации.
Реклама