Методы штрафных и барьерных функций

Размещено на http://www.allbest.ru/

Отчет по лабораторной работе

По курсу:

«Теория оптимального планирования и управления»

«Методы штрафных и барьерных функций»

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

1. Алгоритм метода штрафных функций

0. Выбрать > 0 в качестве критерия остановки. Выбрать начальную точку x₁, штрафной параметр М₁ > 0, число В > 1.

к = к + 1.

1. При начальной точке x_к решить следующую задачу:

минимизировать F(x) + M_k*A(x) при условии x X.

Положить x_k+1 равным оптимальному решению этой задачи и перейти к шагу 2.

2. M_k*A(x_k+1) < ?

да: остановка

нет: M_k+1 = В* M_k

к = к + 1 и перейти к шагу 1.

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

1) Построение вспомогательной функции.

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

2) Проверка неограниченности оптимального решения при различных µ: (1; 10; 100):

а) µ=1:



б) µ=10:



в) Проведение анализа при значении весового коэффициента штрафа µ=100 невозможно в силу того, что не обеспечивается сходимость процедуры поиска оптимального решения. При неоправданно большом (что, собственно, так и есть, в данном случае) значении весового коэффициента штрафа решение вспомогательной задачи приведет быстро в точку, близкую к допустимому множеству исходной задачи, которая может находиться далеко от точки оптимума. В этом случае алгоритм безусловной оптимизации (метод Флетчера-Ривса, в нашем случае) не сможет в дальнейшем делать большие шаги, т.к. при движении в направлении допустимых точек с лучшими значениями целевой функции вспомогательной задачи может оказаться возрастающей. Поэтому в качестве 3-го значения µ было выбрано µ=50:



3) Добавить к задаче ограничения: и, и найти оптимальное решение для этого случая:

Для начальных данных:



4) Найти оптимальное решение задачи для нескольких начальных точек:

а) Начальная точка (3; 1):



б) Начальная точка (-1; 3):

2. Листинг программной реализации

#include<iostream>

#include<conio.h>

#include<stdio.h>

#include<math.h>

#include<windows.h>

#define size 2

using namespace std;

double func (double X[2], double mu1);

void grad_func (double X[2], double Grad[2], double mu1);

double norm (double ptr[2]);

void fletcher_rivs (double eps, double mu1, double X[2]);

double gold_sech (double S[2], double Y[2], int j, double mu1);

int main() {

char cStr[50];

double eps, b, mu1;

double usl;

double X[size];

double X1 [size];

int k=0;

FILE *f1;

X1 [1]=0;

X1 [0]=0;

f1 = fopen («shtraf.txt», «wb»);

system («cls»);

CharToOem (L «Введите погрешность:», cStr);

cout<<cStr;

cin>>eps;

CharToOem (L «Введите значение весового коэффициента штрафа:», cStr);

cout<<cStr;

cin>>mu1;

CharToOem (L «Введите параметр корректировки:», cStr);

cout<<cStr;

cin>>b;

for (int i =0; i<size; i++)

{

cout<< «X [» << i <<»] =»; cin>> X[i];}

CharToOem (L «Начальная точка:», cStr);

fprintf (f1, «%s (%.5f, %.5f)\r\n», cStr, X[0], X[1]);

CharToOem (L «Начальный коэффициент штрафа:», cStr);

fprintf (f1, «%s%.5f\r\n», cStr, mu1);

CharToOem (L «Параметр корректировки:», cStr);

fprintf (f1, «%s%.5f\r\n\r\n», cStr, b);

usl=2;

while (usl>=eps)

{

k+=1;

fletcher_rivs (eps, mu1, X);

mu1*=b;

X1 [0]=X[0];

X1 [1]=X[1];

usl=((X1 [0]+X1 [1] - 1)*(X1 [0]+X1 [1] - 1));

CharToOem (L «Номер итерации (к):», cStr);

fprintf (f1, «%s % d\r\n», cStr, k);

CharToOem (L «Значение коэффициента:», cStr);

fprintf (f1, «%s%.5f\r\n», cStr, mu1);

CharToOem (L «Координаты текущей точки (Xk):», cStr);

fprintf (f1, «%s (%.5f, %.5f)\r\n», cStr, X1 [0], X1 [1]);

CharToOem (L «Значение функции в текущей точке (F(Xk)):», cStr);

fprintf (f1, «%s%.5f\r\n», cStr, func (X1, mu1));

CharToOem (L «Значение штрафа за нарушения ограничения:», cStr);

fprintf (f1, «%s%.5f\r\n», cStr, usl/mu1);

CharToOem (L «Значение штрафной функции:», cStr);

fprintf (f1, «%s%.5f\r\n», cStr, usl+func (X1, mu1));

CharToOem (L «Значение условия остановки:», cStr);

fprintf (f1, «%s%.5f\r\n\r\n», cStr, usl);

}

CharToOem (L»\nРезультаты в файле shtraf.txt корневой папки», cStr);

fclose(f1);

cout<<cStr;

getch();

return 0;

}

double func (double X[2], double mu1)

{

double funct;

funct =X[0]*X[0]*X[0]+X[1]*X[1]*X[1]+(mu1)*(X[0]+X[1] - 1)*(X[0]+X[1] - 1);

return funct;

}

void grad_func (double X[2], double Grad[2], double mu1)

{

Grad[0] =3*X[0]*X[0]+2*(mu1)*(X[0]+X[1] - 1);

Grad[1] = 3*X[1]*X[1]+2*(mu1)*(X[0]+X[1] - 1);

}

