Одномерные методы безусловной оптимизации (методы Фибоначчи и квадратичной аппроксимации)

Цель работы Изучить одномерные методы оптимизации, минимизировать функцию, заданную преподавателем, двумя методами; сравнить результаты оптимизации и выдать рекомендации по применению исследуемых методов.

Алгоритм метода Фибоначчи Подготовительный этап:

1) Выбрать — точность вычисления минимума на интервале. Положить и .

• 2) .
• 3) Если

тогда, иначе и идти к 3.

4) Вычислить:

.

• 5) Если, тогда, и идти к 6. Если и идти к 6.
• 6) Положить .

Основной этап:

• 7) Если, тогда и идти к 8. Иначе, и идти к 9.
• 8) Вычислить

и. Перейти к шагу 10.

9) Вычислить.

и. И идти к 10.

• 10) Если, то и идти к 11, иначе и идти к 11.
• 11) Если, тогда и идти к 7.

Иначе положить.

и вычислить.

Блок-схема алгоритма Алгоритм метода квадратичной аппроксимации.

• 1) Вычислить
• 2) Вычислить и .
• 3) Если, тогда. Если, то .

• 4) Вычислить и найти, .
• 5) С использованием посчитать .

6) Условия окончания поиска: и. Если оба выполняются, закончить алгоритм. В противном случае — идти к шагу 7.

7) Выбрать «лучшую» точку среди или, И две точки слева и справа от нее. Расположить их в естественном порядке и идти к шагу 4.

После шага (5) следует провести дополнительную проверку, и в случае, если точка слишком далеко от, заменить ее точкой .

Блок-схема алгоритма Код программы.

using System;

using System.Collections.Generic;

using System. Linq;

using System. Text;

using System. Data;

using ZedGraph;

namespace Algorithms.

