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

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

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

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

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

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

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

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

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

Хабаровск 2003

Содержание:

I. Методы спуска (Общая схема) ­_________________________ 3

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

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

IV. Метод наискорейшего спуска.______________________________ 9

V. Описание программы._____________________________________10

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

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

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

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

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

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

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

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

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

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

xk+1
=xk
-hk
cos

где - cos=

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

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

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

2. если ; если

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

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

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

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

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

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

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

u=f(M)=f(x
1
, x
2
, . . . ,xn
).
Здесь через М
обозначена точка n-мерного пространства с координатами x
1
, x
2
, . . . ,xn
: M=(x
1
, x
2
, . . . ,xn
).
Выберем какую-нибудь начальную точку М
0
=
(x
1
0
, x
2
0
, . . . ,xn
0
)
и рассмотрим функцию f при фиксированных значениях всех переменных, кроме первой: f(x
1
, x
2
0
,x
3
0
, . . . ,xn
0
).
Тогда она превратится в функцию одной переменной x
1
.
Изменяя эту переменную, будем двигаться от начальной точки x
1
=x
1
0
в сторону убывания функции, пока не дойдем до ее минимума при x
1
=x
1
1
,
после которого она начинает возрастать. Точку с координатами ( x
1
1
, x
2
0
,x
3
0
, . . . ,xn
0
) обозначим через М
1
,
при

этом f(M0
)
>= f(M
1
).

Фиксируем теперь переменные: x
1
=x
1
1
, x
3
= x
3
0
, . . . ,xn
=xn
0
и рассмотрим функцию f
как функцию одной переменной x
2
: f(x
1
1
, x
2
2
, x
3
0
. . . ,xn
0
).
Изменяя x
2
,
будем опять двигаться от начального значения x2
=x2
0
в сторону убывания функции, пока не дойдем до минимума при x2
=x2
1
.Точку с координатами

{x
1
1
, x
2
1
, x
3
0
. . . xn
0
} обозначим через М
2
, при этом f(M1
)
>=f(M
2
).

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

x
3
, x
4
, . . . ,xn
.
Дойдя до переменной xn
,
снова вернемся к x
1
и продолжим процесс. Эта процедура вполне оправдывает название метода. С ее помощью мы построим последовательность точек М
0
,М
1
,М
2
, . . . , которой соответствует монотонная последовательность значений функции

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

Проведем такую же минимизацию целевой функции по переменным x
3
, x
4
, . . . ,xn
.
Дойдя до переменной xn
,
снова вернемся к x
1
и продолжим процесс. Эта процедура вполне оправдывает название метода. С ее помощью мы построим последовательность точек М
0
,М
1
,М
2
, . . . , которой соответствует монотонная последовательность значений функции

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

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

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

f(x) 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)
) 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)
)<=f(x(0)
).Затем находят точку минимума x(1)
функции f (x1
~(0)
,x2
) по второй координате. Далее делают следующий шаг вычислений при k=1. Полагают, что исходной точкой расчета является х(1)
. Фиксируя вторую координату точки х(1)
, находят точку минимума х~(1)
= (x1
~(1)
,x2
(1)
), функции f(x1
,x2
(1)
) одной переменной x(1)
; при этом f(x~(1)
)<=f(x(1)
)<=f(x(0)
). Точку х(2)
получают, минимизируя целевую функцию f(x1
~(1)
,x2
), вновь по коорданате х2
, фиксируя координату x1
~(1)
,точки x(1)
, и т.д. Условием прекращения вычислительной процедуры при достижении заданной точности 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))2
+(дf/ду( x, у, z))2
+(дf/дг(x, y,z))2
.

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

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

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

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

Для оценки частных производных используются разностные методы:

1.Алгоритм с центральной пробой

2. Алгоритм с парными пробами

где gi
– пробный шаг по i-й переменной, выбираемый достаточно малым для разностной оценки производной.

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

Df(x1
, ...,xi
+ gi
, ..., xn
) - f(x1
, ..., xi
, ..., xn
)

Df(x1
, ...,xi
+ gi
, ..., xn
) - f(x1
, ..., xi
- gi
,..., xn
)

