2.2. Выбор длины шага

Пусть известна точка . Необходимо найти координаты точки

для этого сделаем шаг в направлении и определим его величину.

Основная задача при выборе - обеспечить выполнение неравенства.

При выборе шага обычно используют способ удвоения или методы

одномерной минимизации, описанные выше.

Способ удвоения состоит в следующем:

Выбирают . Если при этом , то либо

переходят к следующей ()-й итерации, либо выбирают .

Если значение функции меньше предыдущего, то процесс удвоения можно

продолжать до тех пор, пока убывание не прекратиться.

Если при значение функции, т.е. , то выбирают . Уменьшение значения

функции позволяет вести дальнейший поиск. Увеличение требует нового

изменения и т.д.

Выбор длины шага методами одномерной минимизации основан

на поиске минимума функции .

Часто для этой цели используется метод квадратичной интерполяции,

алгоритм, которого можно представить следующими этапами.

1) В заданной точке принимают . Выбирают длину шага такой,

чтобы . В качестве третьей точки берут значение .

2) Вычисляют три значения .

3) Находят коэффициенты параболы , проходящей через три выбранные

узла интерполяции, из уравнений

4) Функция будет иметь минимум в точке

Вычисляют положение экстремума .

5) Проверяют выполнение условия . Если оно не выполняется, то

, и вычисления повторяются с пункта 1.

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

Кроме метода квадратичной интерполяции для выбора шага

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

сканирования и т.д.

Величину шага можно выбирать также из условия минимума

функции , т.е. из условия . При этом

где - некоторая константа или определитель

для точки .

Условие связано с величиной косинуса угла

между направлением вектора градиента и направлением

движения из этой же точки:

2.3. Выбор направления поиска

Методы безусловной минимизации различаются выбором направления

поиска, но всегда направление выбирают таким, чтобы значение

целевой функции уменьшалось, т.е. чтобы выполнялось условие .

2.3.1. Безградиентные методы. Покоординатный спуск.

Наиболее простым способом определения направления спуска

является выбор в качестве одного из координатных векторов.

Это позволяет поочередно изменять все независимые переменные так,

чтобы на каждой из них достигалось наименьшее значение целевой функции.

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

произвольно и не меняется в процессе поиска. В результате

многомерный поиск заменяется последовательностью одномерных поисков

с любой стратегией минимизации функции одной переменной

(см. методы, описанные выше).

Данный метод эффективен в случае единственного минимума функции.

Для уменьшения числа вычислений величину шага меняют при каждом

переходе от поиска минимума по одной переменной к поиску минимума

по другой переменной.

Алгоритм метода может быть представлен следующими этапами.

1. Задают исходную точку поиска .

2. Определяют направление поиска; если варьируется переменная

3. Делают первый шаг в направлении.

Значение выбирают способом удвоения или минимизацией

функции по. Если аналитическое выражение целевой функции достаточно простое,

для выбора можно использовать условие .

4. После определения положения минимума по координате делают

шаг в направлении

Значение находят, минимизируя функцию, и так далее.

5. Поиск заканчивают при выполнении условия

Пример

Пусть целевая функция имеет вид

Требуется найти её минимум с точностью.

Решение.

1. Примем в качестве исходной точки. Значение целевой функции в этой точки

2. Направление поиска выберем параллельно координатной оси

3. Изменим переменную.

Значение найдём из условия

Итак, нашли точку, в которой значение целевой функции

4. Изменим переменную

Значение найдём из условия

Тогда

Нашли точку

5. От точки вновь изменим направление поиска и сведём дальнейшие вычисления в таблицу 4.

После четвертой итерации выполняется условие окончания поиска:

Ответ: минимум целевой функции находится в точке

Отметим, что точный минимум целевой функции находится в точке

Рассмотрим на другом примере покоординатный спуск с использованием для выбора величин шага способа удвоения. Соответствующая блок-схема представлена на рис.9.

Пусть требуется минимизировать функцию, начиная с точки .

1. Изменим переменную

Найдем, применяя способ удвоения.

Блок-схема метода покоординатного спуска с удвоением шага.

Выберем произвольное значение

Тогда

Удвоим шаг:

При этом

Ещё раз удвоим шаг:

Тогда

Уменьшение целевой функции позволяет ещё удвоить шаг:

При этом

Функция не уменьшилась. Следовательно, наилучшее значение. Точка , найденная с таким значением , имеет координаты .

2. Ещё раз изменим переменную

Примем

Тогда

Функция не уменьшилась. Уменьшим шаг вдвое:

При этом

3. Сделаем шаг по переменной

Примем

Тогда

4. Ещё раз изменим переменную

где

Тогда

