Поможем в ✍️ написании учебной работы

Имя

Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой

Выберите тип работыЧасть дипломаДипломная работаКурсовая работаКонтрольная работаРешение задачРефератНаучно - исследовательская работаОтчет по практикеОтветы на билетыТест/экзамен onlineМонографияЭссеДокладКомпьютерный набор текстаКомпьютерный чертежРецензияПереводРепетиторБизнес-планКонспектыПроверка качестваЭкзамен на сайтеАспирантский рефератМагистерская работаНаучная статьяНаучный трудТехническая редакция текстаЧертеж от рукиДиаграммы, таблицыПрезентация к защитеТезисный планРечь к дипломуДоработка заказа клиентаОтзыв на дипломПубликация статьи в ВАКПубликация статьи в ScopusДипломная работа MBAПовышение оригинальностиКопирайтингДругое

Нажимая кнопку "Продолжить", я принимаю политику конфиденциальности

Тема 1. Введение

Классификация методов оптимизации

Задачи оптимизации

1. Нахождение экстремумов функций

Нахождение локального экстремума

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

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

· Без использования производных

· С использованием производных

2. Методы многомерного поиска

· Без использования производных

· С использованием производных

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

3. Методы случайного поиска

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

1. Методы математического программирования

· Методы линейного программирования

· Методы нелинейного программирования

· Методы дробно-линейного программирования

· Методы сепарабельного программирования

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

· Методы возможных направлений и градиентные методы

· Методы целочисленного программирования

· Методы стохастического программирования

2. Вариационное исчисление и принцип максимума

3. Динамическое программирование

4. Методы случайного поиска

1.1.3. Поиск экстемумов функций, вычисляемых со случайной ошибкой

1. Метод стохастической аппроксимации

2. Метод планирования экспериментов

Нахождение глобального экстремума

· Вариационное исчисление

· Принцип максимума

· Динамическое программирование

· Человеко-машинные методы

2. Нахождение экстремумов функционалов

· Вариационное исчисление

· Принцип максимума

· Динамическое программирование

· Человеко-машинные методы

 

(--3--)

Выпуклые множества

Рассмотрим набор из произвольных векторов из Еⁿ:  и составим линейную комбинацию векторов с весами m_i, i=1,2,…,r:

      (1)

При этом, если  и , i=1,2,…,r, то выражение (1) называется выпуклой линейной комбинацией.

В свою очередь, множество  (содержащееся) называется выпуклым, если вместе с любыми своими двум точками  оно содержит и любую выпуклую линейную комбинацию вида:

  (2)

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

Примеры выпуклых множеств:

Множества, для которых условие (2) не выполняется, являются невыпуклыми:

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

Важное свойство выпуклого множества:

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

Докажем это:

Пусть  - векторы выпуклого множества G.

Образуем из них выпуклую линейную комбинацию:

, при  и

Преобразуем это выражение:

(--4--)

Но выражение в скобках есть не что иное, как выпуклая линейная комбинация двух векторов, принадлежащих ( ) G, и, следовательно, также принадлежит G. Обозначив его через , получим , то есть число векторов в этой линейной комбинации сократилось на единицу. Объединив вектор  с вектором , сокращаем число учитываемых в дальнейшем векторов ещё на единицу. Продолжая таким образом, придём к выражению:

, но поскольку  является линейной комбинацией векторов  и , принадлежащих множеству G, то и сам вектор  принадлежит этому множеству G, то есть , ч.т.д.

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

Для доказательства целесообразно рассмотреть чертёж множества G, являющегося пересечением двух выпуклых множеств G₁ и G₂.

Точки А и В принадлежат одновременно обоим выпуклым множествам G₁ и G₂, значит и весь отрезок АВ принадлежит G₁ и G₂ одновременно, следовательно, и их общей части также принадлежит.

Следовательно, доказано, что множество G – выпукло.

Множество точек , удовлетворяющих неравенству , называется ε‑окрестностью точки .

