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

Содержание

1. Математические постановки задачи оптимизации

2. Причины разнообразия формулировок задач оптимизации

3. Безусловная оптимизация

4. Одномерная безусловная оптимизация

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

6. Методы условной оптимизации

7. Линейное программирование

8. Нелинейное программирование

9. Понятие о численных методах оптимизации

10. Прямые методы

11. Методы поиска нулевого, первого и второго порядков

12. Пассивные и активные (последовательные) методы поиска

13. Конечношаговые и бесконечношаговые методы поиска.

14. Сходимость методов

!15. Скорость сходимости(м.б. см 14)

16. Критерии останова методов поиска

17. Теорема существования решения оптимизационной задачи (формулировка) (Т. Вейерштрасса)

18. Необходимые условия экстремумов первого и второго порядков

19. Достаточные условия экстремума (гладкие функции одной переменной и многих переменных)

20. Безусловная оптимизация

21. Лемма о свойствах унимодальной функции

22. Понятие об эффективности поиска

23. Принцип минимакса

24. Оптимальные и дельта- оптимальные методы поиска

25. Пассивный метод поиска экстремума(+см.26)

26. Алгоритм пассивного поиска

27. Теорема об оптимальности пассивного поиска

28. Последовательные методы поиска экстремума

29. Блочные методы поиска экстремума (четные и нечетные размеры блока)

30(+см29). Об эффективности блочных методов

31. Метод дихотомии

32. Метод деления отрезка пополам

33. Метод золотого сечения

34. Метод чисел Фибоначчи

35. Теорема об эффективности последовательных методов

36. Метод касательных

37. Метод парабол

38. Методы спуска

39. Метод конфигураций

40. Метод симплекса

41. Метод деформируемого симплекса

42. Градиент

43. Об ортогональности градиента к линии уровня целевой функции

44. Градиент и направление роста целевой функции

45. Градиентные методы

46. Градиентный метод с постоянным шагом

47. Градиентный метод с дроблением шага

48. Метод наискорейшего спуска

49. Характер движения в методе наискорейшего спуска

50. Овражные методы спуска

51. Эвристические схемы

52. Методы покоординатного спуска

53. Метод покоординатного спуска с постоянным шагом

54. Метод Гаусса-Зейделя

55. Методы Ньютона

56. Геометрическая интерпретация метода Ньютона

57. Методы Ньютона с регулировкой шага(Ньютона-Рафсона )

58. Метод Ньютона-Рафсона с регулировкой шага

59. Метод Ньютона-Рафсона с оптимальным шагом

60. Модификации метода Ньютона(первая и вторая)

61. Общая, стандартная и каноническая формы лин. прогр.(ЗЛП)

62. Переход от общей ЗЛП к стандартной и канонической

63. Переход от стандартной форме к канонической и обратно

64. Геометрическая интерпретация стандартной формы ЗЛП и ее графическое решение

65. Теорема о выпуклости множества допустимых решений ЗЛП (стандартной и канонической форм)

66. Теорема о глобальности экстремума ЗЛП

67. Теорема о том, что экстремум ЗЛП может находиться только на границе множества допустимых решений.

68. Угловая точка множества

69. Т-ма о наличии среди оптимальных решений ЗЛП угловых точек множества допустимых решений

70. Общее представление допустимых решений ЗЛП канонической формы.

71. Базисное решение ЗЛП

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

73. Выражение целевой функции через свободные переменные

74. Критерий оптимальности

75. Симплекс-алгоритм

76. Поиск исходного допустимого базисного решения

77. Симлекс-метод

78. Вырожденное допустимое базисное решение и проблемы, связанные с ним (нет окончания).

79. Взаимно-двойственные ЗЛП

80. 1-я теорема двойственности

81. 2-я теорема двойственности

82. 3-я теорема двойственности(формулировка)

83. Экономическая интерпретация решения двойственной задачи

84. Двойственная задача к ЗЛП в канонической форме

85. Формулирование задачи нелинейного программирования

86. Особенности задач нелинейного программирования

87. Метод множителей Лагранжа

88. Выпуклые функции

89. Выпуклое программирование

90. Теорема о множестве допустимых решений задачи ВП

91. Теорема о глобальности экстремума в задаче

92. Функция Лагранжа в задаче ВП

93. Седловая точка функции Лагранжа

94. Теорема Куна-Таккера(формулировка)

95. Критерий силовой точки для гладких функций Лагранжа(формулировка)

96. Транспортная задача в матричной постановке

97. Сбалансированная и несбалансированная транспортные задачи.

98. Решение транспортной задачи методом потенциалов

математический транспортный задача экстремум

1. Математические постановки задачи оптимизации

1.f(x) -> min(max): найти значение x, который явл min (max) критерия f.