будет допущена большая ошибка.

Первый алгоритм требует меньших затрат по сравнению со вторым (обычно затраты выражаются количеством вычислений критерия оптимальности), но позволяет получить решение менее точно, чем второй, эта погрешность зависит от величины пробного шага

На рис. изображены линии уровня функции двух переменных u= f (х, у),
, и приведена траектория поиска ее минимума с помощью метода градиентного спуска.

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

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

Описание программы

Программа предназначена для нахождения точек минимума функций нескольких переменных – другими словами для минимизации этих функций.

В программе реализован один из методов спуска – Градиентный метод спуска с выбором шага. Начальный шаг задается.

Изменение шага осуществляется по схеме

если ; если

Вычисление градиента происходит по методу с парными пробами, это улучшает поиск за счёт более точного вычисления градиента.

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

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

В связи с этим в программе был реализован более точный метод градиентного спуска.

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

(В области оптимума градиент равен 0, но достичь этого значения практически не возможно, поэтому задаётся требуемая малость близкая к 0).

Так же в программе можно задавать номер итерации выхода из цикла,

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

Реализация программы:

Общая блок схема

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

Программа написана на языке программирования С++, в

среде Borland C++5.

Программа имеет понятный интуитивный графический интерфейс.

После запуска необходимо следовать инструкциям и вводить все необходимые данные.

На начальном этапе выбирается одна из предложенных функций,

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

Затем программа рассчитывает точки приближения и находит для данных ограничений точку минимума.

Затем графически отображает траекторию поиска точки минимума.

Приложение А

#include <vcl.h>

#pragma hdrstop

#include "Math.hpp"

#include "math.h"

#include "Unit1.h"

//---------------------------------------------------------------------------

#pragma package(smart_init)

#pragma resource "*.dfm"

TForm1 *Form1;

//---------------------------------------------------------------------------

__fastcall TForm1::TForm1(TComponent* Owner)

: TForm(Owner)

{

}

//---------------------------------------------------------------------------

int ii=0,n=0,s=0;

AnsiString Formula[3]={"U=A*x1^3+B*x2^2-C*x1-D*x2","U=x1^2+x1*x2+x2^2","U=X1^2+X2^2"};

int KolPer[3]={2,2,2};// массив в котором хранится кол-во перемен. для каждой ф-ии

bool DD=true,Diapozon=true; // если true то точка входит в диапозон иначе нет

double PeremenN[5]={0};//double *PeremenN =new double[n]; //нул.приб

double InterN[5]={0};//double *InterN =new double[n]; //нач

double InterK[5]={0};//double *InterK =new double[n]; //кон

double Param[4]={0}; //параметры

double T1[5]={0};//double *T1 =new double[n]; //tochka i -я

double T2[5]={0};//double *T2 =new double[n]; //tochka i+1 -я

double TempT[5]={0};//double *TempT =new double[n]; // временная tochka i+1 -я

double BB[5]={0};//double *BB= new double [n]; // BB - массив с измененой i-ой точкой X[i]+g

double B[5]={0};//double *B= new double [n]; //B - массив с измененой i-ой точкой X[i]-g

int g=0;

double ModG =0; //модуль градиента

int ss=0,ind=0;

double **Tochki; // указатель на массив с точками приближения

//---------------------------------------------------------------------------

double TForm1::F1( double T[]) //Formula1 U=A*x1^3+B*x2^2-C*x1-D*x2

{ double U = 0;

U=IntPower(T[0],3)+2*IntPower(T[1],2)-3*T[0]-4*T[1];

return U; }

//---------------------------------------------------------------------------

double TForm1::F2( double T[]) //Formula2 U=x1^2+x1*x2+x2^2

{ double U = 0;

U = IntPower(T[0],2)+T[0]*T[1]+IntPower(T[1],2);

return U; }

//---------------------------------------------------------------------------

double TForm1::F3( double T[]) //Formula3 U=X1^2+X2^2

{ double U = 0;

U =T[0]*T[0]+T[1]*T[1]+1;

return U; }

//---------------------------------------------------------------------------

void TForm1::Tochka(double shag) // функция считает координаты следующей точки

{ // n - количество переменных