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

Министерство  путей сообщения  РФ

Дальневосточный государственный  университет

путей сообщения 
 
 
 

Кафедра «Прикладная математика»

    Курсовая  работа

по  численным методам 

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

Метод спуска.» 
 
 
 

Выполнили: Косолапов А.Г.  Терехов А.А.

                          Проверил: Смагин  С.И. 
 
 
 
 
 
 
 
 
 
 
 
 
 

Хабаровск 2003 
 
 
 
 
 

Содержание: 

1. Методы  спуска (Общая схема) _________________________ 3
2. Метод покоординатного спуска._____________________ 4

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

4. Метод наискорейшего спуска.______________________________  9
5. Описание программы._____________________________________10

6. Общая блок схема.________________________________________ 11

7. Руководство для пользования.______________________________12

8. Приложение  А  (Листинг программы)__________________________13

     IX.      Приложение B

    (Исследование  функции U=A*x1^3+B*x2^2-C*x1-D*x2 (изменение шага))_____ 25 
 

  

                                            

                                            

                                              
Методы спуска

                                                 Общая схема

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

    Решается  задача минимизации функции j(x) на всём пространстве E_n. Методы спуска состоят в следующей процедуре построения последовательности {x_k}. В качестве начального приближения выбирается любая точка x₀ÎE_n. Последовательные приближения x₁, x₂, … строятся по следующей схеме:

1. в точке x_k выбирают направление спуска - S_k;
2. находят (k+1)-е приближение по формуле x_k+1=x_k-h_kS_k.

    Направление S_k выбирают таким образом, чтобы обеспечить неравенство f(x_k+1)<f(x_k) по крайней мере для малых значений величины h_k. На вопрос, какому из способов выбора направления спуска следует отдать предпочтение при решении конкретной задачи, однозначного ответа нет.

    Число h_k определяет расстояние от точки x_k до точки х_k+1. Это число называется длиной шага или просто шагом. Основная задача при выборе величины h_k - это обеспечить выполнение неравенства j(x_k+1)<j(x_k).

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

            x_k+1=x_k-h_k cos  

       где - cos =

    В этом случаи величина рабочего шага не зависит от величины модуля градиента, и ею легче управлять изменением h . В районе оптимума может возникать значительное «рыскание», поэтому используют различные алгоритмы коррекции h.

    Наибольшее  распространение получили следующие  алгоритмы:

    1. (без коррекции);

    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) определяются соотношениями