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

Автор работы: Пользователь скрыл имя, 10 Ноября 2011 в 03:45, реферат

Описание работы

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

Содержание работы

Введение
1. Формулировка математической задачи оптимизации.
2. Численные методы решения задач одномерной оптимизации.
Метод перебора, метод деления пополам.
3. Методы безусловной минимизации функций многих переменных.
3.1. Многомерный поиск без использования производных
Метод циклического покоординатного спуска, метод Хука и Дживса.
3.2. Многомерный поиск, использующий производные
Метод наискорейшего спуска
3.3. Методы, использующие сопряженные направления
Метод Дэвидона-Флетчера-Пауэлла
Заключение
Литература

Файлы: 1 файл

реферат.docx

— 71.46 Кб (Скачать файл)
 

     СОДЕРЖАНИЕ

     Введение

     1. Формулировка математической задачи  оптимизации.

     2. Численные методы решения задач  одномерной оптимизации.

     Метод перебора, метод деления пополам.

     3. Методы безусловной минимизации  функций многих переменных.

     3.1. Многомерный поиск без использования  производных

     Метод циклического покоординатного спуска, метод Хука и Дживса.

     3.2. Многомерный поиск, использующий  производные

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

     3.3. Методы, использующие сопряженные  направления

     Метод Дэвидона-Флетчера-Пауэлла

     Заключение

     Литература 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

     ВВЕДЕНИЕ

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

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

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

     Однако  возьмем другой пример. Допусти, организуется работа городского транспорта. В нашем  распоряжении имеется какое-то количество транспортных средств. Необходимо принять  ряд решений, например: какое количество и каких транспортных средств  направить по тому или другому  маршруту? Как изменять частоту следования машин в зависимости от времени  суток? Где разместить остановки? И  так далее.

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

     Конечно, и во втором примере при выборе решения можно действовать интуитивно, опираясь на опыт и здравый смысл. Но решения окажутся гораздо более  разумными, если они будут подкреплены  количественными, математическими  расчетами. Эти предварительные  расчеты помогут избежать длительного  и дорогостоящего поиска правильного  решения "на ощупь".

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

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

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

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

      
      
 
 
 
 
 
 
 
 
 
 
 
 
 

1.ФОРМУЛИРОВКА  МАТЕМАТИЧЕСКОЙ ЗАДАЧИ                   ОПТИМИЗАЦИИ.

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

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

     Под минимизацией (максимизацией) функции n переменных f(x)=f(x1,... ,xn) на заданном множестве U n-мерного векторного пространства En понимается определение хотя бы одной из точек минимума (максимума) этой функции на множестве U, а также, если это необходимо, и минимального (максимального) на U значения f(x).

     При записи математических задач оптимизации  в общем виде обычно используется следующая символика:

     f(x) -> min (max),x принадлежит U, где f(x) - целевая функция, а U - допустимое множество, заданное ограничениями на управляемые переменные. 

     2.ЧИСЛЕННЫЕ МЕТОДЫ  РЕШЕНИЯ ЗАДАЧ ОДНОМЕРНОЙ ОПТИМИЗАЦИИ

     Задачи  одномерной минимизации представляют собой простейшую математическую модель оптимизации, в которой целевая  функция зависит от одной переменной, а допустимым множеством является отрезок  вещественной оси:  f(x) -> min , x принадлежит [a, b].

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

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

     Для решения задачи минимизации функции  f(x) на отрезке [a, b] на практике, как правило, применяют приближенные методы. Они позволяют найти решения этой задачи с необходимой точностью в результате определения конечного числа значений функции f(x) и ее производных в некоторых точках отрезка [a, b]. Методы, использующие только значения функции и не требующие вычисления ее производных, называются прямыми методами минимизации.

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

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

     Некоторые из них: метод перебора, метод поразрядного поиска, метод деления попалам, метод золотого сечения.

          Метод перебора

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

     Разобьем  отрезок [a,b] на n равных частей точками  деления:

     xi=a+i(b-a)/n, i=0,...n

     Вычислив  значения F(x) в точках xi, путем сравнения  найдем точку xm, где m - это число от 0 до n, такую, что

     F(xm) = min F(xi) для всех i от 0 до n.

     Погрешность определения точки минимума xm функции F(x) методом перебора не превосходит  величены Eps=(b-a)/n.

     Метод деления пополам

     Рассмотрим  функцию F, которую требуется минимизировать на интервале [a1, b1]. Предположим, что F строго квазивыпукла. Очевидно, что наименьшее число вычислений значений функции , которые необходимы для сокращения интервала неопределенности, равно  двум. Одной из стратегий является выбор этих двух точек симметрично  на расстоянии eps>0 от середины интервала. Здесь число eps настолько мало, чтобы  длина нового интервала неопределенности eps+(b1-a1)/2 являлась достаточно близкой  к теоретическому значению (b1-a1)/2, и  в то же время такое, чтобы значение функции в этих двух точках были различимы.

          Алгоритм дихотомического поиска. 
