8.2. Метод координатного спуска

Рассмотрим алгоритм поиска минимума многомерной функции на примере функции двух переменных График функции в области ее минимума представим в параметрическом виде, подобно изображению рельефа местности на географических картах, соединяя линиями точки на координатной плоскости где функция принимает одинаковые значения (рис. 8.5).

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

Алгоритм координатного спуска заключается в сведении многомерной задачи к последовательным одномерным задачам, которые решаются методами минимизации функции одной переменной, и в частности, методом золотого сечения. Вначале в прямоугольной области (8.4) зафиксируем координату тогда функция будет зависеть только от одной переменной Найдем минимум функции изменяя координату по методу золотого сечения. На рис. 8.5 найденный минимум располагается в точке Затем зафиксируем первый аргумент и найдем минимум функции относительно второго аргумента (точка на рис. 8.5). Аналогичным способом перейдем последовательно к точкам и т.д.

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

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

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

Рис. 8.5. Рельеф функции

Рис. 8.6. Блок-схема программы минимизации функции многих переменных методом координатного спуска

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

Программы 8.2 имеют блочную структуру в соответствии с рис. 8.6.

В основном блоке программы в строке 10 описаны одномерные массивы: - для размещения аргументов многомерной функции; - для границ области поиска минимума по каждой координате; для координат начальной точки поиска. Размерность этих массивов выбирается исходя из максимально допустимой размерности минимизируемой функции. В диалоговом режиме (строка 20) задаются значения следующих переменных: размерность функции; допустимая погрешность в определении координат минимума; допустимая погрешность определения минимума одномерной функции методом золотого сечения. В цикле по переменной I в строках 30-40 задаются интервал поиска и начальное значение по каждой координате. После обращения к подпрограмме метода координатного спуска на дисплей выводятся координаты минимума и значение функции в точке минимума (строки 60-80).

Подпрограмма метода координатного спуска составлена для произвольной размерности минимизируемой функции. С помощью оператора цикла в строке 100 значения координат начальной точки поиска пересылаются в массив для аргументов функции. Так как минимизация начинается с вариации первого аргумента задаваемого подпрограммой метода золотого сечения, то инициализация массива начинается со второго элемента В строке 110 инициализируется переменная используемая в программной реализации условий (8.5). В предлагаемом варианте программы выбрана одинаковая погрешность определения минимума по каждой координате и итерационный цикл косодинатного спуска повторяется, когда хотя бы по одной из координат погрешность превышает заданное значение В цикле в строках 120-140 методом золотого сечения находятся последовательно минимумы по каждой координате. Перед обращением к подпрограмме метода золотого сечения задаются границы поиска (переменные . Найденное значение минимума сравнивается с его значением на предыдущей итерации, и затем запоминается в массиве

Подпрограмма метода золотого сечения взята из программы и записана в строках 200-290.

Первый оператор (строка 300) подпрограммы минимизируемой функции формирует значение координаты по которой осуществляется поиск однокоординатного минимума Значение переменной X передается из подпрограммы метода золотого сечения.

В качестве примера находится минимум функции двух переменных [18]

Программа вычисления этой функции записана в строке 310.

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

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

Значения границ изменения аргумента, по которому идет минимизация, передаются в подпрограмму метода золотого сечения как фактические параметры при обращении к подпрограмме В программе на Бейсике для решения такой задачи использованы операции присваивания значений границ переменным

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

Приведем протокол выполнения программы

(см. скан)

(см. скан)

(см. скан)