Алгоритмическое решение

Формулировка поставленной задачи

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

Математическое решение

Постановка задачи

Требуется найти безусловный минимум функции f(x) многих переменных, т.е.найти такую точку x^*, принадлежающую Rⁿ, в которой бы функция имела свой минимум.

Стратегия поиска

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

Алгоритмическое решение

Метод Розенброка:

Шаг 1. Задать начальную точку х⁰, число е > 0 для остановки алгоритма, коэффициент растяжения

α > 1 и сжатия -1 < β < 0, в качестве начальных линейно независимых и ортогональных направлений d₁, d₂, …, d_n выбрать координатные направления:

d₁ = {1, 0, …, 0}, d₂ = {0, 1, …, 0}, …, d_n = {0, 0, …, 1};

начальную длину шага вдоль каждого из направлений поиска ∆ ₁⁰, …, ∆ _n⁰ > 0;

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

Положить y¹= x⁰, k = 0, i = 1, ∆ _i = ∆ _i⁰ для всех i.

Шаг 2. Сделать шаг по i-му направлению:

а) если f(yⁱ + ∆ _id_i) < f(yⁱ), шаг считается удачным. В этом случае следует положить yⁱ⁺¹ = yⁱ + ∆ _id_i,

∆ _i = α ∆ _i и перейти к шагу 3.

б) если f(yⁱ + ∆ _id_i) ≥ f(yⁱ), шаг считается неудачным. В этом случае следует положить yⁱ⁺¹ = yⁱ,

∆ _i = β ∆ _i и перейти к шагу 3.

Шаг 3. Проверить выполнение условий:

а) если i < n, то положить i = i +1 и перейти к шагу 2(сделать шаги по оставшимся направлениям);

б) если i = n, проверить успешность поиска по текущим ортогональным направлениям:

- если f(yⁿ⁺¹) < f(y¹), т.е. хотя бы один спуск по направлению на шаге 2 был успешным, положить y¹ = yⁿ⁺¹, i = 1 и перейти к шагу 2;

- если f(yⁿ⁺¹) = f(y¹), т.е. каждый из n последних шагов был неудачным, оценить успешность поиска на текущей итерации:

-- если f(yⁿ⁺¹) < f(x^k), т.е. на k-ой итерации был хотя бы один удачный шаг, то перейти к шагу 4.

-- если если f(yⁿ⁺¹) = f(x^k), т.е. не было ни одного удачного шага на k-ой итерации, процесс поиска приостановить. Если число l последовательно неудачных серий шагов по всем направлениям на текущей итерации не превышает N, проверить условие окончания, а иначе перейти к шагу 4. Провеяются величиы i, использованные во время последней серии шагов. Если |∆ _i| ≤ е для всех i, то найдено приближённое решение задачи x* = xk. Иначе положить y¹ = yⁿ⁺¹, i = 1 и перейти к шагу 2.

Шаг 4. Положить xk+1 = yn+1 и проверить условие окончания:

а) если ||x^k+1 – x^k|| ≤ е, то поиск завершить х* = x^k+1;

б) если ||x^k+1 – x^k|| > е, вычислить длины шагов по каждому направлению поиска на k-й итерации из соотношения x^k+1 – x^k = ∑ λ _id_i. Далее построить новый набор линейно независимых и взаимно ортогональных направлений поиска с помощью процедуры Грама-Шмидта:

a_i = d_i, при λ _i = 0,

∑ λ _jd_j, j = i, …, n при λ _i ≠ 0,

b_i = a_i, i = 1,

a_i - ∑ (a_i^T_d_j) _d_j, j = 1, …, i-1 при i ≥ 2;

_d_i = b_i/||b_i||

После нахожления новых направлений следует положить: d_i = _d_i, ∆ _i = ∆ _i⁰

для всех i = 1, …n, k = k + 1, y¹ = x^k+1, i =1, и перейти к шагу 2.

Блок-схема

Код программы

#include " stdafx.h"

#pragma hdrstop

#include < stdio.h>

#include < conio.h>

#include < math.h>

#include < locale.h>

#pragma argsused

struct TValue

{

float x;

float y;

};

struct TValue CalculateValue(struct TValue yi, float qi, struct TValue di)

{

struct TValue res;

res.x=yi.x+qi*di.x;

res.y=yi.y+qi*di.y;

return res;

}

float CalculateFunction(struct TValue val)

{

float res;

res=4*((val.x*-5)*(val.x*-5))+(val.y-6)*(val.y-6); //функция Химмельблау

//res=100*((val.y-(val.x*val.x))*(val.y-(val.x*val.x)))+((1-val.x)*(1-val.x)); //функция Розенброка

return res;

}

float CalculateX(struct TValue val1, struct TValue val2)

{

float res;

res=sqrt((val1.x-val2.x)*(val1.x-val2.x)+(val1.y-val2.y)*(val1.y-val2.y));

return res;

}

struct TValue CalculateRaznost(struct TValue val1, struct TValue val2)