Если же множество G содержит не только данную (какую-либо) точку, но и её ε‑окрестность, то такую точку называют внутренней точкой множества G.

Если точка  принадлежит G и в её ε‑окрестности есть точки, принадлежащие G и не принадлежащие ему, то такая точка называется граничной.

 

(--5--)

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

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

Множество G называется ограниченным, если для всех его точек  найдётся такое число С, не зависящее от , что  (длина, норма, метрика)

Для евклидова пространства размерности n справедлива теорема Больцано‑Вейрштрасса:

Из любой ограниченной бесконечной последовательности точек Eⁿ может быть выделена сходящаяся последовательность.

 

(--6--)

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

Примеры выпуклых множеств с конечным и бесконечным числом крайних точек:

A, B, C, D, E являются крайними, М не является крайней.

 

 

Бесконечное множество крайних точек

 

 

На прямой и плоскости не существует крайних точек.

Теорема о крайней точке

Всякое замкнутое выпуклое ограниченное множество G содержит хотя бы одну крайнюю точку.

 

(--7--)

Множество точек , удовлетворяющих линейному уравнению вида

, называется гиперплоскостью..(  - скалярное произведение)

По обе стороны от гиперплоскости лежат два множества, называемые полупространствами:

 и

Гиперплоскость строго разделяет два множества G₁ и G₂, если имеют место строгие неравенства:

 для

 для

Если подобные строгие неравенства не соблюдаются, то множества G₁ и G₂ считаются просто (нестрого) разделимыми.

 

Теорема о разделяющей гиперплоскости (фундаментальная теорема)

Пусть G₁ и G₂ – произвольные выпуклые замкнутые множества без общих точек, из которых хотя бы одно ограничено. Тогда существует гиперплоскость, строго разделяющая множества G₁ и G₂.

Теорема не верна, если хоть одно из предположений относительно G₁ и G₂ не соблюдается:

	G1		G1
	G1 - невыпуклое	G1 – (1) незамкнутое (2) нет строгого разделения	G1 и G2 неограниченны (в бесконечности получится нестрогое разделение)

(--8--)

Гиперплоскость  называется опорной к множеству G в точке , если:

1. , то есть гиперплоскость содержит точку ,

2.  или  при , то есть множество G лежит в одном из полупространств, порождаемых гиперплоскостью.

Например, если  - граничная точка выпуклого замкнутого множества G, то существует опорная гиперплоскость к этому множеству в точке .

Выпуклой оболочкой множества  называется множество [G], состоящее из точек вида (то есть выпуклая линейная комбинация конечного числа точек множества G , которое может быть и невыпуклым), где , , i=1,2,…,N, .

 

Выпуклая оболочка является наименьшим из выпуклых множеств, включающих в себя множество G; например:

 

 

Укажем некоторые свойства выпуклых оболочек:

1. Выпуклая оболочка произвольного множества есть выпуклое множество.

2. В выпуклую оболочку множества G входит само множество G.

3. Выпуклая оболочка [G] выпуклого множества G совпадает с множеством G, то есть [G]=G.

Если G – выпуклое замкнутое ограниченное множество, а G¹ – множество его крайних точек, то G является выпуклой оболочкой множества G¹.

 

(--9--)

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

Функция , заданная на выпуклом множестве  называется выпуклой, если для любых двух точек  и любого  справедливо неравенство

(1)

(в правой части линейная функция, интерполирующая реальную функцию)

Если при тех де условиях удовлетворяется неравенство:

(2)

(в  именно больший индекс)

то такая функция называется вогнутой.

Если неравенства превращаются в строгие равенства, то говорят, что функция строго выпукла (строго вогнута).

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

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

Рассмотрим некоторые важные свойства выпуклых функций.

Теорема 1.

Линейная форма  является выпуклой (и вогнутой одновременно) на всём Eⁿ.

Доказательство

Для любых двух точек  выполняется равенство , , что и указывает, согласно (1) и (2), на принадлежность  классу выпуклых (вогнутых) функций, но не классу строго выпуклых (вогнутых) функций.

 (--10--)

 

