Реферат: Минимизация функций нескольких переменных. Метод спуска

2. если ; если

3. , если ; , если; ,если ,

где –угол между градиентами на предыдущем и текущем шаге;

и – заданные пороговые значения выбираются субъективно

(например, ).

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

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

Пусть нужно найти наименьшее значение целевой функции

u=f(M)=f(x ₁ , x ₂ , . . . ,x_n ). Здесь через М обозначена точка n-мерного пространства с координатами x ₁ , x ₂ , . . . ,x_n : M=(x ₁ , x ₂ , . . . ,x_n ). Выберем какую-нибудь начальную точку М ₀ = (x ₁ ⁰ , x ₂ ⁰ , . . . ,x_n ⁰ ) и рассмотрим функцию f при фиксированных значениях всех переменных, кроме первой: f(x ₁ , x ₂ ⁰ ,x ₃ ⁰ , . . . ,x_n ⁰ ). Тогда она превратится в функцию одной переменной x ₁ . Изменяя эту переменную, будем двигаться от начальной точки x ₁ =x ₁ ⁰ в сторону убывания функции, пока не дойдем до ее минимума при x ₁ =x ₁ ¹ , после которого она начинает возрастать. Точку с координатами ( x ₁ ¹ , x ₂ ⁰ ,x ₃ ⁰ , . . . ,x_n ⁰ ) обозначим через М ₁ , при

этом f(M₀ ) >= f(M ₁ ).

Фиксируем теперь переменные: x ₁ =x ₁ ¹ , x ₃ = x ₃ ⁰ , . . . ,x_n =x_n ⁰ и рассмотрим функцию f как функцию одной переменной x ₂ : f(x ₁ ¹ , x ₂ ² , x ₃ ⁰ . . . ,x_n ⁰ ). Изменяя x ₂ , будем опять двигаться от начального значения x₂ =x₂ ⁰ в сторону убывания функции, пока не дойдем до минимума при x₂ =x₂ ¹ .Точку с координатами

{x ₁ ¹ , x ₂ ¹ , x ₃ ⁰ . . . x_n ⁰ } обозначим через М ₂ , при этом f(M₁ ) >=f(M ₂ ).

Проведем такую же минимизацию целевой функции по переменным

x ₃ , x ₄ , . . . ,x_n . Дойдя до переменной x_n , снова вернемся к x ₁ и продолжим процесс. Эта процедура вполне оправдывает название метода. С ее помощью мы построим последовательность точек М ₀ ,М ₁ ,М ₂ , . . . , которой соответствует монотонная последовательность значений функции

f(M₀ ) >= f (M ₁ ) >= f(M ₂ ) >= Обрывая ее на некотором шаге k можно приближенно принять значение функции f(M_k ) за ее наименьшее значение в рассматриваемой области.

Проведем такую же минимизацию целевой функции по переменным x ₃ , x ₄ , . . . ,x_n . Дойдя до переменной x_n , снова вернемся к x ₁ и продолжим процесс. Эта процедура вполне оправдывает название метода. С ее помощью мы построим последовательность точек М ₀ ,М ₁ ,М ₂ , . . . , которой соответствует монотонная последовательность значений функции

f(M₀ ) >= f(M ₁ ) >= f(M ₂ ) >= ... Обрывая ее на некотором шаге k можно приближенно принять значение функции f(M_k ) за ее наименьшее значение в рассматриваемой области. Отметим , что данный метод сводит задачу поиска наименьшего значения функции нескольких переменных к многократному решению одномерных задач оптимизации. Если целевая функция f(x ₁ , x ₂ , ... ,x_n ) задана явной формулой и является дифференцируемой, то мы можем вычислить ее частные производные и использовать их для определения направления убывания функциипо каждой переменной и поиска соответствующих одномерных минимумов. В противном случае, когда явной формулы для целевой функции нет, одномерные задачи следует решать с помощью одномерных методов