{x^*=arg min f(x) x€A

{ x^*=arg max f(x) x€A

2.min g(x) x€A

Найти значение x, который явл min (max) критерия g.

inf g(x) x€A - нижняя грань.

sup g(x) x€A - верхняя грань.

Если ф-ия достигает своей нижней (верхней) грани, то это есть min (max).

Верхняя и нижняя грань есть всегда, а min и max - нет.

Способ перехода от задачи min к задачи max и наоборот.

g(x^*)=-f(x^*) max f(x^*)=min(-f(x^*))=min g(x^*).

Где x- одна из альтернатив, А- мн-во альтернатив

2. Причины разнообразия формулировок задач оптимизации

1.хар-ка множество альтернатив:

конечное число- самое простое- перебор решений.

счетное мн-во - мн-во альтернатив бесконечно. Каждому элементу можно присвоить номер.

континуальное мн-во - нельзя пронумеровать.

2. Целевая функция

количественная

качественная(часто)

3. Размерность оценки

одномерная - критерий хар-ся одним числом

многомерная - набором чисел

4.что из себя представляет критерий:

4'. м.б. числовым, качественным

скалярный - значением критерия явл число;

векторные - характеристикой числа явл набор чисел

5. выбор:

однократный - оптимальное решение находиться за одну попытку;

последовательный - есть возможность испытать.

6. последствия выбора:

выбор в условиях определенности - есть полная информация о каждой альтернативе;

вероятностный выбор-выбор в условиях риска;

выбор в условиях неопределенности - есть набор последствий, но не известно которое из них наиболее вероятно.

3. Безусловная оптимизация

Делится:

1)Одномерную- Задача поиска минимума целевой функции формулируется в виде:

x*=arg min f(x), xX, где X - множество допустимых точек, среди которых ищется точка x*, доставляющая минимум f(x) целевой функции.

Другая распространенная запись задачи минимизации

.

Когда X=R, это одномерная безусловная задача минимизации, т.е. когда целевая функция f(x) имеет только один простой аргумент и область X есть вся вещественная ось чисел.

В методах одномерной оптимизации вместо X=R рассматривается отрезок X=[a,b], содержащей искомое решение x*. Такой отрезок называется отрезком неопределенности, или отрезком локализации. Относительно целевой функции f(x) часто предполагается, что она унимодальная. Функция f(x) называется унимодальной на X=[a,b], если существует такая точка x*X, что f(x₁)>f(x₂), если x₁<x₂<x*, x₁,x₂X ; f(x₁)<f(x₂), если x*<x₁,x₂, x₁,x₂X.

2)Многомерную- Задача многомерной безусловной оптимизации формулируется в виде:

