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

| Категория реферата: Рефераты по математике
| Теги реферата: реферат на экологическую тему, оформление доклада
| Добавил(а) на сайт: Фетиния.

1) в точке xk выбирают направление спуска - Sk;

2) находят (k+1)-е приближение по формуле xk+1=xk-hkSk.

Направление Sk выбирают таким образом, чтобы обеспечить неравенство f(xk+1)’f(M2).
Проведем такую же минимизацию целевой функции по переменным x3, x4, . . . ,xn. Дойдя до переменной xn, снова вернемся к x1 и продолжим процесс. Эта процедура вполне оправдывает название метода. С ее помощью мы построим последовательность точек М0,М1,М2, . . . , которой соответствует монотонная последовательность значений функции f(M0) >’ f (M1)>’ f(M2) >’ Обрывая ее на некотором шаге k можно приближенно принять значение функции f(Mk) за ее наименьшее значение в рассматриваемой области.

Проведем такую же минимизацию целевой функции по переменным x3, x4,
. . . ,xn. Дойдя до переменной xn, снова вернемся к x1 и продолжим процесс.
Эта процедура вполне оправдывает название метода. С ее помощью мы построим последовательность точек М0,М1,М2, . . . , которой соответствует монотонная последовательность значений функции f(M0)>’ f(M1)>’ f(M2) >’ ... Обрывая ее на некотором шаге k можно приближенно принять значение функции f(Mk) за ее наименьшее значение в рассматриваемой области. Отметим , что данный метод сводит задачу поиска наименьшего значения функции нескольких переменных к многократному решению одномерных задач оптимизации. Если целевая функция f(x1, x2, ... ,xn) задана явной формулой и является дифференцируемой, то мы можем вычислить ее частные производные и использовать их для определения направления убывания функции по каждой переменной и поиска соответствующих одномерных минимумов.
В противном случае, когда явной формулы для целевой функции нет, одномерные задачи следует решать с помощью одномерных методов

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

В двумерном пространстве R2. Решение задачи (2) методом покоординатного спуска, иначе называемого методом Гаусса - Зейделя, производят по следующей общей схеме.

Выбирают произвольно начальную точку х(0) из области определения функции f(х). Приближения х(k) определяются соотношениями

(3): x(k+1)=x(k)+t(k)S(k) (k=0,1,2, ...), где вектор направления спуска s(k)- это единичный вектор, совпадающий с каким-либо координатным направлением (например, если S(k) параллелен х1, то S(k)= {1,0,0,...,0}, если он параллелен x2, то S(k)={0, 1, 0, . . . ,0} и т.д.) ; величина t(k) является решением задачи одномерной минимизации:

f(x(k)+ts(k)) [pic] min, t ?R1, (k=0,1,2, ...),

и может определяться, в частности, методом сканирования.

Детальная реализация общей схемы в двумерном случае R2 дает траекторий приближения к точке х* методом покоординатного спуска, состоящую из звеньев ломаной, соединяющих точки х(k), x1~(k) x(k+1) (k=0, 1, 2,) . При k=0, исходя из начальной точки х(0)=(x1(0),x2(0)), находят точку х~(0)=
(x1~(0),x2(0)), минимума функции одной переменной f(x1,x2(0)); при этом f(x~(0))