На рис.изображены линии уровня некоторой функции двух переменных u= f (х, у). Вдоль этих линий функция сохраняет постоянные значения, равные 1, 3, 5, 7, 9. Показана траектория поиска ее наименьшего значения, которое достигается в точке О, с помощью метода покоординатного спуска. При этом нужно ясно понимать, что рисунок служит только для иллюстрации метода.

Пусть требуется решить задачу (2):

f(x) min, х ÎRⁿ . (2)

В двумерном пространстве R² .Решение задачи (2) методом покоординатного спуска, иначе называемого методом Гаусса - Зейделя , производят по следующей общей схеме.
Выбирают произвольно начальную точку х⁽⁰⁾ из области определения функции f(х). Приближения х^(k) определяются соотношениями

(3): x^(k+1) =x^(k) +t^(k) S^(k) (k=0,1,2, ...),

где вектор направления спуска s^(k) - это единичный вектор, совпадающий с каким-либо координатным направлением (например, если S^(k) параллелен х₁ , то S^(k) = {1,0,0,...,0}, если он параллелен x₂ , то S^(k) ={0, 1, 0, . . . ,0} и т.д.) ; величина t^(k) является решением задачи одномерной минимизации:
f(x^(k) +ts^(k) ) min, t ÎR¹ , (k=0,1,2, ...),
и может определяться, в частности, методом сканирования.
Детальная реализация общей схемы в двумерном случае R² дает траекторий приближения к точке х* методом покоординатного спуска, состоящую из звеньев ломаной, соединяющих точки х^(k) , x₁ ~^(k) x^(k+1) (k=0, 1, 2,) . При k=0, исходя из начальной точки х⁽⁰⁾ =( x₁ ⁽⁰⁾ ,x₂ ⁽⁰⁾ ) , находят точку х~⁽⁰⁾ = (x₁ ~⁽⁰⁾ ,x₂ ⁽⁰⁾ ), минимума функции одной переменной f(x₁ ,x₂ ⁽⁰⁾ ); при этом f(x~⁽⁰⁾ )<=f(x⁽⁰⁾ ).Затем находят точку минимума x⁽¹⁾ функции f (x₁ ~⁽⁰⁾ ,x₂ ) по второй координате. Далее делают следующий шаг вычислений при k=1. Полагают, что исходной точкой расчета является х⁽¹⁾ . Фиксируя вторую координату точки х⁽¹⁾ , находят точку минимума х~⁽¹⁾ = (x₁ ~⁽¹⁾ ,x₂ ⁽¹⁾ ), функции f(x₁ ,x₂ ⁽¹⁾ ) одной переменной x⁽¹⁾ ; при этом f(x~⁽¹⁾ )<=f(x⁽¹⁾ )<=f(x⁽⁰⁾ ). Точку х⁽²⁾ получают, минимизируя целевую функцию f(x₁ ~⁽¹⁾ ,x₂ ), вновь по коорданате х₂ , фиксируя координату x₁ ~⁽¹⁾ ,точки x⁽¹⁾ , и т.д.
Условием прекращения вычислительной процедуры при достижении заданной точности e может служить неравенство
||x^(k+1) - x^(k) ||<e (4)

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

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

Рассмотрим функцию f, считая для определенности, что она зависит от трех переменныхx,y,z. Вычислим ее частные производные дf/дх, дf/ду, дf/дz и образуем с их помощью вектор, который называют градиентом функции:

grad f(x, у, z ) = дf (х, у,z)/дх*i +дf( x, у, z)/ду*j +дf(x, y,z)/дг*k .

Здесь i , j, k - единичные векторы, параллельные координатным осям. Частные производные характеризуют изменение функции f по каждой независимой переменной в отдельности. Образованный с их помощью вектор градиента дает общее представление о поведении функции в окрестности точки (х, у,z). Направление этого вектора является направлением наиболее быстрого возрастания функции в данной точке. Противоположное ему направление, которое часто называют антиградиентным, представляет собой направление наиболее быстрого убывания функции. Модуль градиента
______________________
|grad (х, у,z) | =Ö (дf/дх (х, у,z))² +(дf/ду( x, у, z))² +(дf/дг(x, y,z))² .

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