Two-step

В новых местах15 вычисляются значения минимизируемой функции. Туда, где функция имеет минимальное значение, делается переход, данная точка становится новой точкой приближения к минимуму, а все вышеописанные действия ("ощупывание" функции вблизи точки приближения16) повторяются. Если окажется, что вблизи новой точки приближения все новые значения функции увеличиваются, то шаг поиска (d) уменьшается вдвое, а все действия повторяются. Поиск заканчивается, когда значение d становится меньше tol (системная переменная Mathcad, регулирующая точность вычислений).

Функция Min2step протестирована на довольно сложной функции двух аргументов, которая в области х [-2, 2] и у [-3, 3] имеет три минимума и два максимума (см. рис. 3.33, где эта функция показана в аксонометрии). На рис. 3.27 изображен путь к этим минимумам от трех различных точек приближения.

Примечание

Рис. 3.27 — это некий коллаж: в один рисунок сведены три разных — три трассировки к трем минимумам от трех начальных точек.

Алгоритм функции Min2step, конечно, намного примитивнее алгоритмов встроенных в Mathcad средств поиска минимума. Но бесспорное преимущество функции Min2step перед встроенными в том, что она возвращает "историю" работы — трассировку пути к решению.

На рис. 3.28 показано окно браузера Интернета с открытым сайтом метода "Два шага" (Two-step), где читатель может протестировать другие начальные точки и иные анализируемые функции.

Алгоритм спуска к минимуму, заложенный в программу на рис. 3.26,— простой и без всяких оптимизирующих хитростей. Так, например, при очередном приближении к минимуму лишний раз рассчитывается значение анализируемой функции в предыдущей точке. Если анализируемая функция имеет мало аргументов и сама по себе простая, а ее значение высчитывается быстро, то это повторение мало влияет на общее время поиска минимума. Но что будет, если функция достаточно сложная? Предлагаем читателям доработать программу на рис. 3.26 и исправить отмеченный недостаток.

Рис. 3.28. Шагаем в самую глубокую пропасть

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

Более оптимальная стратегия может требовать "охвата" очередной точки не крестом, а равносторонним треугольником со стороной d (симплекс-метод; при минимизации функции трех переменных точка помещается внутри тетраэдра и т. д.).

Кроме того, неплохо треугольник (либо звезду Давида или даже пятиконечную звезду — новое задание читателю) при каждом шаге приближения к минимуму ориентировать в пространстве случайным образом, растягивать его вдоль одной из вершин. Этим также можно добиться более оптимальной стратегии поиска минимума.

Описанные ухищрения можно перенести и на задачу с п переменными оптимизации (n-мерная иудейская или пятиконечная звезда!). Все это будет хорошим заданием читателям. Поиск и испытание алгоритмов оптимизации относится к одному из разделов вычислительной (прикладной) математики. В данной книге мы только чуть-чуть заглянули в него.

Читатель может отметить еще одну "неоптимальность" программы на рис. 3.26. Она генерирует не только вектор значений переменных, где функция минимальна, но и целую матрицу м с "историей" поиска. Но перегрузка программы на рис. 3.26 не была напрасна. Программирование в среде Mathcad до 13-й версии было лишено средств отладки. Простейшее, но, тем не менее, очень эффективное средство отладки программ — наблюдение за промежуточными результатами. А как раз это в среде Mathcad делать невозможно. И все же— если нельзя, но очень хочется, то можно. Программа, приведенная на рис. 3.26, успешно справляется с довольно-таки сложными задачами. Но если ей подсунуть совсем уж простую функцию — тестовую функцию Розенброка, например, то при определенных начальных приближениях программа на рис. 3.26 зациклится— ответа от нее не дождешься. В чем тут дело? Ответить на этот вопрос поможет некоторая модернизация программы: прервать ее работу можно не только по условию d<tol, но и по дополнительному условию, например, n>30. После того как число шагов приближения п превысит 30, можно будет просмотреть след поиска минимума функции Розенброка или иной другой (задание читателю).

На рис. 3.28 видно, что след поиска минимума закручивается у точки минимума. В чем тут дело?!

Наполните ванну водой, бросьте туда перышко или какой-нибудь другой легкий предмет и выдерните пробку. Перышко сначала будет более-менее спокойно двигаться к отверстию, а затем закрутится в водовороте (см. рис. 3.28). Наш метод поиска минимума можно назвать не просто методом наискорейшего спуска, а методом наискорейшего спуска воды. Жидкость не просто спускается водоворотом, она всегда вращается в одну сторону. Если даже раскрутить ее в противоположном направлении, то, преодолев насилие, она снова потечет по часовой стрелке. Говорят, что это физическое явление через силы Кориолиса связано с вращением Земли: на экваторе вода в ванне не закручивается, но севернее или южнее экватора она приобретает "правый" (как на рис. 3.28) или "левый" уклон. Автор проверил эту гипотезу: он переслал по e-mail файл с задачей коллеге в Австралию. Все подтвердилось: линии траектории спуска стали закручиваться в другую сторону— против часовой стрелки. Интересно, как они себя поведут на Северном или на Южном полюсах? С водой там все ясно, она вообще не будет течь — замерзнет. А вот что будет с кривыми? К сожалению, у автора нет коллег в Арктике и Антарктике.

Читатель, наверное, уже догадался, что его разыгрывают— этот материал был опубликован в апрельском выпуске одного компьютерного журнала17.

Но самое смешное в этой истории то, что траектории спуска, показанные на рис. 3.28, в Австралии на самом деле стали закручиваться в другую сторону. Все объяснилось довольно просто: при передаче данных на линии произошел маленький сбой и в программе на рис. 3.26 вместо строки

for i ORIGIN..L

появилась строка

for i L...ORIGIN

Вот и все объяснение. Но виноваты в этом все те же силы Кориолиса — магнитные диски винчестеров на серверах и маршрутизаторах Южного полушария вращаются несколько иначе, чем на Северном полушарии. Отсюда и сбои, выявить которые довольно сложно, т. к. при контрольной обратной пересылке файла ошибка исправляется по принципу "минус на минус дает плюс"18.

В среде Mathcad 13/14 появилась возможность трассировки и встроенных функций оптимизации (рис. 3.29).

Рис. 3.29. Трассировка встроенной функции minimize