Метод многомерной нелинейной оптимизации – метод наискорейшего спуска

Работа из раздела: «Математика»

Радиотехнический факультет

ОТЧЕТ

по лабораторной работе:

'Метод многомерной нелинейной оптимизации - метод наискорейшего спуска'

Самара 2013

Задание

1 Изучить особенности метода многомерной нелинейной оптимизации - метод наискорейшего спуска;

2 Разработка математической модели и алгоритма для выбранного метода;

3 По составленному алгоритму написать демонстрационный вариант программы, отражающий основные этапы выбранного метода на языке программирования Borland Delphi 7.

Реферат

Пояснительная записка __ с, 6 рисунков, 3 источника, 1 приложение.

МЕТОД НАИСКОРЕЙШЕГО СПУСКА, МИНИМУМ ФУНКЦИИ, ГРАДИЕНТНЫЕ МЕТОДЫ, НЕЛИНЕЙНЫЕ ФУНКЦИИ.

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

Часто, при исследовании функций сигналов РЭА возникает потребность нахождения экстремума этой функции. Такие задачи относятся к нелинейному программированию. Одними из наиболее реализуемых методов решения этих задач являются градиентные методы, в частности, метод наискорейшего спуска

Содержание

1. Теоретические основы метода
2. Алгоритм программы
3. Листинг программы
4. Контрольный пример
Заключение
Список использованных источников

1. Теоретические основы метода

В этом методе из некоторой начальной точки движение осуществляется вдоль направления градиента до тех пор, пока производная по этому направлению не будет равна нулю. Далее из этой точки определяем новый градиент и т.д. Отличие здесь в том, что длина шага из точки X^k определяется из условия, чтобы обеспечить [2]:

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

Наискорейший и покоординатный методы называют методами с длинным шагом. Кроме этого существуют методы, использующие вторую производную для определения длины шага, например, метод Ньютона [2]:

X^k⁺¹=X^k+ [F” (X^k)] - ¹g (X^k)

где [F” (X^k)] - ¹^-обратная матрица вторых производных в точке X^k.

Рассмотрим нахождение минимума функции двух переменных

Задаемся исходной точкой (x⁰; y⁰).

1. Сначала найдём частные производные по x и y:

нелинейная оптимизация наискорейший спуск

2. Если обе производные в точке (x⁰; y⁰) равны нулю, то задача решена, и минимум функции находится в этой точке. В противном случае необходимо определить координаты новой точки (x¹; y¹):

3. Теперь полученные значения принимаем за исходные (x¹=x⁰; y¹=y⁰) и возвращаемся к пункту 2.

Шаг t находится из условия минимума функции: . То есть необходимо найти такое значение t, при котором функция имеет минимум. В нашем случае:

;

Минимум этой функции находится из равенства первой ее производной по t к нулю:

Отсюда находим t:

Для некоторых нелинейных функций этот процесс не позволяет найти такие значения x и y, при которых производная равнялась бы нулю. Поэтому для обеспечения конечности числа итераций в этом случае вводим точность Е, тогда вычисления прекращаются либо когда производная в точке становится равной нулю (в этом случае значение Е задается равным нулю), либо когда |x^k^-1 - x^k| будет меньше наперед заданной точности Е.

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

3. Листинг программы

unit Unit1;

interface

uses

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

Dialogs, StdCtrls, ExtCtrls;

type

TForm1 = class (TForm)

LabeledEdit1: TLabeledEdit;

LabeledEdit2: TLabeledEdit;

LabeledEdit3: TLabeledEdit;

LabeledEdit4: TLabeledEdit;

Button1: TButton;

Label1: TLabel;

Label2: TLabel;

LabeledEdit5: TLabeledEdit;

LabeledEdit6: TLabeledEdit;

Label3: TLabel;

Label4: TLabel;

Label5: TLabel;

Label6: TLabel;

LabeledEdit7: TLabeledEdit;

Label8: TLabel;

