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

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

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

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

1. Нахождение стационарной точки

Шаг 1. Задать:

начальную точку х⁽⁰⁾;

приращение , i = 1,2,...,N;

коэффициент уменьшения шага > 1;

условие окончания поиска.

Шаг 2. Произвести исследующий поиск.

Шаг 3. Был ли исследующий поиск удачным (найдена ли точка с меньшим значением целевой функции)?

Да: перейти к шагу 5;

Нет: продолжить.

Шаг 4. Проверка на окончание поиска: ?

Да: прекратить поиск;

Нет: уменьшить приращение по формуле

, i = 1,2,...,N.

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

Шаг 5. Провести поиск по образцу (формула (4)).

Шаг 6. Провести исследующий поиск, используя в качестве базовой точки; пусть х^(k+1) полученная в результате точка.

Шаг 7. Выполняется ли f()<f (х^(k))?

Да: положить х^{(k -1)} = х^(k); х^(k) = х^(k+1); перейти к шагу 5;

Нет: перейти к шагу 4.

Задача

Минимизировать методом поиска Хука-Дживса.

Условие окончание поиска: момент второго сокращения шага поиска.

Решение.

Dх - векторная величина приращенияDх = 2;

a - коэффициент уменьшения шага.a--=--2;

e - минимальное значение приращения б, при котором ещё стоит искать минимум.

В условиях данной задачи ограничимся значением б =2, т.е. будем искать минимум до первого уменьшения приращения.

Будем искать минимум до первого уменьшения приращения.

f(x)=(x₁-9)²+(x₂-2)²+x₁x₂.

х⁽⁰⁾=[-9;-10]^T , f(x⁽⁰⁾)=558.

Исследующий поиск вокруг базовой точки х⁽⁰⁾:

фиксируя х₂, даём приращение переменной х₁:

х₂=-10;х₁=-9+2=-7; f(-7;-10) =470<558 удача;

фиксируя х1, даём приращение переменной х2:

х₁=-7; х₂=-10+2=-8; f(-7;-8) =412<470удача;

х⁽¹⁾ = [-7;-8]^T;f(x⁽¹⁾)=412;

Т.к. поиск был удачным, переходим к поиску по образцу:

х_p⁽²⁾ = 2*х⁽¹⁾ - х⁽⁰⁾;х_p⁽²⁾ = [-5;-6]^T;f(x_p⁽²⁾) =290<412;

Исследующий поиск вокруг точки х_p ⁽²⁾:

фиксируя х₂, даём приращение переменной х₁:

х₂=-6;х₁=-5+2=-3;f (-3;-6)=226<290удача;

фиксируя х1, даём приращение переменной х2:

х₁=-3; х₂=-6+2=-4;f (-3;-4)=192<226удача;

х⁽²⁾ = [-3;-4]^T;f(x⁽²⁾)=192;

Т.к. поиск был удачным, переходим к поиску по образцу:

х_p ⁽³⁾ = 2*х⁽²⁾ - х⁽¹⁾;х_p ⁽³⁾ = [1;0]^T f(x_p⁽³⁾) =68<192;

Исследующий поиск вокруг точки х_p ⁽³⁾:

фиксируя х₂, даём приращение переменной х₁:

х₂=0;х₁=1+2=3 ; f (3;0)= 40<68удача;

фиксируя х₁, даём приращение переменной х₂:

х1=3; х2=0+2=2 ;f (3;2)= 42<40неудача;

х1=3; х2=0-2=-2; f (3;-2)= 46<40неудача;

х⁽³⁾ = [3;0]^T;f(x⁽³⁾)=40;

Т.к. поиск был удачным, переходим к поиску по образцу:

х_p ⁽⁴⁾ = 2*х⁽³⁾ - х⁽²⁾;х_p ⁽⁴⁾ = [9;4]^T;f (х_p ⁽⁴⁾)=40=40;

Значение целевой функции не изменилось, поэтому возьмём последнюю точку за временную базовую и проведём исследующий поиск.

Исследующий поиск вокруг точки х ⁽³⁾:

х⁽³⁾ = [3;0]^T;f(x⁽³⁾)=40;

фиксируя х₂, даём приращение переменной х₁:

х₂=0;х₁=3+2=5 ;f (5;0)= 20<40 удача;

фиксируя х₁, даём приращение переменной х₂:

х₁=5; х₂=0+2=2;f (5;2)=26>20неудача;

