Курсовая работа: Программная модель поиска глобального минимума нелинейных "овражных" функций двух переменных

Будем рассматривать задачу безусловной минимизации, т.е. задачу минимизации целевой функции f на всем пространстве R. Сущность всех методов приближенного решения этой задачи состоит в построении последовательности точек х1, х2, х3, …, хk, …, монотонно уменьшающих значение целевой функции:

f(x0) >= f(x1) >= f(x3) >= … >= f(xk) >= … (1.3)

Такие методы (алгоритмы) называют методами спуска. При использовании этих методов применяют следующую схему.

Пусть на k-й итерации имеется точка хk. Тогда выбирают направление спуска pkÎR и длину шага вдоль этого направления ak > 0. Следующую точку последовательности вычисляют по формуле:

xk+1 = xk + ak*pk, k = 0, 1, 2, …

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

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

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

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

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

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

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

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

1.2.2 Градиентные методы

Ненулевой антиградиент - Ñf(x0) указывает направление, небольшое перемещение вдоль которого из х0 приводит к значению функции fменьшему, чем f(x0). Это замечательное свойство лежит в основе градиентных методов, согласно которых на k-й итерации полагают pk = - Ñf(xk), т.е.

xk+1 = xk - akÑf(xk), ak > 0, k = 0, 1, 2, … .

Эти методы отличаются друг от друга способом выбора величины шага ak. Достаточно малый шаг ak обеспечивает убывание целевой функции

f(xk+1) = f(xk – akÑf(xk)) < f(xk), (1.4)

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

На практике нередко в качестве величины шага выбирают некоторое а > 0, одинаковое для всех итераций. При этом если условие 1.4 (при ak =|a|) нарушится, то для текущей итерации величину а уменьшают до тех пор, пока указанное неравенство не станет выполнимым.

Часто величину ak рекомендуют выбирать так, чтобы имело место более жесткое условие убывания, чем 1.4:

f(xk) – f(xk – akÑf(xk)) >= eak || Ñf(xk) ||, (1.5)

где 0 < e <1 – некоторая фиксируемая константа. Здесь также сначала фиксируют некоторое ak = a > 0 (например, ak = 1), одинаковое для всех итераций, а затем при необходимости уменьшают его до тех пор, пока не будет выполнено неравенство 1.5.

При реализации градиентных методов в качестве критериев окончания счета используют условие вида || Ñf(xk) || <= e, где е > 0 –фиксированная точность вычислений.

Точный смысл сходимости градиентных методов раскрывает следующее утверждение.

Пусть функция f ограничена снизу, непрерывно дифференцируема на R и ее градиент Ñf(x) удовлетворяет условию Липшица:

|| Ñf(x) -Ñf(x’) || <= L || x – x’ || для всех x,x’ Î R,

где L >= 0 – некоторая фиксированная константа. Кроме того, пусть выбор величины шага ak производится на основе условия 1.5. Тогда, какова бы ни была начальная точка х0, оба градиентных метода приводят к построению последовательности {xk}, обладающей свойством lim || Ñf(xk) ||= 0. Если, кроме того, функция f дважды непрерывно дифференцируема и существует такие числа М >= m > 0 , что

m || y || ² <= (Ѳf(x)y,y) <= M || y || ² для всех x,y,