Алгоритм дихотомического метода для минимизации строго квазивыпуклой фунции на интервале [a1,b1].

     Начальный этап. Выбрать константу различимости 2еps > 0 и допустимую конечную длину интервала неопределенности l > 0. Пусть [a1,b1] - начальный интервал неопределенности. Положить k=1 и перейти к основному этапу.

     Основной  этап.

     Шаг 1. Если bk-ak < l, то остановиться; точка минимума принадлежит интервалу [ak,bk]. В противном случае вычислить pk=(ak+bk)/2-eps qk=(ak+bk)/2+eps и перейти к шагу 2.

     Шаг2. Если F(pk) < F(qk), положить a[k+1]=ak и b[k+1]=qk. В противном случае положить a[k+1]=pk и b[k+1]=bk. Заменить k на k+1 и перейти к шагу 1. 

3.МЕТОДЫ  БЕЗУСЛОВНОЙ МИНИМИЗАЦИИ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ

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

3.1.Многомерный  поиск без использования производных.

     Рассмотрим  методы решения минимизации функции  нескольких переменных f, которые опираются только на вычисление значений функции f(x), не используют вычисление производных, т.е. прямые методы минимизации. Важно отметить, что для применения этих методов не требуется не только дифференцируемости целевой функции, но даже аналитического задания. Нужно лишь иметь возможность вычислять или измерять значения f в произвольных точках. Такие ситуации часто встречаются в практически важных задачах оптимизации. В основном все описанные методы заключаются в следующем. При заданном векторе х определяется допустимое направление d. Затем, отправляясь из точки х, функция f минимизируется вдоль направления d одним из методов одномерной минимизации. Задача линейного поиска заключается в минимизации f(x+lym*d) при условии, что lym принадлежит L, где L обычно задается в форме L=E1, L={lym: lym >= 0} или L={l: a<=lym<=b}. Будем предполагать, что точка минимума lym* существует. Однако в реальных задачах это предположение может не выполняться. Оптимальное значение целевой функции в задаче линейного поиска может быть не ограниченным или оптимальное значение функции конечно, но не достигается ни при каком

lym. Некоторые из них: метод циклического покоординатного спуска, метод Хука и Дживса, метод Розенброка, метод минимизации по правильному симплексу, метод минимизации по деформируемому симплексу.

          Метод циклического покоординатного спуска.

     В этом методе в качестве направлений  поиска используются координатные векторы. Метод циклического покоординатного  спуска осуществляет поиск вдоль  направлений d1, ..., dn, где dj - вектор, все компоненты которого, за исключением j-ого, равны нулю.

      

Таким образом, при поиске по направлению dj меняется только переменная xj, в то время как все остальные переменные остаются зафиксированными. 

     Алгоритм  циклического покоординатного спуска  

     Начальный этап. Выбрать eps >0, которое будет использоваться для остановки алгоритма, и взять в качестве d1, ..., dn координатные направления. Выбрать начальную точку x1, положить y1 = x1, k=j=1 и перейти к основному этапу. 

     Основной  этап.

     Шаг 1. Положить lymj равным оптимальному решению задачи минимизации f(yj+lym*dj) при условии, что lym принадлежит E1. Положить y[j+1]= yj+lymj*dj. Если j < n, то заменить j на j+1 и вернуться к шагу 1. Если j=n, то перейти к шагу 2.

     Шаг 2. Положить x[k+1] = y[n+1]. Если || x[k+1] - xk || < eps, то остановиться. В противном случае положить y1= x[k+1], j=1, заменить k на k+1 и перейти к шагу 1.

           Метод Хука и Дживса.

     Метод Хука и Дживса осуществляет два типа поиска - исследующий поиск и поиск  по образцу. Первые две итерации процедуры  показаны на рисунке.

     

     1-поиск  по образцу; 2- исследующий поиск  вдоль координатных осей.

     При заданном начальном векторе x1 исследующий  поиск по координатным направлениям приводит в точку x2 . Последующий  поиск по образцу в направлении x1- x2 приводит в точку y. Затем исследующий  поиск, начинающийся из точки y, дает точку x3. Следующий этап поиска по образцу  вдоль направления x3- x2 дает y*. Затем  процесс повторяется. 

     Алгоритм  Хука и Дживса с использованием одномерной минимизации.

     Рассмотрим  вариант метода, использующий одномерную минимизацию вдоль координатных направлений d1,..., dn и направлений  поиска по образцу. 

     Начальный этап. Выбрать число eps > 0 для остановки алгоритма. Выбрать начальную точку x1, положить y1= x1, k=j=1 и перейти к основному этапу.

     Основной  этап.

     Шаг 1. Вычилить lymj - оптимальное решение задачи минимизации f(yj+lym * dj) при условии lym принадлежит E1. Положить y[j+1]= yj+lymj*dj. Если j < n, то заменить j на j+1 и вернуться к шагу 1. Если j=n, то положить x[k+1] = y[n+1]. Если ||x[k+1] - xk|| < eps , то остановиться; в противном случае перейти к шагу 2.

Информация о работе Методы оптимизации