procedure Button1Click (Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

Form1: TForm1;

A, B, C, D, E: real;

x: array [0.100] of real;

y: array [0.100] of real;

dx: array [0.100] of real;

dy: array [0.100] of real;

t: array [0.100] of real;

i: integer;

implementation

{$R *. dfm}

procedure TForm1. Button1Click (Sender: TObject);

label l1;

begin

if (LabeledEdit1. Text='') or (LabeledEdit2. Text='') or (LabeledEdit3. Text='') or (LabeledEdit4. Text='') or (LabeledEdit5. Text='') or (LabeledEdit6. Text='') or (LabeledEdit7. Text='') then

Label2. Caption: ='Заполните все поля! '

else

begin

Label2. Caption: ='';

A: =strtofloat (LabeledEdit1. Text);

B: =strtofloat (LabeledEdit2. Text);

C: =strtofloat (LabeledEdit3. Text);

D: =strtofloat (LabeledEdit4. Text);

E: = strtofloat (LabeledEdit7. Text);

x [0]: =strtofloat (LabeledEdit5. Text);

y [0]: =strtofloat (LabeledEdit6. Text);

i: =0;

dx [i]: =A+2*C*x [i];

dy [i]: =B+2*D*y [i];

While ( (dx [i] <>0) and (dy [i] <>0)) {or ( (dx [i] >E) or (dx [i] < (0-E))) and ( (dy [i] >E) or (dy [i] < (0-E))) }do

begin t [i]: = ( ( (A+2*C*x [i]) *dx [i]) + ( (B+2*D*y [i]) *dy [i])) / ( (2*C*sqr (dx [i])) + (2*D*sqr (dy [i])));

x [i+1]: =x [i] - t [i] *dx [i];

y [i+1]: =y [i] - t [i] *dy [i];

if ( ( (x [i+1] - x [i]) <=E) and ( (x [i+1] - x [i]) >= (0-E))) and ( ( (y [i+1] - y [i]) <=E) and ( (y [i+1] - y [i]) >= (0-E))) then

goto l1 else

dx [i+1]: =A+2*C*x [i+1];

dy [i+1]: =B+2*D*y [i+1];

i: =i+1;

end;

l1: begin

Label5. Caption: ='xmin = '+floattostr (x [i]);

Label6. Caption: ='ymin = '+floattostr (y [i]);

Label4. Caption: ='Минимум функции F (x,y) ='+floattostr (A) +'x+'+floattostr (B) +'y+'+floattostr (C) +' (x) ^2+'+floattostr (D) +' (y) ^2 с заданной точностью равен: ';

end;

end.

4. Контрольный пример

Рисунок 1 - Начальное окно программы

Рисунок 2 - Задание параметров в программу

Рисунок 3 - Результат расчетов по выбранному методу

Заключение

В ходе данной работы был изучен метод многомерной нелинейной оптимизации - метод наискорейшего спуска, разработан алгоритм решения поставленной задачи, написана и отлажена программа в среде программирования Borland Delphi 7.0. [3]. С помощью данной программы можно решать задачу по нахождению точек минимума функции двух переменных, с заданной точностью расчётов.

Список использованных источников

1 СТО СГАУ 02068410-004 - 2007. Стандарт организации. Общие требования к учебным текстовым документам [Текст] - Самара: СГАУ, 2007. - 30с.

2 Матюнин, С.А. Методы Гаусса-Зейделя и наискорейшего спуска [Текст] /: методические указания для выполнения лабораторных работ/С.А. Матюнин, Б.В. Скворцов. - Самара: СГАУ, 1996. - 19с.

3 Баженова, И.Ю. Delphi 7. Самоучитель программиста [Текст] /И.Ю. Баженова. - М.: КУДИЦ - Образ, 2003. - 448с.

4 Фленов, М.В. Библия Delphi [Текст] / М.В. Фленов. - СПБ.: БХВ-Петербург, 2011. - 686с.