х₁=5; х₂=0-2=-2;f (5;-2)=22>20неудача;

х⁽⁴⁾ = [5;0]^T;f(x⁽⁴⁾)=20;

Т.к. поиск был удачным, переходим к поиску по образцу:

х_p ⁽⁵⁾ = 2*х⁽⁴⁾ - х⁽³⁾;х_p ⁽⁵⁾ = [7;0]^T; f (х_p ⁽⁵⁾)=8<20;

5. Исследующий поиск вокруг точки х_р ⁽⁵⁾:

фиксируя х₂, даём приращение переменной х₁:

х₂=0;х₁=7+2=9 ;f (9;0)= 4<8 удача;

фиксируя х₁, даём приращение переменной х₂:

х₁=9; х₂=0+2=2; f (9;2)=18>8 неудача;

х₁=9; х₂=0-2=2; f (9;-2)=-2<8 удача;

х⁽⁵⁾ = [9;-2]^T;f(x⁽⁵⁾)=-2;

Т.к. поиск был удачным, переходим к поиску по образцу:

х_p ⁽⁶⁾ = 2*х⁽⁵⁾ - х⁽⁴⁾;х_p ⁽⁶⁾ = [13;-4]^T ;f(х_p ⁽⁶⁾) =0>-2;

Значение целевой функции увеличилось, поэтому возьмём последнюю точку за временную базовую и проведём исследующий поиск, при этом изменим значение б=1.

6. Исследующий поиск вокруг точки х ⁽⁵⁾:

х⁽⁵⁾ = [9;-2]^T;f(x⁽⁵⁾)=-2;

фиксируя х₂, даём приращение переменной х₁:

х₂=-2;х₁=9+1=10; f (10;-2)= -3<-2 удача;

x₁=10;x₂=-2+1=-1;f (10;-1)=0>-3 неудача;

фиксируя х₁, даём приращение переменной х₂:

х₁=10;х₂=-2-1=-3; f (9;0)=-4<-3 удача;

х⁽⁶⁾ = [10;-3]^T;f(x⁽⁶⁾)=-4.

Т.к. поиск был удачным, переходим к поиску по образцу:

х_p ⁽⁷⁾ = 2*х⁽⁶⁾ - х⁽⁵⁾;х_p ⁽⁷⁾ = [11;-4]^T; f(х_p ⁽⁷⁾) =-4-неудача;

Изменим б=0,5.

х⁽⁶⁾ = [10;-3]^T;

х₂=-3; х₁=10+0,5=10,5;f (10,5;-3)=-4,25<-4=>удача;

х₁=10,5; х₂=-2,5;f (10,5;-2,5)=3,75>4.25=>неудача.

х⁽⁷⁾ = [10,5;-3]^T.

В результате исследующего поиска не было достигнуто уменьшение значения целевой функции, то есть значение шага (векторной величины приращения) уменьшить в раз, до величины , затем необходимо произвести исследующий поиск вокруг точки х⁽⁷⁾ = [10,5;-3]^T, используя новое значение приращения . Итерации продолжаются, пока величина шага не укажет на окончание поиска в окрестности точки минимума.

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

Графическое приложение к методу Хука-Дживса:

Метод сопряженных направлений Пауэлла

Метод относится к категории теоретических методов оптимизации. Метод ориентирован на решение задач с квадратичными целевыми функциями. Основная идея алгоритма заключается в том, что если квадратичная функция N переменных приведена к сумме квадратов, то ее оптимум может быть найден в результате реализации N одномерных поисков по преобразованным координатным (сопряженным) направлениям. Сопряженные направления определяются алгоритмически. Для нашего двумерного случая реализация метода требует три одномерных поиска. Для нахождения экстремума квадратичной функции N переменных необходимо выполнить N² одномерных поисков.

Алгоритм метода:

Шаг 1. задать исходные точки х⁽¹⁾, х⁽²⁾ и направление d. В частности, направление d может совпадать с направлением координатной оси;

Шаг 2. произвести одномерный поиск из точки х⁽¹⁾ в направлении d и получить точку y⁽¹⁾, являющуюся точкой экстремума на заданном направлении;

Шаг 3. произвести поиск из точки х⁽²⁾ в направлении d и получить точку y⁽²⁾;

Шаг 4. вычислить направление (y⁽²⁾ - y⁽¹⁾);

