Главная
страница 1
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

Государственное образовательное учреждение высшего профессионального образования

НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ

ТОМСКИЙ ПОЛИТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

ИНСТИТУТ КИБЕРНЕТИКИ

Кафедра Информатики и проектирования систем



ОТЧЕТ

по лабораторной работе № 5

по дисциплине Методы оптимизации

Многомерная условная оптимизация

Вариант 3


Выполнил: студент гр. 8В83

Б.А. Сафронов
Проверил: О.В. Березняк

Задание:

Найти минимум функции f(x) с точностью E=10-5.

Применить методы:


  1. Методом градиентного спуска;

  2. Методом Марквардта.

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



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

namespace mo_lb_5

{

class Program



{

bool flag;

double R = 100;

double sigma = 0;

int count_f = 0;
/*

* Функция

*/

double f(double[] x)



{

count_f++;

return 2 * x[0] + x[1];

}
/*

* Ограничение

*/

double g(double[] x)



{

return (x[0] - 4) * (x[0] - 4) + (x[1] - 2) * (x[1] - 2) - 1;

}
/*

* Вспомогательная функция

*/

double Q(double[] x)



{

if (flag)

{

double G = 0.5 * x[2] * (g(x) + Math.Abs(g(x)));



return f(x) + G * G;

}

double s = g(x) + sigma;



if (s < 0) s = 0;

return f(x) + R * (s * s - sigma * sigma);

}
/*

* Производные для метода Марквардта нахождения мининимума безусловной оптимизации

* -------------------------------------------------------------------------------

*/

double dQ(double[] x, int i, double h)



{

x[i] -= h;

double Q1 = Q(x);

x[i] += 2 * h;

double Q2 = Q(x);

x[i] -= h;

return (Q2 - Q1) / (2 * h);

}

double[] dQ(double[] x, double h)



{

double[] d = new double[x.Length];

for (int i = 0; i < d.Length; i++) d[i] = dQ(x, i, h);

return d;

}
double d2Q(double[] x, int i, int j, double h)

{

x[j] -= h;



double dQ1 = dQ(x, i, h);

x[j] += h + h;

double dQ2 = dQ(x, i, h);

x[j] -= h;

return (dQ2 - dQ1) / (h + h);

}
double[,] d2Q(double[] x, double h)

{

double[,] d = new double[x.Length, x.Length];



for (int i = 0; i < x.Length; i++)

for (int j = 0; j < x.Length; j++)

d[i, j] = d2Q(x, i, j, h);

return d;

}
/*

* -------------------------------------------------------------------------------

*/

/*

* Нахождение нормали градиента



*/

double norm(double[] x, double h)

{

double d = 0;



for (int i = 0; i < x.Length; i++)

{
double df1 = dQ(x, i, h);

d += df1 * df1;

}

return Math.Sqrt(d);



}
/*

* Метод Марквардта

*/

public double[] MinOfFun(double[] x, double E, int M)



{

double[] xk = x;

int k = 0;

double lmb = 1000;

double h = .001;

double[] dQk = dQ(xk, h);

double dQkn = norm(xk, h);

double[,] H = d2Q(xk, h);

double[] s = new double[xk.Length];

double a;

double fk, fk1;

while (dQkn > E && k < M)

{

for (int i = 0; i < xk.Length; i++)



H[i, i] += lmb;

for (int i = 1; i < xk.Length; i++)

{

a = H[i, i - 1] / H[i - 1, i - 1];



for (int j = 0; j < xk.Length; j++)

H[i, j] -= a * H[i - 1, j];

dQk[i] -= a * dQk[i - 1];

}

for (int i = xk.Length - 1; i >= 0; i--)



{

s[i] = -dQk[i];

for (int j = i + 1; j < xk.Length; j++)

s[i] -= H[i, j] * s[j];

s[i] /= H[i, i];

}
fk = f(xk);

xk[0] += s[0];

xk[1] += s[1];

fk1 = f(xk);

dQkn = norm(xk, h);

dQk = dQ(xk, h);

H = d2Q(xk, h);


if (fk1 < fk)

{

lmb /= 2;



k++;

continue;

}
lmb *= 2;

k++;


}

return xk;

}
public void StrFun(double[] x0, double r0, int M, double E)

{

flag = true;



count_f = 0;

double[] x = new double[x0.Length + 1];

x0.CopyTo(x, 0);

x[2] = r0;

int k = 0;

do

{



MinOfFun(x, E, M).CopyTo(x, 0);

x[2]++;


k++;

} while (g(x) > 0 && k < M);


Console.WriteLine("X1 = " + x[0] + "X2 = " + x[1]);

Console.WriteLine("F(X) = " + f(x));

Console.WriteLine("Iterations = " + k);

Console.WriteLine("F count = " + count_f);

}
public void FactFun(double[] x0, int M, double E)

{

count_f = 0;



flag = false;

double[] x = new double[x0.Length];

x0.CopyTo(x, 0);

sigma = 0;

int k = 0;

double x11, x21;

double x12, x22;

double s1, s2;

double f1, f2;

double g1, g2;

do

{

x11 = x[0];



x12 = x[1];

s1 = sigma;

f1 = f(x);

g1 = g(x);


MinOfFun(x, E, M).CopyTo(x, 0);

sigma += g(x);


if (sigma < 0) sigma = 0;

k++;
x21 = x[0];

x22 = x[1];

s2 = sigma;

f2 = f(x);

g2 = g(x);

} while (x11 != x21 && x12 != x22 && s1 != s2 && f1 != f2 && g1 != g2 && k < M);
Console.WriteLine("X1 = " + x[0] + "X2 = " + x[1]);

Console.WriteLine("F(X) = " + f(x));

Console.WriteLine("Iterations = " + k);

Console.WriteLine("F count = " + count_f);

}

static void Main(string[] args)



{

Program b = new Program();

double[] x0 = new double[] { 100, 100 };

b.StrFun(x0, 1, 1000, 0.0001);

b.FactFun(x0, 1000, 0.0001);

Console.ReadKey();

}

}

}