{.

public class Fibonachi.

{.

private int func;

private double xOpt, fOpt;

private int iter;

private string process;

PointPairList points;

public PointPairList Points.

{.

get { return points; }.

set { points = value; }.

}.

public string Process.

{.

get { return process; }.

set { process = value; }.

}.

public double FOpt.

{.

get { return fOpt; }.

set { fOpt = value; }.

}.

public double XOpt.

{.

get { return xOpt; }.

set { xOpt = value; }.

}.

public int Iter.

{.

get { return iter; }.

set { iter = value; }.

}.

public Fibonachi (int func).

{.

this.func = func;

}.

private double Func (double x).

{.

if (func == 1).

{.

return 2 * Math. Pow ((x — 3), 2) + Math. Exp (Math.Pow (x, 2) / 2);

}.

if (func == 2).

{.

return (Math.Pow (x, 3) + x) / (Math.Pow (x, 4) — Math. Pow (x, 2) + 1);

}.

return 0;

}.

private double F (int p).

{.

if (p == 1 || p == 2).

{.

return 1;

}.

else.

{.

return (F (p — 1) + F (p — 2));

}.

}.

public void Fibo (double a0, double b0, double eps).

{.

points = new PointPairList ();

int j = 1;

int m;

for (; ;).

{.

if (F (j + 1) = (1 / eps) * (b0 — a0)).

{.

m = j;

break;

}.

j++;

}.

double x1s = a0 + (F (m) / F (m + 2)) * (b0 — a0);

double x2s = a0 + (F (m + 1) / F (m + 2)) * (b0 — a0);

double a1, b1;

if (Func (x1s) <= Func (x2s)).

{.

a1 = a0;

b1 = x2s;

}.

else.

{.

a1 = x1s;

b1 = b0;

}.

double x1k = x1s;

double x2k = x2s;

double ak = a1;

double bk = b1;

Process = «» ;

for (int k = 1; k <= m — 1; k++).

{.

double x1k1, x2k1;

double ak1, bk1;

if (Func (x1k) <= Func (x2k)).

{.

x2k1 = x1k;

x1k1 = ak + (F (m — k) / F (m + 2)) * (b0 — a0);

}.

else.

{.

x1k1 = x2k;

x2k1 = ak + (F (m — k + 1) / F (m + 2)) * (b0 — a0);

}.

if (Func (x1k1) <= Func (x2k1)).

{.

ak1 = ak;

bk1 = x2k1;

}.

else.

{.

ak1 = x1k1;

bk1 = bk;

}.

Process += «x: «+ (ak1 + bk1) / 2 + «; f (x): «+ Func ((ak1 + bk1) / 2) + «; итерация: «+ k + «; «;

points.Add (k, Math. Abs (ak1 — bk1));

x1k = x1k1;

x2k = x2k1;

ak = ak1;

bk = bk1;

}.

XOpt = (ak + bk) / 2;

FOpt = Func (XOpt);

Iter = m — 1;

}.

public void Quadratic (double x1, double deltaX, double eps1, double eps2).

{.

points = new PointPairList ();

double x2 = x1 + deltaX;

double x3;

if (Func (x1) > Func (x2)).

{.

x3 = x1 + 2 * deltaX;

}.

else.

{.

x3 = x1 — deltaX;

}.

int k = 1;

Process += «» ;

for (; ;).

{.

double[] F = { Func (x1), Func (x2), Func (x3) };

double Fmin = F. Min ();

int minIndex = Array. IndexOf (F, Fmin);

double xMin = 0;

switch (minIndex).

{.

case 0: xMin = x1; break;

case 1: xMin = x2; break;

case 2: xMin = x3; break;

default: break;

}.

double a1 = (F[1] - F[0]) / (x2 — x1);

double a2 = (1 / (x3 — x2)) * ((F[2] - F[0]) / (x3 — x1) ;

(F[1] - F[0]) / (x2 — x1));

double xS = ((x2 + x1) / 2) — (a1 / (2 * a2));

if (xS > (x3 + deltaX)).

{ оптимизация функция фибоначчи итерация.

xS = x3 + deltaX;

}.

if (Math.Abs (Fmin — Func (xS)) <= eps1 && Math. Abs (xMin — xS) <= eps2).

{.

Process += «x: «+ xS + «; f (x): «+ Func (xS) + «; итерация: «+ k + «; «;

points.Add (k, Math. Abs (x1 — x3));

XOpt = xS;

FOpt = Func (xS);

Iter = k;

break;

}.

else.

{.

double[] xBest = { Func (xS), Func (xMin) };

int minInd = Array. IndexOf (xBest, xBest. Min ());

switch (minInd).

{.

case 0: x2 = xS; break;

case 1: x2 = xMin; break;

default: break;

}.

x1 = x2 — deltaX;

x3 = x2 + deltaX;

Process += «x: «+ xS + «; f (x): «+ Func (xS) + «; итерация: «+ k + «; «;

k++;

}.

if (k > 10 000).

{.

Process = «Необходимо увеличить значения Е1 и Е2, или уменьшить шаг!» ;

break;

}.

}.

}.

}.

}.

Результаты работы программы Задание: f (x) = 2(x — 3)² + exp{x² / 2}, [0, 100].

Рисунок 1 — Решение методом Фибоначчи, график изменения длинны интервала неопределенности от номера итерации Результат работы программы для метода Фибоначчи:

x: 19,983 005 609 879; f (x): 1,5 973 081 599 4183E+79; итерация: 1;

x: 11,8 033 988 780 243; f (x): 1,7 906 160 936 8607E+30; итерация: 2;

x: 7,2 949 016 829 636; f (x): 359 433 594 996,898; итерация: 3;

x: 4,50 849 719 506 067; f (x): 25 937,6006853167; итерация: 4;

x: 2,78 640 448 790 293; f (x): 48,6 136 188 214 171; итерация: 5;

x: 1,72 209 270 715 774; f (x): 7,67 136 451 462 504; итерация: 6;

x: 1,6 431 178 074 518; f (x): 9,25 565 487 933 309; итерация: 7;

x: 1,47 084 263 507 781; f (x): 7,62 630 189 506 422; итерация: 8;

x: 1,72 209 270 715 774; f (x): 7,67 136 451 462 504; итерация: 9;

x: 1,56 681 192 490 506; f (x): 7,52 057 196 317 356; итерация: 10;

x: 1,66 278 121 473 232; f (x): 7,56 084 342 303 454; итерация: 11;