5. Ещё раз изменим переменную с таким же значением

6. Следующий шаг по с тем же параметром приводит к возрастанию функции:

Следовательно, функция является точкой минимума целевой функции.

2.3.2. Градиентные методы.

Градиентные методы связаны с поиском по направлению градиента или антиградиента оптимизируемой функции.

Градиент функции обозначается и определяется как вектор-столбец из первых частных производных этой функции:

В каждой точке градиент ортогонален линии уровня

, проходящей через эту точку, и направлен в сторону наискорейшего возрастания функции.

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

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

где - некоторые малые приращения аргументов.

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

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

Числа выбираются согласно 2.2. В частности, можно для определения -ом шаге использовать косинус угла (между последовательными векторами переходов в процесс спуска от точки к точке

Тогда

В качестве и можно принять, например, углы в, соответственно.

Модификации градиентных методов

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

Рассмотрим две модификации - наискорейший спуск и метод сопряженных направлений.

2.3.2.1. Метод наискорейшего спуска.

При, т.е. когда является единичный матрицей, алгоритм записывается как

Здесь индекс “i” характеризует номер составляющей вектора, индекс определяет номер итерации поиска, определяется из условия минимума функции или по формуле.

Алгоритм такого метода, называемого методом наискорейшего спуска, можно представить следующими этапами.

1. Задают исходную точку

Оценивают направление поиска путем вычисления частных производных в точке

2. Делают переход от точки к точке по формуле

3. Вновь определяют направление спуска, вычисляя частные производные в полученной точке

4. Делают переход к точке

И так далее

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

5. Поиск заканчивают, если

или

где - малая положительная величина.

Пример

Требуется минимизировать функцию, начиная с точки, с точностью

Решение.

1. Определим направление поиска, вычисляя производные в заданной точке:

2. Выберем из условия

Пусть, тогда точка имеет координаты

При этом

Следовательно, необходимо уменьшить.

Примем, тогда

При этом

3. Сделаем переход в точку, корректируя по формулам

Поскольку, в соответствии с примем. Тогда

4. Вновь определим направление поиска, вычисляя производные в точке, скорректируем, и все дальнейшие итерации сведём в таблицу 5.

На шестнадцатой итерации выполняется условие окончания поиска

Ответ: минимум целевой функции находится в точке

Графическая иллюстрация данного примера приведена на рис.11.

Строим линии уровня целевой функции. Задавая некоторые постоянные значения функции, получаем каноническое уравнение эллипса:

при; при

и так далее.

2.3.2.2. Метод сопряженных напряжений

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

Алгоритм метода выражается следующими расчетными формулами:

Здесь - весовые коэффициенты, одним из способов, определения которых служит формула

Ниже приводятся этапы этого алгоритма.

1. В исходной точке вычисляют градиент как начальное направление поиска, т.е.

2. По формуле (25) находят точку с координатами, минимизируя функцию по с помощью методов одномерного поиска.

3. Вычисляют в точке значение функции и значение градиента

4. Определяют новое направление поиска из соотношения

и так далее.

5. Поиск заканчивают при выполнении условия

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

Пример.

Требуется минимизировать функцию, начиная сточки. Принять = 0,5.

1. Вычисляем частные производные целевой функции в исходной точке, тем самым, задавая начальное направление поиска:

2. Длину шага определяем по формуле (13)

Находим координаты точки:

3. Вычисляем значения:

4. Определяем новое направление поиска

5. Оцениваем длину шага

Точка имеет координаты

И так далее. На рис. 13 изображена траектория поиска, результаты расчетов сведены в таблицу 6.

На пятой итерации выполняется условие окончания поиска:

Ответ: минимум целевой функции находится в точке

2.4. Задания

Найти минимум (максимум) функции с точностью

3. МНОГОМЕРНЫЙ ПОИСК. НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ. МЕТОДЫ УСЛОВНОЙ МИНИМИЗАЦИИ [1,2,6-8]

3.1. Метод сканирования

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

Точность метода определяется частотой расположения выбранных точек на данной области изменения переменных.

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

1. Исследуется функция цели вдоль одного выбранного направления (вдоль одной из координатных осей) с шагом. В каждой точке вычисляется и запоминается значение целевой функции.

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

Графическая иллюстрация поиска минимума для случая двух переменных дана на рис.14.

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

Если имеются ограничения на независимые переменные, то точки, которые не удовлетворяют уравнениям (или неравенствам) ограничений, исключаются из рассмотрения.

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

где n - число переменных.

Недостаток метода: велико число вычислений, которое резко возрастает (в показательной степени) в зависимости от размерности решаемой задачи.

Преимущества метода: простота алгоритма, возможность определения глобального минимума.

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