min f(x), xX, где x={x⁽¹⁾, x⁽²⁾,…, x⁽ⁿ⁾} - точка в n-мерном пространстве X=IRⁿ, то есть целевая функция f(x)=f(x⁽¹⁾,…,f(x⁽ⁿ⁾) - функция n аргументов.

Численные методы отыскания минимума, как правило, состоят в построении последовательности точек {x_k}, удовлетворяющих условию f(x₀)>f(x₁)>…>f(x_n)>…. Методы построения таких последовательностей называются методами спуска. В этих методах точки последовательности {x_k} вычисляются по формуле:х_k+1 = x_k + _kp_k, k=0,1,2,…, где p_k - направление спуска, _k - длина шага в этом направлении.

Различные методы спуска отличаются друг от друга способами выбора направления спуска p_k и длины шага _k вдоль этого направления. Алгоритмы безусловной минимизации принято делить на классы, в зависимости от максимального порядка производных минимизируемой функции, вычисление которых предполагается. Методы, использующие только значения самой целевой функции, относят к методам нулевого порядка (иногда их называют также методами прямого поиска); если, кроме того, требуется вычисление 1-х производных минимизируемой функции, то это метод первого порядка; если дополнительно используются 2-е производные, то это методы второго порядка и т. д.

4. Одномерная безусловная оптимизация

Задача поиска минимума целевой функции формулируется в виде:

x*=arg min f(x), xX,

где X - множество допустимых точек, среди которых ищется точка x*, доставляющая минимум f(x) целевой функции. Другая распространенная запись задачи минимизации .Когда X=R, это одномерная безусловная задача минимизации, т.е. когда целевая функция f(x) имеет только один простой аргумент и область X есть вся вещественная ось чисел. В методах одномерной оптимизации вместо X=R рассматривается отрезок X=[a,b], содержащей искомое решение x*. Такой отрезок называется отрезком неопределенности, или отрезком локализации. Относительно целевой функции f(x) часто предполагается, что она унимодальная. Функция f(x) называется унимодальной на X=[a,b], если существует такая точка x*X, что f(x₁)>f(x₂), если x₁<x₂<x*, x₁,x₂X, f(x₁)<f(x₂), если x*<x₁,x₂, x₁,x₂X.

Если ограничиваться рассмотрением лишь непрерывных функций f(x), то свойство унимодальности функции означает наличие у нее единственного локального минимума и этот минимум достигается в точке x=x*. В ряде методов относительно целевой функции f(x) предполагается, что она выпуклая на X. Функция f(x) называется выпуклой на x=[a,b],

если f(x₁+(1-)x₂)f(x₁)+(1-)f(x₂)

при любых x₁,x₂,X и всех , 01.

Если при любых x₁,x₂,X неравенство будет строгим, то функция f(x) называется строго выпуклой. Непрерывная строго выпуклая функция является унимодальной. Однако не всякая унимодальная функция является выпуклой или непрерывной.

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

Задача многомерной безусловной оптимизации формулируется в виде: min f(x), xX где x={x⁽¹⁾, x⁽²⁾,…, x⁽ⁿ⁾} - точка в n-мерном пространстве X=IRⁿ, то есть целевая функция f(x)=f(x⁽¹⁾,…,f(x⁽ⁿ⁾) - функция n аргументов. Рассматриваем задачу минимизации. Численные методы отыскания минимума, как правило, состоят в построении последовательности точек {x_k}, удовлетворяющих условию f(x₀)>f(x₁)>…>f(x_n)>…. Методы построения таких последовательностей называются методами спуска. В этих методах точки последовательности {x_k} вычисляются по формуле: х_k+1 = x_k + _kp_k, k=0,1,2,…, где p_k - направление спуска, _k - длина шага в этом направлении.

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

6. Методы условной оптимизации

7. Линейное программирование

8. Нелинейное программирование

Делятся на задачи линейного и нелинейного программирования.

Линейное программирование: Общая форма задачи линейного программирования.

В общем случае задача линейного программирования (ЗЛП) формулируется следующим образом: найти величины х₁,…, х_n, доставляющие минимум (максимум) линейной целевой функции

f(x) = c₁x₁ + c₂x₂ +…+ c_nx_n

и удовлетворяющие ограничениям, которые могут быть только равенствами и неравенствами вида

a_i1x₁ +…+a_inx_n b_i, i = i,k,

a_i1x₁ +…+a_inx_n b_i, i = i,k,

a_i1x₁ +…+a_inx_n b_i, i = i,k.

Cреди ограничений часто встречаются условия не отрицательности всех или части переменных

x_j 0, j=1, 2, …,S.

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

В более компактной записи общая задача линейного программирования имеет вид:

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

где a_ij, b_i, c_j - заданные постоянные величины.

2. Стандартная и каноническая формы задачи линейного программирования.

Различаются еще две основные формы задач линейного программирования в зависимости от наличия ограничений разного типа:

стандартная форма ЗЛП

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

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

каноническая форма ЗЛП

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

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

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

Нелинейное программирование:



i=1…k

i=k+1…m

j=1…S

В отличие от линейного программирования, в нелинейном есть локальный max

9. Понятие о численных методах оптимизации

1)численные методы одномерной оптимизации

По-крупному делятся на 2 группы: 1) пассивный поиск. x⁽¹⁾, x⁽²⁾… x⁽ⁿ⁾ A, набор точек, в которых необходимо произвести вычисления, задается до начала самих вычислений. f(x^||)… f(x⁽ⁿ⁾)с точностью , ||x^*-||. 2)Активный поиск. В алгоритмах активного поиска очередная точка, в которой производится эксперимент, выбирается с учетом информации, полученной в предыдущих опытах. Рассмотрение этих алгоритмов начинается с блочного поиска, которые сочетают в себе пассивные и последовательные стратегии поиска. При этом вычисления в точках объединены в блоки, в каждом из которых проводится одновременно n_i экспериментов), общее число экспериментов будет

),

т.е. блок - это совокупность из нескольких экспериментов, которые проводятся одновременно (пассивный поиск). Результаты, полученные в (i-1)-м блоке, становятся известны перед началом экспериментов в i-м блоке {x_ij (j=1,2,…,n_i}(последовательный поиск). Если размеры блоков равны единице, т.е. n_i=1, то мы имеем обычный последовательный алгоритм поиска. К методу активного поиска относятся также: алгоритм деления интервала пополам(алгоритм блочного поиска, но n-число экспериментов в блоке=3), метод дихотомии(Это алгоритм блочного поиска для ni=n=2, т.е. когда в блоке два эксперимента.), симметричные методы-метод зол сечения и чисел Фибоначчи(т.е. точки, в которых выполняются два эксперимента, на основе которых происходит уменьшение отрезка неопределённости, расположены симметрично относительно середины отрезка.)

Выбор точки x₁ в 2-х последних методах происходит на основе формул:

и

2) численные методы многомерной оптимизации

Численные методы отыскания минимума, как правило, состоят в построении последовательности точек {x_k}, удовлетворяющих условию f(x₀)>f(x₁)>…>f(x_n)>…. Методы построения таких последовательностей называются методами спуска. В этих методах точки последовательности {x_k} вычисляются по формуле:

х_k+1 = x_k + _kp_k, k=0,1,2,…,

где p_k - направление спуска, _k - длина шага в этом направлении.

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

10. Прямые методы

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