double norm (double ptr[2])

{

double help = 0;

for (int i = 0; i<size; i++)

help = help + pow (ptr[i], 2);

help = pow (help, 0.5);

return help;

}

double gold_sech (double S[2], double Y[2], int j, double mu1) {

const double alpha = 0.618;

double func_lymb, func_mu;

double L, a, b;

double X[2] = {0, 0};

double mu = 0, lymb = 0;

int k = 0;

a = -0.1;

b = 0.1;

L = 0.1;

lymb = a + (1 - alpha) * (b - a);

mu = a + alpha * (b - a);

for (int i = 0; i <= (size-1); i++)

X[i] = Y[i];

X[j] = Y[j] + lymb * S[j];

func_lymb = func (X, mu1);

for (int i = 0; i <= (size-1); i++)

X[i] = Y[i];

X[j] = Y[j] + mu * S[j];

func_mu = func (X, mu1);

while ((b-a)>=L)

{

k++;

if (func_lymb>func_mu) {

a = lymb;

lymb = mu;

mu = a + alpha * (b - a);

func_lymb = func_mu;

X[j] = Y[j] + mu * Y[j];

func_mu = func (X, (mu1));

}

else {

b = mu;

mu = lymb;

lymb = a + (1 - alpha) * (b - a);

func_mu = func_lymb;

X[j] = Y[j] + lymb * S[j];

func_lymb = func (X, (mu1));

}

}

return ((b+a)/2);

}

void fletcher_rivs (double eps, double mu1, double X[2])

{

double Y[size];

double S[size];

double help_gr[size];

double lymb;

int k = 1;

int j = 1;

bool trace = true;

double alf;

FILE *f;

char cStr[50];

for (int i =0; i<size; i++)

{

Y[i] = X[i];

}

k=0;

grad_func (X, S, (mu1));

for (int i =0; i<size; i++)

S[i] = - S[i];

f = fopen («fletcher.txt», «ab»);

while (norm(S) >= eps)

CharToOem (L «Номер итерации (к):», cStr);

fprintf (f, «%s % d\r\n», cStr, k);

CharToOem (L «Координаты текущей точки (х):», cStr);

fprintf (f, «%s (%.5f, %.5f)\r\n», cStr, X[0], X[1]);

CharToOem (L «Значение функции в текущей точке:», cStr);

fprintf (f, «%s%.5f\r\n\r\n», cStr, func (X, mu1));

CharToOem (L «Значение кэффициента:», cStr);

fprintf (f, «%s%.5f\r\r\n», cStr, mu1);

trace = false;

}

lymb = gold_sech (S, Y, j-1, (mu1));

grad_func (Y, help_gr, (mu1));

if (j == 1)

fprintf (f, «j\t\t y(j) \t\t F (y(j)) \t grF (y(j)) \t\t ||grF (y(j))|| \t alfa(j) \t\t Dj \t\t Lymbdaj \t\t y (j+1)\r\n»);

fprintf (f, «%d\t (%.5f, %.5f)\t%.5f \t (%.5f, %.5f) \t\t%.5f\t», j, Y[0], Y[1], func (Y, mu1), help_gr[0], help_gr[1], norm (help_gr));

if (j == 1)

fprintf (f, "\t -\t»);

else

fprintf (f, "\t%.5f\t», alf);

fprintf (f, "\t (%.5f, %.5f)\t % f \t», S[0], S[1], lymb);

Y [j-1] = Y [j-1] + lymb * S [j-1];

fprintf (f, "(%.5f, %.5f)\r\n», Y[0], Y[1]);

if (j < size) {

grad_func (Y, help_gr, mu1);

alf = pow (norm(help_gr), 2)/pow (norm(S), 2);

S [j-1] = - help_gr [j-1] + alf * S [j-1];

j++;

} else {

for (int i = 0; i < size; i++)

X[i] = Y[i];

grad_func (Y, S, mu1);

for (int i =0; i<size; i++)

S[i] = - S[i];

k++;

j = 1;

trace = true;

}

}

CharToOem (L «Номер итерации (к):», cStr);

fprintf (f, «%s % d\r\n», cStr, k);

CharToOem (L «Координаты текущей точки (х):», cStr);

fprintf (f, «%s (%.5f, %.5f)\r\n», cStr, X[0], X[1]);

CharToOem (L «Значение функции в текущей точке:», cStr);

fprintf (f, «%s%.5f\r\n\r\n», cStr, func (X, mu1));

fclose(f);

}

Выводы

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

Было замечено, что значение интервала неопределенности сильно влияет на результат работы алгоритма. При большом значении длины интервала неопределенности происходит «скачок» за границу ограничений, что не дает алгоритму достичь оптимального решения. Это объясняется прямой зависимостью шага в методе Флетчера и Ривса от исходного интервала неопределенности в методе золотого сечения.

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

штрафной оптимизация программа флетчер

Приложение

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

При начальном ограничении:

Начальная точка (0; 1)
µ	Оптимальная точка	Значение функции	Число итераций
1	(0.45923; 0.4606)	0.24598	3
10	(0.48011; 0.48498)	0.24912	1
50	(0.4831; 0.5079)	0.25075	1

При измененном ограничении:

µ=1
Начальная точка	Оптимальная точка	Значение функции	Число итераций
(0; 1)	(0.54812; 0.55034)	1.14414	1
(3; 1)	(0.55025; 0.5492)	1.14324	1
(-1; 2)	(0.54688; 0.54934)	1.14616	1

Размещено на Allbest.ru