{

TValue res;

res.x=val1.x-val2.x;

res.y=val1.y-val2.y;

return res;

}

float CalcKoren(struct TValue b1)

{

return sqrt(b1.x*b1.x+b1.y*b1.y);

}

int main(int argc, char* argv[])

{

setlocale(LC_ALL, " Russian");

struct TValue val;

struct TValue xk[100], d1, d2, y1, y2, y3, X;

float a, b, q01, q02, e, q1, q2, lam1, lam2, end;

int i, N, k=0, n=2, l=0;

float f1, f2;

int direction;

//Вводим начальные условия

printf(" \nПервая точка: ");

xk[k].x=-10;

printf(" \nКоордината по X: \t %f\n", xk[k].x);

xk[k].y=8;

printf(" Координата по Y: \t %f\n", xk[k].y);

e=0.000006;

printf(" Число для остановки алгоритма e> 0: \t %f\n", e);

a=4.6;

printf(" Коэфициент растяжения a> 1: \t %f\n", a);

b=-0.75;

printf(" Коэффициент сжатия -1< b< 0: \t %f\n", b);

d1.x=1; d1.y=0;

printf(" Первое координатное направление: \t %f %f\n", d1.x, d1.y);

d2.x=0; d2.y=1;

printf(" Второе координатное направление: \t %f %f\n", d2.x, d2.y);

q01=1;

printf(" Начальная длина шага по первому направлению: \t %f\n", q01);

q02=2;

printf(" Начальная длина шага по второму направлению: \t %f\n", q02);

N=3;

printf(" Количество неудачных шагов N: \t %d\n", N);

i=1; y1=xk[k]; q1=q01; q2=q02;

direction=1;

STEP2:

if(direction==1)

{

val=CalculateValue(y1, q1, d1);

f1=CalculateFunction(val);

f2=CalculateFunction(y1);

if(f1< f2)

{

y2=val; q1=a*q1;

goto STEP3;

}

else

{

y2=y1; q1=b*q1;

goto STEP3;

}

}

if(direction==2)

{

val=CalculateValue(y2, q2, d2);

f1=CalculateFunction(val);

f2=CalculateFunction(y2);

if(f1< f2)

{

y3=val; q2=a*q2;

goto STEP3;

}

else

{

y3=y2; q2=b*q2;

goto STEP3;

}

}

STEP3:

if(i< n)

{

i=i+1;

if(direction==1) {direction=2; goto STEP2; }

if(direction==2) {direction=1; goto STEP2; }

}

if(i==n)

{

if(CalculateFunction(y3)< CalculateFunction(y1))

{

y1=y3; i=1;

if(direction==1) {direction=2; goto STEP2; }

if(direction==2) {direction=1; goto STEP2; }

}

if(CalculateFunction(y3)==CalculateFunction(y1))

{

if(CalculateFunction(y3)< CalculateFunction(xk[k]))

{

goto STEP4;

}

if(CalculateFunction(y3)==CalculateFunction(xk[k]))

{

l++;

if(l> =N){goto STEP4; }

else

{

if((fabs(q1)< =e)& & (fabs(q2)< =e))

{

X=xk[k];

goto EXIT;

}

if((fabs(q1)> e)||(fabs(q2)> e))

{

y1=y3; i=1;

if(direction==1) {direction=2; goto STEP2; }

if(direction==2) {direction=1; goto STEP2; }

}

}

}

}

}

STEP4:

xk[k+1]=y3;

if(CalculateX(xk[k+1], xk[k])< =e)

{

X=xk[k+1];

}

else

{

TValue raz, a1, a2, b1, b2;

float Koren, b3;

raz=CalculateRaznost(xk[k+1], xk[k]);

lam1=d1.x*raz.x+d1.y*raz.y;

lam2=d2.x*raz.x+d2.y*raz.y;

a1.x=lam1*d1.x+lam1*d1.y; a1.y=lam2*d1.x+lam2*d1.y;

a2.x=lam2*d2.x; a2.y=lam2*d2.y;

b1=a1;

Koren=CalcKoren(b1);

d1.x=b1.x/Koren;

d1.y=b1.y/Koren;

b3=a2.x*d1.x+a2.y*d1.y;

b2.x=a2.x-b3*d1.x;

b2.y=a2.y-b3*d1.y;

q1=q01; q2=q02;

k++;

y1=xk[k]; i=1;

if(direction==1) {direction=2; goto STEP2; }

if(direction==2) {direction=1; goto STEP2; }

}

EXIT:

end=CalculateFunction(X);

printf(" \nИтог");

printf(" \nТочка минимума: ");

printf(" \nx*=x%d=(%f; %f)", k+1, X.x, X.y);

printf(" \nЗначение функции в точке минимума ");

printf(" \nF(x*)=%f\n", end);

printf(" Количество итераций: %d", k+1);

getch();

return 0;

}

Сводная таблица

1) функция Химмельблау №1

2) функция Розенброка:

Используя тестовые функции заполним таблицу.

Выводы

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