Теорема 2

Если функции , j=1,2,…,m являются выпуклыми на некотором выпуклом множестве , то функция  также является выпуклой.

Доказательство:

для любых двух точек и любого  выполняется:

(Неравенство справедливо, т.к. выполняется для любой выпуклой функции)

ч.т.д.

То есть, сумма выпуклых функций есть выпуклая функция.

Теорема 3

Если  выпуклая дифференцируемая функция, то справедливо неравенство:

, где  - вектор-градиент функции  в точке .

A=

Для справки:

Если f(x) – действительная функция, имеющая в интервале  n-ую производную f⁽ⁿ⁾(x), тогда , где .

Доказательство

Из формулы (1) следует, что при всех  

Если разложить числитель этой дроби по формуле Тейлора без учёта остаточных членов выше первого порядка малости, получим:

, где , и переходя к пределу при , окончательно получим:

, где  - любая внутренняя точка из множества Х, и

ч.т.д.

(--11--)

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

Теорема 4

Если  - выпуклые функции и  - множество точек, удовлетворяющих условиям

, , i=1,2,…,m       (*)

тогда  - выпуклое множество.

Доказательство:

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

Очевидно, что . Осталось показать, что , а это видно из выпуклости .

Действительно:

.

Из условий (*) следует, что при  справедливы условия

,

Следовательно:

, то есть , то есть  и  - выпуклое множество.

ч.т.д.

(--12--)

Теорема 5

Если  - выпуклая функция, заданная на замкнутом выпуклом множестве , тогда любой относительный (локальный, местный) минимум  на Х является абсолютным (глобальным) минимумом  на Х.

 

Доказательство ведём методом от противного.

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

Из условия выпуклости функции следует, что для любого  выполняется неравенство:

.

Если учесть, что , то можно записать:

Рассмотрим любую ε‑окрестность точки  с . Если взять λ такое, что , то точка  лежит в ε‑окрестности точки  и . Но это невозможно, так как  достигает в точке  относительного минимума. Таким, образом, любой относительный минимум является одновременно глобальным минимумом для функции .

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

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

заданы множество Х и функция , определённая на Х. Требуется найти точки минимума или максимума функции  на Х. Будем записывать задачу на минимум в виде:

, .

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

Х называется допустимым множеством (или решением, планом).

Любой  называется допустимой точкой задачи.

Считается, что , то есть задача является конечномерной.

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

Точка  называется точкой локального минимума функции  на множестве Х (или локальным решением задачи), если существует число ε>0 такое, что

 при всех ,

где  - шар радиуса ε>0 с центром в .

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

Итак, понятно, что ,

                             ,

то есть точка  реализует величину .

Множество всех точек глобального минимума  на X обозначается через

то есть .

Аналогично для задачи максимизации записываем , .

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

 

(--14--)

Для задач оптимизации вопрос о существовании решения решает теорема Вейерштрасса (из математического анализа):

Пусть Х – замкнутое ограниченное множество в Еⁿ.  - непрерывная функция на Х. Тогда точка глобального минимума функции  на Х существует.

Выделим наиболее важные для теории и приложений объекты оптимизации: реальные, модельные и математические.

1) реальные:

Объект оптимизации представляет собой реальный объект, на котором решается задача оптимизации. Необходимо, однако, чтобы характеристики объекта изменялись значительно медленнее, чем происходит процесс оптимизации, иначе это будет экстремальное регулирование. Например: отладка технического процесса, отработка конструкции.

2) модельные:

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

3) математические

математические объекты, для которых критериальная функция и множество Х заданы математическими выражениями.

Весь процесс оптимального проектирования проходит все три стадии: в), б), а).

В нашем курсе мы подробно остановимся на стадии в).

Сначала выделим наиболее важные классы оптимизационных задач.

 

(--15--)

Задача условной оптимизации

, , ,

то есть Х – собственное подмножество пространства Eⁿ.

Тема 1. Введение

Классификация методов оптимизации

Задачи оптимизации

1. Нахождение экстремумов функций