Минимизация функции методом сопряженных градиентов

Разработка программного обеспечения, реализующего нахождение минимального значения заданной функции многих переменных и ее точку минимума методом сопряжённых градиентов. Минимизация функции вдоль заданного направления. Блок-схема алгоритма минимизации.
Краткое сожержание материала:

Размещено на

Размещено на

Министерство образования и науки Российской Федерации

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«ОРЕНБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»

Факультет экономики и управления

Кафедра математических методов и моделей в экономике

ОТЧЕТ

по учебной-вычислительной практике

на базе кафедры математических методов и моделей в экономике

ГОУ ОГУ 080116.65.9011.06 П

Руководители от кафедры:

профессор, заведующий кафедры ММиМЭ А.Г. Реннер

ассистент кафедры ММиМЭ Р.М. Шаяхметова

ассистент кафедры ММиМЭ Т.А. Зеленина

Исполнители:

Студент группы 09 ММЭ Д.А. Евдокимов

Оренбург 2011

Содержание

1. Задание на практику

2. Безусловная минимизация функции многих переменных

2.1 Минимизация функции вдоль заданного направления

2.2 Градиентный метод наискорейшего спуска

2.3 Метод сопряженных градиентов

2.4 Блок-схема алгоритма минимизации

2.5 Листинг программы «Безусловная минимизация функции»

1. Задание на практику

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

2. Безусловная минимизация функции многих переменных

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

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

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.2 Градиентный метод наискорейшего спуска

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

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

Градиентные методы представляют собой методы спуска, в которых в качестве направлений убывания выбирается направление антиградиента функции:-grad

В качестве абсолютного критерия останова обычно выбирают либо неравенство (критерий сильной сходимости) или ¦grad¦. В качестве относительного критерия останова обычно выбирают либо , либо .

С помощью метода минимизации функции вдоль заданного направления осуществляется поиск минимума из заданной точки. В методе наискорейшего спуска в качестве вектора направления используют вектор антиградиента.

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

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

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

Геометрическая иллюстрация метода представлена на рисунке 1.



Рисунок 1 - геометрическая иллюстрация метода наискорейшего спуска

2.3 Метод сопряженных градиентов

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

Рассмотрим следующую частную задачу оптимизации:

Здесь - симметричная положительно определённая матрица размера . Такая задача оптимизации называется квадратичной. Имеем последовательность точек хi=хi-1+бdi-1, где б выбирается из условия , а направление d - по правилу , где . Для квадратичной функции метод сопряжённых градиентов сходится за n шагов, где n - число переменных в функции.

В общем случае (неквадратичная функция) для задачи минимизации имеем , если и , если

В качестве абсолютного критерия останова обычно выбирают либо неравенство (критерий сильной сходимости) или ¦grad¦. В качестве относительного критерия останова обычно выбирают либо , либо .

Рисунок 2 - Геометрическая иллюстрация метода сопряженных градиентов

2.4 Блок-схема алгоритма минимизации



2.5 Листинг программы «Безусловная минимизация функции»

алгоритм сопряженный градиент минимизация

unit Unit1;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, StdCtrls, XPMan;

type

TForm1 = class(TForm)

Button1: TButton;

Label1: TLabel;

Edit2: TEdit;

XPManifest1: TXPManifest;

Label2: TLabel;

Edit3: TEdit;

Button4: TButton;

Button5: TButton;

Label3: TLabel;

Edit4: TEdit;

edt1: TEdit;

lst1: TListBox;

lbl1: TLabel;

edt2: TEdit;

lst2: TListBox;

btn1: TButton;

btn2: TButton;

lbl2: TLabel;

lst3: TListBox;

btn3: TButton;

btn4: TButton;

edt3: TEdit;

Label4: TLabel;

procedure Button4Click(Sender: TObject);

procedure Button5Click(Sender: TObject);

procedure Button1Click(Sender: TObject);

procedure btn1Click(Sender: TObject);

procedure btn3Click(Sender: TObject);

procedure btn2Click(Sender: TObject);

procedure btn4Click(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

const nvar=5;

var x,x0,x00,xleft,d:array [0..(nvar-1)] of real;

eps,h,lam0: real;

n:integer;

macht,tipich: a...