К прямым методам одномерной оптимизации относятся: 1)алгоритм пассивного поиска минимума- x⁽¹⁾, x⁽²⁾… x⁽ⁿ⁾ A, набор точек, в которых необходимо произвести вычисления, задается до начала самих вычислений. f(x^||)… f(x⁽ⁿ⁾) с точностью , ||x^*-||.

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

),

т.е. блок - это совокупность из нескольких экспериментов, которые проводятся одновременно (пассивный поиск). Результаты, полученные в (i-1)-м блоке, становятся известны перед началом экспериментов в i-м блоке {x_ij (j=1,2,…,n_i}(последовательный поиск). Если размеры блоков равны единице, т.е. n_i=1, это обычный последовательный алгоритм поиска. К методу активного поиска относятся также: алгоритм деления интервала пополам(алгоритм блочного поиска, но n-число экспериментов в блоке=3), метод дихотомии(Это алгоритм блочного поиска для ni=n=2, т.е. когда в блоке два эксперимента.), симметричные методы-метод зол сечения и чисел Фибоначчи(т.е. точки, в которых выполняются два эксперимента, на основе которых происходит уменьшение отрезка неопределённости, расположены симметрично относительно середины отрезка.)

Выбор точки x₁ в 2-х последних методах происходит на основе формул:

и

Прямые методы многомерной оптимизации:

1)метод конфигураций (метод Хука и Дживса).

Алгоритм включает в себя два основных этапа поиска. а) В начале обследуется окрестность выбранной точки (базисной точки), в результате находится приемлемое направление спуска;

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

2) Метод симплекса.

Под симплексом понимается n-мерный выпуклый многогранник n-мерного пространства, имеющий n+1 вершину. Для n=2 это треугольник, а при n=3 это тетраэдр.

Идея метода состоит в сравнении значений функции в n+1 вершинах симплекса и перемещении симплекса в направлении лучшей точки. В рассматриваемом методе симплекс перемещается с помощью операций отражения. Далее принято следующее: х₀(k), х₁(k), …, х_n(k) - вершины симплекса, где к - номер итерации.

3) Метод деформируемого симплекса (метод Нелдера - Мида).

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

11. Методы поиска нулевого, первого и второго порядков

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

Методы нулевого порядка:

Пассивный поиск. x⁽¹⁾, x⁽²⁾… x⁽ⁿ⁾ A, набор точек, в которых необходимо произвести вычисления, задается до начала самих вычислений. f(x^||)… f(x⁽ⁿ⁾) с точностью , ||x^*-||. 2)Активный поиск. В алгоритмах активного поиска очередная точка, в которой производится эксперимент, выбирается с учетом информации, полученной в предыдущих опытах. Рассмотрение этих алгоритмов начинается с блочного поиска, которые сочетают в себе пассивные и последовательные стратегии поиска. При этом вычисления в точках объединены в блоки, в каждом из которых проводится одновременно n_i экспериментов), общее число экспериментов будет ), т.е. блок - это совокупность из нескольких экспериментов, которые проводятся одновременно (пассивный поиск). Результаты, полученные в (i-1)-м блоке, становятся известны перед началом экспериментов в i-м блоке {x_ij (j=1,2,…,n_i}(последовательный поиск). Если размеры блоков равны единице, т.е. n_i=1, то мы имеем обычный последовательный алгоритм поиска. К методу активного поиска относятся также: алгоритм деления интервала пополам(алгоритм блочного поиска, но n-число экспериментов в блоке=3), метод дихотомии(Это алгоритм блочного поиска для ni=n=2, т.е. когда в блоке два эксперимента.), симметричные методы-метод зол сечения и чисел Фибоначчи(т.е. точки, в которых выполняются два эксперимента, на основе которых происходит уменьшение отрезка неопределённости, расположены симметрично относительно середины отрезка.)

Выбор точки x₁ в 2-х последних методах происходит на основе формул: и ; метод, основанный на аппроксимации целевой функции(по полученной в ходе вычислений информации строится аппроксимирующая функция и её минимум принимается за точку очередного вычисления.): метод парабол, т.е. в качестве аппроксимирующей функции используется парабола.

Методы первого порядка: из одномерной оптимизации- метод касательных.

Многомерная: 1) Градиентные методы: градиент функции в некоторой точке x_k направлен в сторону наискорейшего локального возрастания функции и перпендикулярен линии уровня (поверхность постоянного значения функции f(x), проходящей через точку x_k). Вектор, противоположный градиенту , называется антиградиентом, который направлен в сторону наискорейшего убывания функции f(x). Выбирая в качестве направления спуска p_k антиградиент - в точке x_k, мы приходим к итерационному процессу вида:

x_k+1 = x_k - _k f'(x_k), _k>0, k=0,1,2,….

В координатной форме этот процесс записывается следующим образом:

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

2) Метод покоординатного спуска. Желание уменьшить объем вычислительной работы, требуемой для осуществления одной итерации метода наискорейшего спуска, привело к созданию методов покоординатного спуска.