Шаг 5. провести одномерный поиск из точки у⁽¹⁾ (либо у⁽²⁾) в направлении (y⁽²⁾ - y⁽¹⁾) с выходом в точку х^*.

Решение

Исходные данные:

Шаг 1.

- начальная точка

, .

Шаг 2.

а) Найдем значение , при котором минимизируется в направлении :

Откуда ; .

Значение функции в этой точке:

.

Продифференцируем полученное выражение по , получим:

.

Приравняв его к нулю, находим ;

Получили

б) Аналогично находим значение минимизирующее функцию в направлении :

Откуда ; .

Значение функции в этой точке:

.

Продифференцируем полученное выражение по , получим:

.

Приравняв его к нулю, находим ;

Получили

в) Найдем значение минимизирующее :

Откуда ; .

Значение функции в этой точке:

.

Продифференцируем полученное выражение по , получим:

.

Приравняв его к нулю, находим ;

Получили

Шаг 3.

Шаг 4.

Найдем такое значение , при котором минимизируется в направлении .

Откуда ; .

Значение функции в этой точке:

.

Продифференцируем полученное выражение по , получим:

.

Приравняв его к нулю, находим ;

Получили

Таким образом, получили точку , значение функции в которой примерно равно , которая почти совпадает со стационарной точкой.

Графическое пояснение метода сопряженных направлений Пауэлла:

Методы прямого поиска являются удобными при простых целевых функциях, или когда необходимо найти оптимум с невысокой степенью точности. Но требуют больших затрат времени и вычислительных ресурсов, из-за большого числа проводимых итераций: метод поиска по симплексу - 14 итераций, метод Хука-Дживса - 6 итераций, метод сопряженных направлений Пауэлла - 4 итерации.

3. Градиентные методы поиска экстремума функции

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

Простейший градиентный метод

Описание простейшего градиентного метода

f(x1,x2)= (х1 - 9)² + (х2 - 2)² +х1*х2.

Находим градиентную составляющую:

?f/?x1=2*x1 + x2 - 18; ?f/?x2=x1 + 2*x2 -4;

1. Шаг: Задаем начальные данные:

х⁽⁰⁾ = [-9;-10]^Т; б =0,3;

2. Шаг:

1 итерация: х⁽¹⁾ = х⁽⁰⁾ - б *f (x⁽⁰⁾ ) ;

f (x⁽⁰⁾ ) = [-46;-33]^T; х⁽¹⁾ = [-9;-10]^Т -0,3[-46;-33]^T=[4,8;-0,1]^T.

2 итерация:

х⁽²⁾ = х⁽¹⁾ - б *f (x⁽¹⁾ ) ;

f (x⁽²⁾ ) = [-8,5;-0,6]^T; х⁽²⁾ = [4,8;-0,1]^T -0,3[-8,5;-0,6]^T =[7,35;0,08]^T.

3 итерация: х⁽³⁾ = х⁽²⁾ - б *f (x⁽²⁾ ) ;

f (x⁽³⁾ ) = [-3,22;3,51]^T; х⁽³⁾ = [7,35;0,08]^T -0,3[-3,22;3,51]^T =[8,316;-0,973]^T.

4 итерация: х⁽⁴⁾ = х⁽³⁾ - б *f (x⁽³⁾ ) ;

f (x⁽⁴⁾ ) = [-2,341;2,37]^T; х⁽⁴⁾ = [8,316;-0,973]^T -0,3[-2,341;2,37]^T =[9,0183;-1,684]^T.

5 итерация: х⁽⁵⁾ = х⁽⁴⁾ - б *f (x⁽⁴⁾ ) ;

f (x⁽⁵⁾ ) = [-1,6466;1,6507]^T; х⁽⁵⁾ = [9,0183;-1,684]^T -0,3[-1,6466;1,6507]^T =[9,51;-2,18]^T.

6 итерация: х⁽⁶⁾ = х⁽⁵⁾ - б *f (x⁽⁵⁾ ) ;

f (x⁽⁶⁾ ) = [-1,15465;1,15386]^T; х⁽⁶⁾ =[9,51;-2,18]^T -

-0,3[-1,15465;1,15386]^T =[9,856;-2,526]^T.

7 итерация: х⁽⁷⁾ = х⁽⁶⁾ - б *f (x⁽⁶⁾ ) ;

