Оглавление:

Введение . 2

1. Общая схема методов спуска . 3

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

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

3.1 Обзор градиентных методов 7

3.2 Ограничения, накладываемые на функцию . 9

3.3 "Овражный" характер функции . 10

Список литературы 15

Введение

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

Эта задача записывается следующим образом

(1)

Задача (1) называется задачей без ограничений или задачей безусловной оптимизации, если и задачей с ограничениями или задачей условной оптимизации, если .

Решить задачу (1) означает найти точку (а также соответствующее значение ) такую, что () или установить неразрешимость этой задачи. Решение называют оптимальным, а значение - оптимумом функции на множестве .

Задачи , и , называют соответственно задачей минимизации и максимизации функции на множестве .

Отметим, что задачу максимизации функции можно свести к задаче минимизации, заметив, что на .

Рассмотрим задачу безусловной минимизации

. (2)

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

удовлетворяющих условию

(4)

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

1. Общая схема методов спуска

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

При построении последовательностей (3)-(4) применяют следующую схему. Пусть на -й итерации имеется точка . Тогда выбирают направление спуска и длину шага вдоль этого направления . Следующую точку последовательности определяют по формуле

,

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

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

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

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

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