3)методы оврагов: эвристические алгоритмы, овражные методы I, II. Градиентные методы медленно сходятся в тех случаях, когда поверхности уровня целевой функции f(x) сильно вытянуты. Это «эффект оврагов». Суть эффекта в том, что небольшие изменения одних переменных приводят к резкому изменению значений функции - эта группа переменных характеризует «склон оврага», а по остальным переменным, задающим направление «дно оврага», функция меняется незначительно. Существуют различные подходы для определения точки минимума функции f(x) в овражной ситуации. Большинство из них основаны на эвристических (то есть интуитивных, не обоснованных строго) соображениях. Их можно применять в ситуациях, когда применение более совершенных методов невозможно или нецелесообразно, например, значение целевой функции вычисляется со значительными погрешностями, информация о ее свойствах недостаточна, и т. д. Эти методы просты в реализации и довольно часто применяются на практике, позволяя в ряде случаев получить удовлетворительное решение задачи.

4) Метод сопряженных градиентов: алгоритм для неквадратичных целевых функций, метод Флетчера - Ривса. Метод сопряженных градиентов отличается от градиентных методов более высокой скоростью сходимости, которая при определенных предположениях относительно целевой функции, приближается к скорости сходимости метода Ньютона.

Методы второго порядка:

Методы Ньютона. Все они являются прямым обобщением известного метода Ньютона отыскания корня уравнения: ц(x) = 0, (1), где ц(x) - скалярная функция скалярного аргумента x.

Метод Ньютона отыскания корня уравнения описывается следующей рекуррентной формулой: x_k+1 = x_k - ц(x_k) / ц'(x_k). (2) Этот метод ещё называют методом касательных для решения уравнения (1). Сюда относятся: метод Ньютона, его модификация I и II, Методы с регулировкой шага (методы Ньютона - Рафсона): Ньютона - Рафсона с дроблением шага, метода Ньютона - Рафсона с выбором оптимального шага.

12. Пассивные и активные (последовательные) методы поиска

1)Пассивные методы: алгоритм пассивного поиска минимума- x⁽¹⁾, x⁽²⁾… x⁽ⁿ⁾ A, набор точек, в которых необходимо произвести вычисления, задается до начала самих вычислений. f(x^||)… f(x⁽ⁿ⁾) с точностью , ||x^*-||.