f (x⁽⁷⁾ ) = [-0,814;0,804]^T; х⁽⁷⁾ =[9,856;-2,526]^T -0,3[-0,814;0,804]^T =[10,1;

-2,767]^T.

8 итерация: х⁽⁸⁾ = х⁽⁷⁾ - б *f (x⁽⁷⁾ ) ;

f (x⁽⁸⁾ ) = [-0,567;0,566]^T; х⁽⁸⁾ =[10,1;-2,767]^T -0,3[-0,567;0,566]^T; =[10,27;-2,94]^T.

После выполнения 8 итераций получено решение х* = х⁽⁸⁾, при котором значение целевой функции f*=-4,0921.

Графическое представление простейшего градиентного метода

Описание метода Коши

Однако вблизи экстремума скорость сходимости алгоритма становится недопустимо низкой, так как вблизи экстремума значение градиента стремится к нулю.

В случае, когда матрица Гессе положительно определена, то направление поиска по методу Ньютона оказывается направлением спуска.

Нахождение минимума целевой функции методом Ньютона:

Vf(x) = Vg(x) = Cx + b = g(x).

Изменение градиента при переходе от точки х⁽⁰⁾ к точке х⁽¹⁾:

Дg(x) = g(x⁽¹⁾) - g(x⁽⁰⁾) = C(x⁽¹⁾ - x⁽⁰⁾);

Дg(x) = CДx.

Изменения аргумента:

x^-(k+1) = x^(k) - б^(k)s(x^(k)).

Направление поиска:

s^(k) = -g^(k) + ? г⁽ⁱ⁾ s⁽ⁱ⁾ , s⁽⁰⁾ = -g⁽⁰⁾, г⁽ⁱ⁾ = ;

s^(k) = -g^{(k) +} *s^(k+1) (формула Флетчера-Ривса)

Нахождение минимума целевой функции методом сопряжённых градиентов:

Решение

Исходные данные:

Шаг 1.

- начальная точка;

Шаг 2.

Поиск вдоль прямой:

Шаг 3.

Определим направление :

Поиск вдоль прямой:

;

.

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

Графическое приложение к методу сопряжённых градиентов:

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

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

x^(k+1) = x^(k) + ^(k)s^(k) .

Направление поиска определяется выражением

s^(k) = -A^(k)(X^(k)),

где A^(k) - матрица порядка NN.

Матрица A - вычисляется по формуле

A^(k) = A^(k-1) +A_c^(k-1),

где

A_c^(k-1) = ; (1)

где g^(k) = g^(k) - g^(k-1) изменение градиента на предыдущем шаге.

Нахождение минимума целевой функции Квазиньютоновским методом:

Описание алгоритма:

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

Направление поиска определяется выражением:

,

где - матрица порядка (метрика).

Матрица - вычисляется по формуле.

,

где:

(1)

Где изменение градиента на предыдущем шаге.

Данный алгоритм отличается устойчивостью, так как обеспечивает убывание целевой функции от итерации к итерации.

Алгоритм метода:

Шаг 1. Задать: начальную точку х⁽⁰⁾. Перейти к шагу 2.

Шаг 2. Вычислить направление поиска s^(k). Перейти к шагу 3.

Шаг 3. Произвести поиск вдоль прямой . Перейти

к шагу 4.

Шаг 4. Проверка условия окончания поиска.

Да: закончить поиск;

Нет: перейти к шагу2.

Решение:

f(x) = x1² - 18*x1 + x2 ² - 4*x2 +85+ x1*x2;

x⁽⁰⁾ = [-9;-10]^T;

?f/?x1=2*x1 + x2 -18; ?f/?x2=x1 + 2*x2 -4;

ШАГ 1:

f(x) = [2*x1 + x2 -18; x1 + 2*x2 -4]^T;

f(x⁽⁰⁾ ) = [-46;-33]^T;

Положим s⁽⁰⁾ = -f(x⁽⁰⁾ ) = [46;33]^T;

ШАГ 2:

Поиск вдоль прямой:

х⁽¹⁾ = х⁽⁰⁾ - a^???*f(x⁽⁰⁾ ) a^(_)--= 0.343;

х⁽¹⁾ = [-9;-10]^Т - 0.343 *[-46;-33]^T = [5,778; 1,29]^T;

ШАГ 3:

А⁽⁰⁾ = Е =

х⁽⁰⁾ = [5,778; 1,29]^T - [-9;-10]^T = [14,778; 11,29]^T;

