Алгоритм решения задачи методом наискорейшего спуска

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

, , .

1. Выбирается начальная точка поиска .

2. Определяется значение целевой функции в начальной точке .

3. В исходной точке вычисляется градиент целевой функции (2.4).

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

4. В направлении антиградиента делается шаг спуска

.

5. Рассчитывается значение целевой функции в точке

.

6. Сравниваются значения целевой функции в точке и начальной точке поиска .

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

Если же , то необходимо изменить начальную точку поиска , либо уменьшить величину рабочего шага .

7. Затем делается новый шаг в том же направлении и так до тех пор, пока не будет найден минимум в этом направлении.

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

8. Критерием окончания поиска является выполнение условия

,

которое проверяется после каждого удачного шага.

Блок-схема алгоритма решения задачи методом наискорейшего спуска

Безградиентные методы детерминированного поиска

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

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

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

К безградиентным методам детерминированного поиска относятся: метод локализации экстремума функции, метод «золотого сечения», метод поиска с использованием чисел Фибоначчи, метод Гаусса-Зейделя, метод сканирования [1]. Рассмотрим один из этих методов – метод сканирования.

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

Метод сканирования заключается в последовательном просмотре значений критерия оптимальности в ряде точек, принадлежащих области изменения независимых переменных, и нахождении среди этих точек такой, в которой критерий оптимальности имеет минимальное (максимальное) значение. Точность метода определяется тем, насколько “густо” располагаются выбранные точки в допустимой области изменения независимых переменных.

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

Другое достоинство – независимость от вида оптимизируемой функции.

К недостаткам метода относится необходимость вычисления критерия для большого числа точек. Последнее обстоятельство существенно ограничивает возможности использования метода сканирования.

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

Для сокращения объема вычислений используется алгоритм с переменным шагом сканирования.