2)Активный поиск. В алгоритмах активного поиска очередная точка, в которой производится эксперимент, выбирается с учетом информации, полученной в предыдущих опытах. Рассмотрение этих алгоритмов начинается с блочного поиска, которые сочетают в себе пассивные и последовательные стратегии поиска. При этом вычисления в точках объединены в блоки, в каждом из которых проводится одновременно n_i экспериментов), общее число экспериментов будет ), т.е. блок - это совокупность из нескольких экспериментов, которые проводятся одновременно (пассивный поиск). Результаты, полученные в (i-1)-м блоке, становятся известны перед началом экспериментов в i-м блоке {x_ij (j=1,2,…,n_i}(последовательный поиск). Если размеры блоков равны единице, т.е. n_i=1, то мы имеем обычный последовательный алгоритм поиска. К методу активного поиска относятся также: алгоритм деления интервала пополам(алгоритм блочного поиска, но n-число экспериментов в блоке=3), метод дихотомии (Это алгоритм блочного поиска для ni=n=2, т.е. когда в блоке два эксперимента.), симметричные методы-метод зол сечения и чисел Фибоначчи(т.е. точки, в которых выполняются два эксперимента, на основе которых происходит уменьшение отрезка неопределённости, расположены симметрично относительно середины отрезка.)

Выбор точки x1 в 2-х последних методах происходит на основе формул: и ;

16. Критерии останова методов поиска

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

Пр: в градиентном методе с постоянным шагом: L=

где L-производная в точке x_(k+1).

14. Сходимость методов

Особенностью метода Ньютона является то, что для квадратичной целевой функции он находит минимум за один шаг, независимо от начального приближения x₀ и степени овражности. В общем случае, когда минимизируемая функция не квадратична, вектор p_k = - (f ''(x_k)) ^-1·f '(x_k) не указывает в точку её минимума, однако имеет большую составляющую вдоль оси оврага и значительно ближе к направлению на минимум, чем антиградиент. Этим и объясняется более высокая сходимость метода Ньютона по сравнению с градиентными методами при минимизации овражных целевых функций. Недостатками метода Ньютона является то, что он, во-первых, предполагает вычисление вторых производных и, во-вторых, может расходиться, если начальное приближение находится слишком далеко от минимума. Удачный выбор начального приближения x₀ гарантирует сходимость метода Ньютона. Однако отыскание подходящего начального приближения - далеко не простая задача. Поэтому необходимо как-то изменить формулу x_k+1 = x_k - (f ''(x)) ^-1·f '(x), чтобы добиться сходимости независимо от начального приближения. Доказано, что в некоторых предположениях для этого достаточно в методе Ньютона кроме направления движения (f ''(x)) ^-1·f '(x) выбирать и длину шага вдоль него. Такие алгоритмы называются методами Ньютона с регулировкой шага (методами Ньютона - Рафсона) и выглядят так: x_k+1 = x_k - _k(f ''(x_k)) ^-1·f '(x_k).Величина _k выбирается так, чтобы обеспечить убывание целевой функции на каждой итерации.

Мы рассмотрим два способа выбора шага _k. Первый из них связан с проверкой неравенства f(x_k + _kp_k ) - f(x_k) ·_k(f '(x_k), p_k), где p_k = - (f ''(x_k)) ^-1·f '(x_k) - направление спуска, а 0 < < Ѕ - некоторое заданное число, общее для всех итераций. Если это неравенство выполнено при _k = 1, то шаг принимается равным единице и осуществляется следующая итерация. Если нет - дробится до тех пор, пока оно не выполнится. Второй метод определения шага _k, как и в методе наискорейшего спуска состоит в минимизации функции f(x_k + _kp_k ) = min f(x_k + _kp_k ). 0

Т-ма. О сходимости градиентных методов.

Если f(x) удовлетворяет условию Лифшица (||f `(x<sub>1</sub>)-f `(x₂)||?R||x₁-x₂||), тогда какая бы ни была Х₀

17. Теорема существования решения оптимизационной задачи (формулировка Т. Вейерштрасса)

Если А - ограничена и замкнута, а f(x) - непрерывная функция на А, тогда у этой функции существует глобальный min (max). (где А-множество альтернатив)

18. Необходимые условия экстремумов первого и второго порядков

Это условия, которым должна удовл-ть функция: f(x), f ^| (x), f^||(x)-полностью дифференцируемы(т.е у функции есть производные первого и второго порядка и все эти функции непрерывны)

Т. Необходимое условие 1 порядка:

Х₀ - локальный минимум f `(x)=0

Лекц: для того, чтобы f(x) достигала внутр точки, x^*-экстремума, необходимо чтобы f `(x)=0

Т. вар 3 Необх-ое условие min 1-го порядка

Стационарная X*

Т. Необходимое условие 2 порядка:

f(x) - имеет непрерывные производные 1 и 2 порядка, Х₀ - стационарная точка, f ``(x)?0.

Др.форм-ка(лекц): для того, чтобы стац. внутр. точка была точкой min, необх, чтобы 2-я произв была в этой точке. f ``(x<sup>*</sup>)?0- min; f ``(x^*)?0 -max. Где x^*-внутр точка(или экстремум?). Стац. точки-все точки, производные кот. равны 0.

Т.вар 3 Необходимое условие 2 го порядка X₀ -стационарная точка

Квадратичная форма записи

19. Достаточные условия экстремума (гладкие функции одной переменной и многих переменных)

Т. Достаточное условие 2 порядка:

f(x) - имеет непрерывные производные 1 и 2 порядка, Х₀ - стационарная точка, f ``(x)>0.

(лекц) x^*-стац точка(все точки, производные кот. равны 0). Если f ``(x^*)>0 то x^*-локальный min

Т. вар 3 Достаточное условие 2-го порядка

Х^* - стационарная точка

20. Унимодальная функция

f(x)-унимодальная функция, т.е. на отрезке [a, b] есть единственный min.

Функция f(x) называется унимодальной на X=[a,b], если существует такая точка x*X, что f(x₁)>f(x₂), если x₁<x₂<x*, x₁,x₂X, f(x₁)<f(x₂), если x*<x₁,x₂, x₁,x₂X.

Непрерывная строго выпуклая функция является унимодальной. Однако не всякая унимодальная функция является выпуклой или непрерывной.

21. Лемма о свойствах унимодальной функции

Пусть f(x) -унимодальна на отрезке [a, b], x⁽¹⁾<x⁽²⁾, x⁽¹⁾, x⁽²⁾[a, b]. Тогда:

1) f(x⁽¹⁾)<f(x⁽²⁾), x*[a, x⁽²⁾].

2) f(x⁽¹⁾) >f(x⁽²⁾), x*[ x⁽¹⁾, b ].

3) f(x⁽¹⁾) =f(x⁽²⁾), x*[ x⁽¹⁾, x⁽²⁾].

22. Понятие об эффективности поиска

Л. Любые два эксперимента позволяют уменьшить отрезок неопределенности

f(x^(k)) =min f(x⁽ⁱ⁾), 1?i?n, [ x^(k-1), x^(k+1)], ln(x⁽¹⁾,…x⁽ⁿ⁾, k)= x^(k+1)- x^(k-1)

L_n=( x⁽¹⁾,…x⁽ⁿ⁾)=max ln(x⁽¹⁾, x⁽²⁾…x⁽ⁿ⁾, k)=/* (ф-ла эффект-ти стратегии)*/=max(x^(k+1)- x^(k-1)) 1?k?n

(⁽¹⁾… ⁽ⁿ⁾)