g⁽⁰⁾ = g⁽¹⁾ - g⁽⁰⁾ = [-0,65; 0,68]^T - [-46;-33]^T = [45.35; 32.32]^T;

А⁽¹⁾ = A⁽⁰⁾ + A_c⁽⁰⁾;

s⁽¹⁾ = - A⁽¹⁾*g⁽¹⁾;

s⁽¹⁾ = [5,981; -6,987]^T;

ШАГ 4:

Поиск вдоль прямой:

х⁽²⁾ = x⁽¹⁾ + ⁽¹⁾s⁽¹⁾ =[5,778; 1,29]^T+⁽¹⁾ [5,981; -6,987]^T;

⁽¹⁾ =1.003;

x⁽²⁾ = [10,667;-3.333]^Т;

Точность метода позволяет уже на четвертом шаге считать текущую точку точкой-экстремумом. Т.е. х* = х⁽²⁾ = [10,667;-3.333]^Т; f(x*) =-4,333.

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

Графическое приложение к квазиньютоновскому методу:

Поиск условного экстремума

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

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

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

min f (x), ХR^N ;

при ограничениях

g_j (x) ? 0;

h_k(x) = 0, k = 1...K;

то преобразованная задача имеет вид:

P(x,R) = f(x) + [R, h(x),g(x)];

где - штрафная функция от ограничений задачи, а R - штрафной пара-метр. Наличие штрафного параметра R вызвано тем, что введение штрафной функции сильно деформирует поверхность целевой функции, что, в свою очередь, приводит к ухудшению обусловленности преобразованной задачи. Поэтому параметр R служит “регулятором” веса штрафной составляющей в целевой функции, и процесс решения задачи разбивается на ряд вспомогательных задач с различными значениями параметра R и контролем сходимости их решений.

Виды штрафов

Квадратичный штраф имеет вид = R{h(x)}². Этот вид штрафов используется для учёта ограничений-равенств. Функция непрерывна и имеет непрерывную производную, откуда следует, что если непрерывны и дифференцируемые f(x) и h(x), то стационарную точку можно найти ана-литически.

Логарифмический штраф

= - Rln(g(x));

Этот штраф положителен для всех х таких, что 0 < g(x) <1, и отрицателен при g (x) > 1. Логарифмический штраф - это барьерная функция, неопределённая в точках, где g (x) < 0. Поэтому на начальном этапе поиска, когда значение шага поиска велико, необходимо обеспечить защиту процедуры от попадания рабочей точки в недопустимую область.

Штраф, заданный обратной функцией

= R*1/g(x);

Как и предыдущий штраф, является барьерным. В допустимой области вблизи границы значение штрафа быстро убывает при продвижении внутрь допустимой области. На самой границе значение P(x,R) неопределено, как и в предыдущем случае возможно появление недопустимых точек.

Штраф типа квадрата срезки

= R*<g(x)>²,

б, если б ? 0,

< б > =

0,если б > 0.

Этот штраф является внешним, и недопустимые точки не создают проблем по сравнению с допустимыми. Различие заключается в том, что в допустимых точках штраф равен нулю. Этот вид штрафа удобен тем, что P(x,R) непрерывна и определена всюду. Параметр R положителен и увеличивается от итерации к итерации.

Задача

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

Нахождение минимума целевой функции :

Исходные данные:

f(x)=(x₁-9)²+(x₂-2)²+x₁x₂.

х⁽⁰⁾=[-9;-10]^T ;

Ограничение на решение:

h(x) = -5x1 +12x2 +120 = 0;

Преобразуем целевую функцию введением в неё заданного квадратичного штрафа: -0,5x1 +1,2x2 +12=0;

P(x,R) = f(x1,x2) = (x1-9)^2+(x2-2)^2+x1x2+(1/R)( -5x1 +12x2 +120 )^2;

Найдем минимум целевой функции с заданным квадратичным штрафом:

Совместное решение даёт:

Устремляя к нулю, получаем

То есть, при изменении от нуля до бесконечности, решение будет изменяться от минимума задачи с учётом ограничений до минимума функции без учёта ограничений.

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

1. ;

;

2. ;

;

.

3. ;

;

.

4. ;

;

.

Сведем все данные в таблицу:

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

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

Графическое приложение к методу штрафных функций:

оптимизация функция градиентный

Выводы

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

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

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

Заключение

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

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

Библиографический список литературы