Результат работы программы:

X1 = 3,11082011182478

X2 = 1,5424700947918

F(X) = 7,76411031844136

Iterations = 38

F count = 1901825


X1 = 3,10557271295335

X2 = 1,55278673205527

F(X) = 7,76393215796196

Iterations = 7

F count = 79353
Вывод:

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



Метод штрафных функций, использует вспомогательные функции таким образом, чтобы они становились отличными от нуля (положительными) при нарушении соответствующего ограничения. А так как мы движемся в направлении миннимума, то движение в сторону нарушения становится невыгодным, т.е. значение функции увеличивается. Метод факторов, является очень эффективным методом штрафов, основывается на штрафе типа «квадрат срезки» для ограничений-неравенств. Факторы меняются таким образом, что каждый раз штраф за нарушение ограничений возрастает, поэтому происходит быстрое приближение к допустимой области. Исходя из полученных результатов можно сказать, что метод факторов является наиболее эффективным и находит минимум функции за меньшее число итераций.

Томск 2011


Смотрите также:
Отчет по лабораторной работе №5 по дисциплине Методы оптимизации
69.77kb.
1 стр.
Отчет по лабораторной работе №5 по дисциплине электроника
97.38kb.
1 стр.
Отчет по лабораторной работе №5 по дисциплине электроника
119.38kb.
1 стр.
Отчет по лабораторной работе №4 по дисциплине «Операционные системы»
90.67kb.
1 стр.
Отчет по лабораторной работе №8 по дисциплине «Информационно-поисковые системы»
40.89kb.
1 стр.
Отчет о лаботарорной работе методы и средства анализа данных по теме: «Система анализа данных weka»
383.87kb.
2 стр.
Отчет по лабораторной работе №3 по дисциплине «Сети ЭВМ и телекоммуникации»
187.36kb.
1 стр.
Отчет по лабораторной работе №3 «Модели стационарных рядов arma, и нестационарных arima»
55.97kb.
1 стр.
Отчет по лабораторной работе №7 студент 3 курса гр. И-912 Алиева М. И. Проверила : ст
484.17kb.
4 стр.
Методические указания к лабораторной работе №1 «Изучение лабораторного комплекса sdk 1» по дисциплине «Микропроцессорные системы»
50.73kb.
1 стр.
Отчет по лабораторной работе №3 «Модели стационарных рядов arma и нестационарных arima»
21.05kb.
1 стр.
Отчет по лабораторной работе №3 «Модели стационарных рядов arma и нестационарных arima»
36.42kb.
1 стр.