L(⁽¹⁾… ⁽ⁿ⁾)=min ln( x⁽¹⁾,…x⁽ⁿ⁾)=, (a? x⁽¹⁾< x⁽²⁾…. <x⁽ⁿ⁾ ?b), = min(max ln( x⁽¹⁾,…x⁽ⁿ⁾, k)), 1?k?n, (a? x⁽¹⁾< x⁽²⁾…. <x⁽ⁿ⁾ ?b) Наилучшая стратегия по min и max критерию.

Замечания:

1) реш-я x* нах-ся на отрезке x*[^(k-1)… ^(k+1)] =

2) не всегда наилучшая стратегия существует

Надо расположить наилучшим образом 2 точки на отрезке, чтобы был отрезок неопределенности

1) Ѕ+

2) Ѕ+

0<=max, L₂(x_1,x₂)=1/2+

Наил стратегии не сущ, т.к уменьшая , можно сделать стратегию еще лучше. Надо взять стратегию чуть больще Ѕ. Ѕ=L^*(значение, меньше кот быть не может). L₂<L^*+ (- оптимальная стратегия)

24. Оптимальные и дельта- оптимальные методы поиска

Оптимальный алгоритм пассивного поиска.

Т. Если N=2k-1, то предлагаемый алгоритм является оптимальным. Если N=2k то оптимального алгоритма не существует. Предлагаемый алгоритм является оптимальным.

Если располагать нечетное число точек, то нужно делать это след обр: x_i=a+i

если N=2k: Ф-ла для выч четных точек: x_2j-a+j, j=1, 2..k(где k=1/2n). Для выч-я нечетных точек сдвигаем на : x_2j= x_2j-.

Метод Фибоначчи.

Т. Метод Фибоначчи является оптимальным. Для заданного числа вычислений нет метода оптимальнее и лучше.

25. Пассивный метод поиска зкстремума

П ассивный поиск. x⁽¹⁾, x⁽²⁾… x⁽ⁿ⁾ A, набор точек, в которых необходимо произвести вычисления, задается до начала самих вычислений. f(x^||)… f(x⁽ⁿ⁾) с точностью , ||x^*-||.

26. Алгоритм пассивного поиска минимума

Отрезок [a,b] исходный отрезок неопределенности. Пусть N - число точек, в которых необходимо провести вычисления целевой функции f(x), т.е. N экспериментов. Точки, в которых необходимо провести эксперименты, определяются следующим образом:

Среди вычисленных значений {f(x_i)} (i=1,N), ищется точка x_j, в которой достигается минимум:

f(x_j)= min f(x_i) 1iN

Найденная точка принимается за приближенное решение задачи . Исходный отрезок неопределенности [a,b] после экспериментов в N точках сужается до [x_j-1,x_j+1], длина которого равна: L_N.

Точность найденного решения равна половине отрезка неопределенности, т.е. , где и x^* - точное решение.

30. Об эффективности блочных методов

Чем меньше размер блока, тем точнее и эффективнее поиск

27. Теорема об оптимальности пассивного поиска

Т. 1)Если N=2k-1, то предлагаемый алгоритм является оптимальным. 2)Если N=2k то оптимального алгоритма не существует. Предлагаемый алгоритм является оптимальным.

1) x_i=a+i; L_N(x₁…x_n)=2()=

Т: L_N(x₁…x_n) <

x₂-a<

Предположим, что min будет в промежутке x_2-x₄

b-x_n-1<. Таких неравенств k;

Просуммируем левые и правые части: b-a<k =b-a; противоречие: b-a< b-a. L_N(x₁…x_n) <;не выполняется L_N(x₁…x_n)=2()=стратегия явл. наил.

2)

все четные точки раскидываются оптимально

Ф-ла для выч четных точек: x_2j-a+j, j=1, 2..k(где k=1/2n).

Для выч-я нечетных точек сдвигаем на : x_2j= x_2j-.

Т-ма: L_N(x₁…x_n) <+;

L_N(x₁…x_n) x₂-a<

x_1-x₂

x_n-x_n-2

сложим обе части: x_n -a k ()

1) x_n= x_2k a+()(b-a) 2) b- x_k+1 ;

Рассм-м отрезок: b- x_n< b- x_n-1 ; b- x_nb-(a+()(b-a))= (b-a)- (b-a)=

28. Последовательные(активные) методы поиска экстремума

