§ 4. Другие методы сведения многомерных задач к задачам меньшей размерности

Иногда полезно рассмотреть следующую формальную процедуру сведения многомерных задач к одномерным.

Пусть ищется минимум А функции в области

Можно написать равенство

где

Минимум каждый раз берется по области определения минимизируемой Функции в соответствии с условиями (1). Таким образом, исходная задача минимизации функции m переменных свелась к минимизации функции одной переменной, каждое значение которой определяется минимизацией функции переменной. В свою очередь минимизацию функции сведем к минимизации фунции одной переменной, каждое значение которой определяется минимизацией функции от переменных, и т.д. Получим цепочку соотношений

Кажущейся простоте метода сопутствует его большая трудоемкость. Предположим, что каждая минимизация функций одной переменной потребует вычисления s значений минимизируемой функции. Тогда минимизация требует нахождения при s значениях параметра , т.е. вычислений значений функции . Это в свою очередь потребует вычисления значений и т.д. В конечном счете потребуется вычисление значений функции Ф. Уже при умеренных , например , такой объем вычислений окажется недопустимо большим. Однако при малых некоторые модификации рассматриваемой идеи оказываются полезными. Например, возможен такой вариант. Задаются начальным приближением . Реализуют указанный алгоритм при не очень большом значении s, например или . При этом значения функции вычисляются в точках некоторого параллелепипеда . Получаемую точку минимума принимают за следующее приближение; приближение находят аналогичным образом, но значения функции Ф вычисляются в точках параллелепипеда и т. д.

Рассмотрим еще один метод, общая структура которого похожа на структуру описанного выше.

Если линии уровня функции Ф похожи на сферы, то при применении методов спуска происходит быстрое смещение в направлении минимума (рис. 7.4.1). Однако практически более типичен случай, когда эти линии похожи на эллипсоиды с большим разбросом полуосей. Тогда при движении по градиенту смещение в направлении точки минимума будет довольно медленным (рис. 7.4.2).

Предположим, что оси этих «эллипсоидов» естественным образом разбиваются на две группы: первая группа состоит из осей одного порядка и относительно малых, вторая группа состоит из осей одного порядка и относительно больших.

При решении некоторых задач такого рода хорошо зарекомендовал себя следующий метод, называемый методом оврагов. Задаются какими-то приближениями и производят несколько шагов метода спуска, исходя из каждого из этих приближений. Будут получены приближения и .

Рис. 7.4.1

Рис. 7.4.2

Рис. 7.4.3

Рис. 7.4.4

Из рис. 7.4.3 видно, что эти приближения будут лежать в многообразии, расположенном в окрестности осей второй группы. Процесс итераций состоит в получении последовательных приближений , лежащих в окрестности этого многообразия. В случае приближение отыскивается следующим образом. Проведем через и прямую и найдем приближение к точке минимума на этой прямой. Таким образом, это приближение ищется в виде

Далее проводим несколько итераций исходя из и получаем приближение , также лежащее в овраге. В случае приближение иногда удобно отыскивать в виде

Из рис. 7.4.4 видно, что описанный способ оказывается эффективным и в Ряде случаев, когда линии уровня функции имеют более сложную структуру.

Решение системы уравнений

также формально сводится к последовательному решению уравнений с одним неизвестным. Рассмотрим систему уравнений

относительно неизвестных . Пусть — ее решение. Подставляя выражения в первое из уравнений (2), получим уравнение

относительно одной неизвестной .

Отыскание значений и решение уравнения (4) можно проводить численно. Выбирается какой-то метод решения (4) по значениям функции при каждом требуемом значении в результате решения (3) получаются значения , которые подставляются затем в правую часть (4). Для решения системы уравнений (3) при каждом значении применим тот же прием.

Пусть — решение системы уравнений

относительно неизвестных . Подставляя во второе уравнение системы, получим уравнение

При каждом это уравнение может быть разрешено относительно . Его решение , а также образуют решение системы (3). Систему (5) при каждых опять решаем, сводя к системе, где число неизвестных единицу меньше, и т.д.

Если для решения каждого вспомогательного уравнения с одной неизвестной потребуется s вычислений функций, то суммарно этот алгоритм потребует порядка вычислений правых частей уравнений системы.

По поводу реального применения этого алгоритма можно сказать все то же, что и по поводу применения описанного в начале параграфа метода минимизации.

Задача 1. Рассмотреть, во что переходит описанный метод в случае, когда система уравнений (2) линейная.