x: 1,60 346 972 230 689; f (x): 7,51 727 760 135 902; итерация: 12;

x: 1,56 681 192 490 506; f (x): 7,52 057 196 317 356; итерация: 13;

x: 1,58 946 561 992 866; f (x): 7,51 593 707 248 513; итерация: 14;

x: 1,60 346 972 230 689; f (x): 7,51 727 760 135 902; итерация: 15;

x: 1,59 482 012 966 151; f (x): 7,51 606 349 215 786; итерация: 16;

x: 1,58 946 561 992 866; f (x): 7,51 593 707 248 513; итерация: 17;

x: 1,59 276 070 284 119; f (x): 7,51 595 867 486 789; итерация: 18;

x: 1,59 070 127 602 086; f (x): 7,51 592 415 514 834; итерация: 19;

x: 1,59 193 693 211 305; f (x): 7,51 593 644 659 914; итерация: 20;

x: 1,59 111 316 138 492; f (x): 7,51 592 544 841 694; итерация: 21;

x: 1,59 070 127 602 086; f (x): 7,51 592 415 514 834; итерация: 22;

x: 1,59 028 939 065 679; f (x): 7,51 592 566 285 447; итерация: 23;

x*: 1,59 028 939 065 679; f (x)*: 7,51 592 566 285 447; Число итераций: 23.

Рисунок 2 — Решение методом квадратичной аппроксимации Результат для метода квадаратичной аппроксимации:

x: 1,03; f (x): 9,46 149 700 020 013; итерация: 1;

x: 1,05; f (x): 9,34 042 093 880 804; итерация: 2;

x: 1,07; f (x): 9,22 240 461 705 795; итерация: 3;

x: 1,09; f (x): 9,10 750 938 343 364; итерация: 4;

x: 1,11; f (x): 8,99 579 975 896 803; итерация: 5;

x: 1,13; f (x): 8,8 873 436 109 131; итерация: 6;

x: 1,15; f (x): 8,78 221 233 700 656; итерация: 7;

x: 1,17; f (x): 8,6 804 810 610 181; итерация: 8;

x: 1,19; f (x): 8,58 222 884 030 586; итерация: 9;

x: 1,21; f (x): 8,48 753 888 616 402; итерация: 10;

x: 1,23; f (x): 8,39 649 879 779 722; итерация: 11;

x: 1,25; f (x): 8,30 920 081 081 562; итерация: 12;

x: 1,27; f (x): 8,22 574 206 120 736; итерация: 13;

x: 1,29; f (x): 8,14 622 486 581 229; итерация: 14;

x: 1,31; f (x): 8,7 075 702 039 334; итерация: 15;

x: 1,33; f (x): 7,99 945 211 647 944; итерация: 16;

x: 1,35; f (x): 7,93 242 987 823 748; итерация: 17;

x: 1,37; f (x): 7,86 981 652 072 031; итерация: 18;

x: 1,39; f (x): 7,81 174 513 093 462; итерация: 19;

x: 1,41; f (x): 7,75 835 607 327 569; итерация: 20;

x: 1,43; f (x): 7,70 979 742 098 812; итерация: 21;

x: 1,45; f (x): 7,66 622 541 543 119; итерация: 22;

x: 1,47; f (x): 7,62 780 495 505 703; итерация: 23;

x: 1,49; f (x): 7,59 471 011 614 841; итерация: 24;

x: 1,51; f (x): 7,56 712 470 751 294; итерация: 25;

x: 1,53; f (x): 7,54 524 286 149 153; итерация: 26;

x: 1,55; f (x): 7,52 926 966 381 242; итерация: 27;

x: 1,57; f (x): 7,51 942 182 500 937; итерация: 28;

x: 1,59; f (x): 7,5 159 283 963 241; итерация: 29;

x: 1,59 068 610 054 296; f (x): 7,51 592 416 101 319; итерация: 30;

x*: 1,59 068 610 054 296; f (x)*: 7,51 592 416 101 319; Число итераций: 30.

Вывод При выполнении лабораторной работы мною были изучены одномерные методы оптимизации (метод Фибоначчи и квадратичная аппроксимация), написана программа на языке C#, которая позволяет оптимизировать заданные функции этими методами.

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