В алгоритмах активного поиска очередная точка, в которой производится эксперимент, выбирается с учетом информации, полученной в предыдущих опытах. Рассмотрение этих алгоритмов начинается с блочного поиска, которые сочетают в себе пассивные и последовательные стратегии поиска. При этом вычисления в точках объединены в блоки, в каждом из которых проводится одновременно n_i экспериментов), общее число экспериментов будет ), т.е. блок - это совокупность из нескольких экспериментов, которые проводятся одновременно (пассивный поиск). Результаты, полученные в (i-1)-м блоке, становятся известны перед началом экспериментов в i-м блоке {x_ij (j=1,2,…,n_i}(последовательный поиск). Если размеры блоков равны единице, т.е. n_i=1, то мы имеем обычный последовательный алгоритм поиска. К методу активного поиска относятся также: алгоритм деления интервала пополам(алгоритм блочного поиска, но n-число экспериментов в блоке=3), метод дихотомии(Это алгоритм блочного поиска для ni=n=2, т.е. когда в блоке два эксперимента.), симметричные методы-метод зол сечения и чисел Фибоначчи(т.е. точки, в которых выполняются два эксперимента, на основе которых происходит уменьшение отрезка неопределённости, расположены симметрично относительно середины отрезка.)

Выбор точки x₁ в 2-х последних методах происходит на основе формул:

и ;

29. Блочные методы поиска экстремума(четные и нечетные размеры блока)

Вычисления в точках объединены в блоки, в каждом из которых проводится одновременно n_i экспериментов), общее число экспериментов будет ), т.е. блок - это совокупность из нескольких экспериментов, которые проводятся одновременно. Результаты, полученные в (i-1)-м блоке, становятся известны перед началом экспериментов в i-м блоке {x_ij (j=1,2,…,n_i}(

Схема алгоритма(нечетное, n=2k-1)

Шаг 1. Задаются исходный отрезок неопределенности [a,b], - точность приближенного решения , число экспериментов в блоке - n (нечетное, n=2k-1). Проводим эксперимент в середине отрезка [a,b], т.е. вычисляем y_k=f(x_k), где xk=(a+b)/2.

Шаг 2. Проводим эксперименты в остальных точках блока: y_i=f(x_i), где x_i=a+i*(b-a)/(n+1), i=1,2,..,n, ik. Находим точку x_j, в которой достигается минимум среди вычисленных значений: f(x_j)=min f(x_i), следовательно, точное значение минимума x^* содержится на отрезке [x_j-1,x_j+1].

Шаг 3. Полагаем a=x_j-1, b=x_j+1, x_k=x_j, y_k=y_j. Если b-a2, то , и поиск заканчивается. Иначе перейти к шагу 2.

Если заданная точность достигнута после т итераций,т.е. после экспериментов в m блоках, то длина отрезка неопределенности после всех N вычислений (N=n+(m-1)(n-1)=(n-1)m+1) будет:

и

Схема алгоритма(четное, n=2k)

Шаг 1. [a,b], ,

Шаг 2. определяем точки, в кот нужно производить вычисления:

x_2j=a+(b-a)/(k+1), j=1, 2..k;

x_2j-1= x_2j-; y_i=f(x_i)² i=1,2..n; x₀=0, x_n+1=b

Шаг 3 найти n, в которой зн-е функции будет min: f(x_L)=minf(x_i), 1in

Шаг 4 вновь получившийся отрезок локализации наз-м ab: a=x_L-1, b=x_L+1

Шаг 5 Если b-a>2, то идти ко 2 шагу, иначе (a+b)/2, длина отрезка неопределенности после всех N вычислений: L=(b-a)/(+1)^N/n

31. Метод дихотомии

Это алгоритм блочного поиска для ni=n=2, т.е. когда в блоке два эксперимента. Так как пассивная составляющая алгоритма, т.е. блок, содержит четное число экспериментов, то оптимальный выбор точек x_ij, в которых необходимо провести эксперименты, будет неравномерным, в отличие от предыдущих алгоритмов, где число экспериментов в блоке было нечетным и, соответственно, расположение точек равномерным. Если блок содержит два эксперимента, то оптимальное (дельта оптимальное) расположение точек, в которых будут проводится эксперименты, это как можно ближе к середине отрезка. Такое расположение точек позволяет получить наименьший отрезок неопределенностей после экспериментов в блоке.

Схема алгоритма.

Шаг 1. Задаются a,b, и - малое положительное число, значительно меньшее чем .

Шаг 2. Определяется середина отрезка x=(a+b)/2. Производятся эксперименты в двух точках близких середине: y1=f(x-), y2=f(x+).

Шаг 3. Определяется следующий отрезок локализации, т.е. определяется какой из отрезков [a,x+] или [x-,b] содержит точное решение x*. Если y₁y₂, то это отрезок [a,x+] и b=x+, иначе это отрезок [x-,b] и a=x-, т.е. выбранный отрезок локализации мы снова обозначили как [a,b].

Шаг 4. Если b-a2, то x=(a+b)/2, и поиск заканчивается. Иначе перейти к шагу 2.

После к итераций общее число экспериментов будет N=2к, а длина получившегося отрезка неопределенности .

Следовательно, .

32. Алгоритм деления интервала пополам

Это вариант блочного метода при n=3.

Схема алгоритма.

Шаг 1. Задаются a,b,. Производим эксперимент в точке x₂=(a+b)/2, т.е. вычисляем y₂=f(x₂).

Шаг 2. Проводим эксперименты в остальных точках блока: x₁=(a+x₂)/2, y₁=f(x₁), x₃=(x₂+b)/2, y₃=f(x₃).

Находим x_j такую, что f(x_j)=min {f(x_i)}.