Минимизация функции методом сопряженных градиентов
Министерство
образования и науки Российской Федерации
ГОСУДАРСТВЕННОЕ
ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО
ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
«ОРЕНБУРГСКИЙ
ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»
Факультет
экономики и управления
Кафедра
математических методов и моделей в экономике
ОТЧЕТ
по
учебной-вычислительной практике
на
базе кафедры математических методов и моделей в экономике
ГОУ
ОГУ 080116.65.9011.06 П
Руководители от кафедры:
профессор, заведующий
кафедры ММиМЭ А.Г. Реннер
ассистент кафедры ММиМЭ
Р.М. Шаяхметова
ассистент кафедры ММиМЭ
Т.А. Зеленина
Исполнители:
Студент группы 09 ММЭ
Д.А. Евдокимов
Оренбург
2011
Содержание
1. Задание на практику
. Безусловная минимизация функции многих переменных
.2 Градиентный метод наискорейшего спуска
.3 Метод сопряженных градиентов
.4 Блок-схема алгоритма минимизации
2.5 Листинг программы «Безусловная минимизация функции»
1. Задание на практику
Разработать программное обеспечение,
реализующее нахождение минимального значения заданной функции многих переменных
и её точку минимума методом сопряжённых градиентов.
2. Безусловная минимизация функции
многих переменных
Метод сопряжённых градиентов
является быстросходящимся методом, но он сходится только из начальных точек,
достаточно близких к точке минимума.
Начальное приближение следует найти
с помощью процедуры, реализующей метод наискорейшего спуска (использующей
процедуру минимизации вдоль заданного направления). Затем следует уточнить
точку минимума при помощи процедуры, реализующей метод сопряжённых градиентов
(использующей процедуру минимизации вдоль заданного направления). При этом
необходимо учесть возможность того, что значения переменных и самой функции
могут иметь разные масштабы (использовать масштабирующие коэффициенты и
относительные критерии останова).
.1 Минимизация функции вдоль
заданного направления
Численное решение задачи одномерной
минимизации:
Имеем некоторую
начальную точку 
и
вектор направления 
.
Требуется с заданной точностью ε найти точку
минимума функции в данном направлении и минимизирующее функцию значение α.
С помощью метода
удвоения шага локализуем интервал, на котором находится αmin.
Суть метода удвоения шага состоит в том, что мы выбираем некоторое
начальное значение α (в данном случае выберем нулевое) и некоторую величину шага h.
Следующую точку итерационной последовательности αi находим
по формуле αi=αi-1+2i-1*h. Затем вычисляем хi=х0+αih.
Итерации продолжаем до тех пор, пока не выполнится условие
f(хi)>f(хi-1). При выполнении этого условия полагаем αmin=[αi-2;
αi].
Затем уточним границы
интервала (и, соответственно, приближённое значение точки минимума) с помощью
одного из быстросходящихся методов. Например, с помощью метода золотого
сечения.
Суть метода золотого
сечения состоит в использовании одноимённой пропорции. Точка на отрезке
является его «золотым сечением», если она делит отрезок так, что его большая
часть соотносится с ним самим так же, как и меньшая часть с большей. На отрезке
существует две таких точки. Обозначим их α(1) и
α(2). Пусть a,b - левая и правая границы отрезка соответственно, тогда
их координаты можно выразить, используя формулы 
. Находя х(1)=х0+α(1)h
и х(2)=х0+α(2)h, сравниваем f(х(1)) и f(х(2)). Если f(х(1))>f(х(2)), то 
.
Если f(х(1))<f(х(2)), то 
. Если f(х(1))=f(х(2)),
то 
.
При необходимости находим новые точки золотого сечения. Следует заметить, что
точка α(1) является точкой золотого сечения для отрезка [a; α(2)],
а точка α(2) - точкой золотого сечения для [α(1); b].
Абсолютный критерий останова имеет вид 
. Относительный критерий
останова: 
.
steptol обычно принимают равным 10-p, где p - желаемое число значащих цифр
после запятой.
.2 Градиентный метод
наискорейшего спуска
Имеем оптимизационную
задачу минимизации функции: 
, где 
.
Каждое следующее приближение находим по формуле 
. Если вектор hk равен
антиградиенту функции в точке хk, а αk выбирается
из условия 
,
то мы имеем метод наискорейшего спуска.
Метод наискорейшего
спуска является методом первого порядка, так как использует информацию о
значении первых производных функции. К группе таких методов относятся различные
градиентные методы.
Градиентные методы
представляют собой методы спуска, в которых в качестве направлений убывания
выбирается направление антиградиента функции:
-grad
В качестве абсолютного
критерия останова обычно выбирают либо неравенство 
(критерий
сильной сходимости) или ║grad║
.
В качестве относительного критерия останова обычно выбирают либо 
,
либо .
Метод наискорейшего
спуска требует решения на каждом шаге задачи одномерной оптимизации 
,
т.е. из точки 
будем
двигаться в направлении антиградиента до тех пор, пока не достигнем минимума
функции на этом направлении.
Сходимость метода
наискорейшего спуска зависит от отношения максимального и минимального
собственных чисел в окрестности точки экстремума. Чем больше это отношение, тем
хуже сходимость метода.
При нахождении решения
задачи градиентными методами итерационный процесс продолжается до тех пор, пока
не выполнится выбранный критерий останова.
Геометрическая
иллюстрация метода представлена на рисунке 1.
Рисунок 1 -
геометрическая иллюстрация метода наискорейшего спуска
.3 Метод сопряженных
градиентов
Метод сопряжённых
градиентов - итерационный метод для безусловной оптимизации в многомерном
пространстве. Основным достоинством метода является то, что он решает
квадратичную задачу оптимизации за конечное число шагов. Однако, этот
работоспособность этого метода зависит от начального приближения. Поэтому перед
применением метода сопряжённых градиентов находят точку начального приближения
с помощью, например, метода наискорейшего спуска.
Рассмотрим следующую
частную задачу оптимизации:
Здесь 
-
симметричная положительно определённая матрица размера 
.
Такая задача оптимизации называется квадратичной. Имеем последовательность
точек хi=хi-1+αdi-1, где α выбирается из условия 
, а направление d - по
правилу 
,
где 
.
Для квадратичной функции метод сопряжённых градиентов сходится за n шагов, где
n - число переменных в функции.
В общем случае
(неквадратичная функция) для задачи минимизации имеем 
,
если 
и
,
если 
В качестве абсолютного
критерия останова обычно выбирают либо неравенство (критерий
сильной сходимости) или ║grad║.
В качестве относительного критерия останова обычно выбирают либо ,
либо .
Рисунок 2 -
Геометрическая иллюстрация метода сопряженных градиентов
2.4 Блок-схема алгоритма
минимизации
.5 Листинг программы
«Безусловная минимизация функции»
алгоритм сопряженный
градиент минимизация
unit Unit1;, Messages,
SysUtils, Variants, Classes, Graphics, Controls, Forms,, StdCtrls, XPMan;=
class(TForm): TButton;: TLabel;: TEdit;: TXPManifest;: TLabel;: TEdit;:
TButton;: TButton;: TLabel;: TEdit;: TEdit;: TListBox;: TLabel;: TEdit;:
TListBox;: TButton;: TButton;: TLabel;: TListBox;: TButton;: TButton;: TEdit;:
TLabel;Button4Click(Sender: TObject);Button5Click(Sender:
TObject);Button1Click(Sender: TObject);btn1Click(Sender:
TObject);btn3Click(Sender: TObject);btn2Click(Sender:
TObject);btn4Click(Sender: TObject);
{ Private declarations }
{ Public declarations
};nvar=5;x,x0,x00,xleft,d:array [0..(nvar-1)] of real;,h,lam0:
real;:integer;,tipich: array [0..nvar-1] of real; //Коэф-ты масштабирования и
типичные значения х и ф-ции: TForm1;
{$R *.dfm}myfunc(x:
array of real):real;:=sqr(x[0])+2*x[0]+2*sqr(x[1])+4*x[1]+5;;FindAlpha(x0,d:array
of Real; h,eps:real; n:integer; var lam0:real);lam: array [1..3] of
real;:integer;newlam;[1]:=lam[2];[2]:=lam[3];[3]:=lam[3]+h;:=2*h;;newx;i:integer;;i:=0
to (n-1) do[i]:=x0[i]+d[i]*lam[3];;FindInterval;i:Integer;myfunc(x)>myfunc(x0)
then begin:=-h;;;myfunc(x)<myfunc(x0) do begini:=0 to (n-1) do
begin[i]:=x0[i];[i]:=x[i];;;;;MakeItAccurate;i:integer;,lam2:real; //Золотое
сечение,x2: array [0..(nvar-1)] of real;: byte; //1 - интервал [a, lam2], 2 -
интервал [lam1, b], 1 - интервал [lam1, lam2]choose(lam1,lam2:real); //выбираем
новый отрезокi:integer;,v:real; //Чтобы постоянно функцию не вычислятьi:=0 to
(n-1) do
begin[i]:=x0[i]+lam1*d[i];[i]:=x0[i]+lam2*d[i];;:=myfunc(x1);:=myfunc(x2);u<v
then chosen:=1;u>v then chosen:=2;u=v then chosen:=3;;zollam; //Считаем
новые лямбдаchosen=1 then
begin[3]:=lam2;:=lam1;:=lam[3]-0.618*(lam[3]-lam[1]);;chosen=2 then
begin[1]:=lam1;:=lam2;:=lam[1]+0.618*(lam[3]-lam[1]);;chosen=3 then
begin[1]:=lam1;[3]:=lam2;:=lam[3]-0.618*(lam[3]-lam[1]);:=lam[1]+0.618*(lam[3]-lam[1]);;;makestop:boolean;norm:real;:integer;relxnorm(x1,x2:array
of real):real;relx:array [0..nvar-1] of real;:integer;:real;k:=0 to (n-1) do
begin[k]:=abs(x2[k]-x1[k]);abs(x2[k])>tipich[k] then relx[k]:=relx[k]/abs(x2[k])relx[k]:=relx[k]/tipich[k];;:=0;k:=0
to (n-1) do:=norme+sqr(relx[k]);:=sqrt(norme);:=norme; ;(lam1,lam2);i:=0 to
(n-1) do
begin[i]:=x0[i]+d[i]*lam[1];[i]:=x0[i]+d[i]*lam[3];;relxnorm(xleft,x)<eps
then makestop:=truemakestop:=false;;i:=0 to (n-1) do
x0[i]:=x00[i+1];:=lam[3]-0.618*(lam[3]-lam[1]);:=lam[1]+0.618*(lam[3]-lam[1]);not
makestop do zollam;;[1]:=0;[2]:=0;[3]:=0;;;;i:=1 to n
do[i]:=(xleft[i]+x[i])/2;:=(lam[3]+lam[1])/2;;spusken(x0:array of real;
eps,h:real; n:integer; var x1:array of real);xo,xn,agrad:array [0..(nvar-1)] of
Real; //xold, xnew, antigrad.,gradnorm:Real;:integer;grads(x:array of Real; var
agrad: array of Real);i:integer;:real;: array [0..(nvar-1)] of
Real;[0]:=-(2*x[0]+2);[1]:=-(4*x[1]+4);:=myfunc(x);abs(g)>tipich[n] then
g:=abs(g)g:=tipich[n];i:=0 to (n-1) do
begin[i]:=abs(-agrad[i]);abs(x[i])>tipich[i] then
gradtole[i]:=gradtole[i]*abs(x[i])gradtole[i]:=gradtole[i]*tipich[i];[i]:=gradtole[i]/g;;:=gradtole[0];i:=0
to (n-1) dogradnorm<gradtole[i] then gradnorm:=gradtole[i];;xnew(alpha:real;
x0:array of Real; var x:array of Real);i:integer;i:=0 to (n-1)
do[i]:=x0[i]+alpha*agrad[i];;stop (norm,eps:Real):Boolean;norm<eps then
stop:=truestop:=false;;j:=0 to (n-1) do
xo[j]:=x0[j];(xo,agrad);(xo,agrad,h,eps,n,alpha);(alpha,xo,xn);j:=0 to (n-1) do
xo[j]:=xn[j];stop(gradnorm,eps);j:=0 to (n-1) do
x1[j]:=xn[j];;soprgrad(x0:array of Real; eps,h:real; n:Integer; var x:array of
real);xold, xnew, nd, antigrad, predd: array [0..(nvar-1)] of real; //predd -
предыдущее d, newd - новое d,teknorm,prednorm,alpha:Real; //текушая и
предыдущая нормы,counter:integer;grads(x:array of Real; var agrad: array of
Real; gradnorm:real);g:real;:integer;: array [0..(nvar-1)] of
Real;[0]:=-(2*x[0]+2);[1]:=-(4*x[1]+4);:=myfunc(x);abs(g)>tipich[n] then
g:=abs(g)g:=tipich[n];i:=0 to (n-1) do
begin[i]:=abs(-agrad[i]);abs(x[i])>tipich[i] then
gradtole[i]:=gradtole[i]*abs(x[i])gradtole[i]:=gradtole[i]*tipich[i];[i]:=gradtole[i]/g;;:=gradtole[0];i:=1
to (n-1) dogradnorm<gradtole[0] then gradnorm:=gradtole[i];;newbeta(ti:Integer;
norm,prednorm:real):Real; //ti - текущая итерация((ti mod n)=0) then
newbeta:=0newbeta:=Sqr(norm/prednorm);;newd(agrad,d:array of Real; beta:Real;
var nd:array of real);i:integer;i:=0 to (n-1)
do[i]:=agrad[i]+beta*d[i];;theend(norm,eps:real):boolean;norm<(eps/1000)
then theend:=truetheend:=false;;findx(alpha:real; d,x0:array of Real; var
x:array of Real);i:integer;i:=0 to (n-1) do[i]:=x0[i]+alpha*d[i];;k:=0 to (n-1)
do xold[k]:=x0[k];(xold,eps,h,n,xnew);(xnew,antigrad,prednorm);k:=0 to (n-1) do
xold[k]:=xnew[k];:=0;:=newbeta(counter,teknorm,prednorm);(antigrad,predd,beta,nd);(xold,nd,h,eps,n,alpha);(alpha,nd,xold,xnew);k:=0
to (n-1) do xold[k]:=xnew[k];:=teknorm;:=counter+1;theend(teknorm,eps);k:=0 to
(n-1) do x[k]:=xnew[k];;TForm1.Button4Click(Sender:
TObject);g:real;.AddItem(Edit3.Text, Edit3);:=StrToFloat(Edit3.Text);('Enter
real number!');.Items.Delete(Lst1.Items.Count-1);;;TForm1.Button5Click(Sender:
TObject);.Items.Delete(Lst1.ItemIndex);;TForm1.Button1Click(Sender: TObject);i:integer;:real;:=StrToFloat(Edit4.Text);:=StrToFloat(Edt1.Text);('Enter
real number!');.Text:='';.Text:='';;:=Lst1.Items.Count;i:=0 to (n-1) do
begin[i]:=StrToFloat(Lst1.Items[i]);[i]:=StrToFloat(Lst2.Items[i]);[i]:=StrToFloat(Lst3.Items[i]);;:=myfunc(tipich);[n]:=g;(x0,eps,h,n,x);.Text:='';i:=0
to (n-1) do.Text:=Edit2.Text+FloatToStr(x[i])+'; ';;TForm1.btn1Click(Sender:
TObject);g:real;.AddItem(Edt2.Text, Edt2);:=StrToFloat(Edt2.Text);('Enter real
number!');.Items.Delete(Lst2.Items.Count-1);;;TForm1.btn3Click(Sender:
TObject);g:real;.AddItem(Edt3.Text, Edit3);:=StrToFloat(Edt3.Text);('Enter real
number!');.Items.Delete(Lst1.Items.Count-1);;;TForm1.btn2Click(Sender:
TObject);.Items.Delete(Lst2.ItemIndex);;TForm1.btn4Click(Sender:
TObject);.Items.Delete(Lst3.ItemIndex);;.