Содержание:

Список Литературы 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

                                            1. Основные понятия

1.1 Визначення.

    Під оптимізацією розуміють процес вибору найкращого варіанту з усіх можливих. З точки зору інженерних розрахунків методи оптимізації дозволяють  найкращий варіант конструкції, найкращий розподіл ресурсів та інше.

    В процесі розв’язку задачі оптимізації ,як звичай,необхідно знайти оптимальне значення деяких параметрів,які визначають дану задачу.При розвязку інженерних задач їх прийнято називати проектними параметрами, а в задачах економіки їх называють параметрами плана. В якості проектних параметрів можуть бути,зокрема,значення лінійних розмірів обєкта, маси, температури й інше число n проектних параметрів x₁,x₂,…,x_n які характеризують розмірність ( й степінь складності) задачі оптимізації.

    Вибір оптимального рішення або порівняння двох альтернативних розв’язків проводиться за допомогою деякої залежної величини (функції),обумовленої проектними параметрами.Ця велечина називається цвілевою функцією (або критерієм якості).В процесі розв’язку задачі оптимізації повинні бути знайдені такі значення проектних параметрів, при яких цілева функція має мінімум (або максимум). Таким чином, цілева функція – це глобальний критерій оптимальності в математичих моделях, за допомогою яких описуються инженерні або экономичні задачі.

    Цілеву функцію можно записати у вигляді:

U=F(x₁, x₂,…,x_n).                              (1.1)

    Прикладами цвілевої функції,які зустрічаються у інженерних та економічних розрахунках,є міцність й маса конструкції,потужність установки, обєм випуску продукції,вартість перевезень вантажу та шнше.

     У випадку одного проектного параметра цілева функція (1.1) є функцією однієї змінної,а її графік - деяка крива на площині.При цілева функція є функцією двох змінних, її графік — поверхня у тривимірному просторі.

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

   Цілевих функцій може бути декілька.Наприклад,при проектуванні виробів машино- будівництва одночасно потребується забезпечити максимальну надійність, мінімальну матеріалоємкість,максимальний корисний об’єм (або вантажопідємність).Деякі цілеві функції можуть здатися несумісними.В таких випадках необхідно вводити пріоритет тієї чи іншої цвілевої функції.

1.2 Задачі оптимізації. 

     Можно виділити два типи задач оптимізації — безумовні та умовні. Безумовна задача оптимізації складається у відшуканні максимуму або мінімуму дійсної функції (1.1) при дійсних змінних й визначенні значень аргументів на деякій множині σ  n-мірного простору. Звичайно розглядаються задачі мінімізації, що до них легко зводяться і задачі на пошук максимуму шляхом заміни знака цільової функції на протилежний.    Условные задачи оптимизации, или задачи с ограничениями, это такие, при формулировке которых задаются некоторые условия (ограничения) на множестве . Эти ограничения задаются совокупностью некоторых функций, удовлетворяющих уравнениям или неравенствам.

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

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

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

2.1 Задачи па экстремум.

       Одномерная задача оптимизации в общем случае формулируется следующим образом. Найти наименьшее (или наибольшее) значение целевой функции y=х, заданной на множестве σ, и определить значение проектного параметра х Є σ, при котором целевая функция принимает экстремальное  значение. Существование решения поставленной задачи вытекает из следующей теоремы.

  Методы поиска экстремума функции f (x) (одномерной оптимизации) 

          К числу наиболее популярных  численных методов одномерной  оптимизации относятся: метод Больцано (деления интервала пополам), метод «золотого сечения» и пошаговый метод. Первые два метода ориентированы на поиск  ext f (x) внутри фиксированного интервала (а,b) оси х, последний - на поиск ext f (x) в окрестности заданной точки х₀.

Метод Больцано при поиске минимума функции f (x) предусматривает следующие действия:

1) определяется  средняя точка интервала (а,b):  с = (a+b)/2;

2) выбирается  число  0 <d< (b-a)/2 (наиболее популярная рекомендация: d =(b-a)/4)  и определяются точки: x₁=c-d  и x₂=c+d ;

3) вычисляются  значения функции в этих точках: f (x₁)  и f (x₂);

4) если f (x₁)< f (x₂), то интервал (а,b)  стягивается в свою левую половину:  b=c, в противном случае - в правую: а=с.

          Для  нового интервала (а,b) вновь выполняются действия  п.п. 1)-4). Процесс  деления интервала продолжается до тех пор, пока его длина не станет меньше  заданной  точности:  b-а < e.  При завершении процесса поиска за точку минимума  f (x) принимается середина последнего отрезка:  x^*=(а+b)/2.

          Достаточные условия сходимости алгоритма метода Больцано:

        а) функция f (x) непрерывна внутри интервала;

        б) f (x) унимодальна на интервале (а,b), т.е. имеет внутри него единственный экстремум; 

        в) в некоторой окрестности  искомой точки х*  f (x) является монотонной

(с одной   стороны  возрастает, с другой - убывает).

          При тех же условиях сходится  алгоритм метода «золотого сечения».

          Определение:  «золотым  сечением» отрезка называется его деление на две части таким образом, что отношение длины отрезка к его большей части равно отношению большей части к меньшей.

      Следовательно, для отрезка единичной длины: 1/t = t/(1-t) ® t²+t-1=0 ®

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

           При поиске минимума функции  метод заключается в

следующем:

     1) выполняется пробный шаг от точки х₀ с целью выбора направления поиска:

x = x₀ + x (x ~ 0.5×e)  и вычисляются значения  f (х₀), f (х);

       2) если f (х) < f (х₀), то величина основного шага, с которым осуществляется движение в направлении убывания функции, положительна (h > 0), в противном случае - отрицательна (h < 0);

          3) движение в выбранном направлении  с шагом h: x_k+1= x_k+h, k=0,1,2 ...

осуществляется  до тех пор, пока f (x_k+1) <  f (x_k);

          4) если f (x_k+1) ≥ f (x_k),  то при выполнении условия h < ε процесс поиска заканчивается,  а если h ³ ε, то шаг дробится:  h=|h|/p, p > 1 и осуществляется возврат

к п. 1) с начальной  точкой х₀ = x_k.

          В качестве коэффициента дробления  шага p используют 2, 3, 5,  но чаще всего p = e = 2.71828.  По завершении процесса поиска за точку экстремума принимается значение x* =(x_k+1 + x_k)/2.

2.2 Методы  поиска.

      Численные методы поиска экстремальных значений функции рассмотрим на примере нахождения минимума функции на отрезке [а., b]. Будем предполагать, что целевая функция унимодальна, т.е. на данном отрезке она имеет только один минимум. Отметим, что в инженерной практике обычно встречаются именно такие целевые функции.

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

                  (2.1)

     Процесс решения задачи методом поиска состоит в последовательном сужении интервала изменения проектного параметра, называемого интервалом неопределенности. В начале процесса оптимизации его длина равна , а к концу она должна стать меньше , т. е. оптимальное значение проектного параметра должно находиться в интервале неопределенности – на отрезке , причем . Тогда для выполнения (2.1) в качестве приближения к оптимальному значению можно принять любое .

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

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

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

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

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

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

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

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

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

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

     Второй  шаг проводим на отрезке [a_1, b₁], где a₁ = a₀, b₁ = x₂. Нужно снова выбрать две внутренние точки, но одна из них (x₁) осталась из предыдущего шага, поэтому достаточно выбрать лишь одну точку x₃, вычислить значение f(x₃) и провести сравнение. Поскольку здесь f(x₃) > f(x₁), ясно, что минимум находится на отрезке [x₃, b₁]. Обозначим этот отрезок [a₂, b₂], снова выберем одну внутреннюю точку и повторим процедуру сужения интервала неопределенности. Процесс оптимизации повторяется до тех пор, пока длина очередного отрезка [a_n, b_n] не станет меньше заданной величины ε.

     Теперь рассмотрим способ размещения внутренних точек на каждом от резке [a_k, b_k]. Пусть длина интервала неопределенности равна l, а точка деления делит его на части l₁, l₂: l₁ > l₂, l = l₁ + l₂. Золотое сечение интервала неопределенности выбирается так, чтобы отношение длины большего отрезк к длине всего интервала равнялось отношению длины меньшего отрезка к длине большего отрезка: (1)

       Из этого соотношения можно найти точку деления, определив отношение l₂/l₁. Преобразуем выражение (1), и найдем это значение:

             l =l₂l₁, l =l₂(l₁ + l₂),

     l +l₁l₂ - l =0,

      ² + - 1 =0,

      = .

 Поскольку нас интересует только положительное решение, то

          .

       Отсюда l₁ k₁l, l₂ k₂l.

     Поскольку заранее неизвестно, в какой последовательности делить интервал неопределенности, то рассматривают внутренние точки, соответствующие двум этим способам деления. Точки деления x₁ и x₂ выбираются с учетом полученных значений для частей отрезка. В данном случае имеем

           x₁ – a₀ = b₀ – x₂ = k₂d₀,

     b₀ - x₁ = x₂ – a₀ = k₁d₀,

     d₀ = b₀ – a₀.

После первого шага оптимизации получается новый интервал неопределенности – отрезок [a_1, b₁].

         Можно показать, что точка x₁ делит этот отрезок в требуемом отношении, при этом

          b₁ – x₁ = k₂d₁, d₁ = b₁ – a₁.

         Для этого проведем очевидные преобразования:

           b₁ – x₁ = x₂ – x₁ = (b₀ – a₀) – (x₁ – a₀) – (b₀ – x₂) = d₀ – k₂d₀ - k₂d₀ = k₃d₀,

     d₁ = x₂ – a₀ = k₁d₀,

     b₁ – x₁ = k₃(d₁/k₁) = k₂d₁.

         Вторая точка деления x₃ выбирается на таком же расстоянии от левой границы отрезка, т.е. x₃ – a₁ = k₂d₁.

     И снова интервал неопределенности уменьшается  до размера

d₂ = b₂ – a₂ = b₁ – x₃ = k₁d₁ = k d₀.

 Используя полученные соотношения, можно записать координаты точек деления y и z отрезка [a_k, b_k] на k +1 шаге оптимизации (y < z):

y = k₁a_k + k₂b_k,

     z = k₂a_k + k₁b_k.

При этом длина  интервала неопределенности равна

  d_k = b_k – a_k = k d₀. 

     Процесс оптимизации заканчивается при  выполнении условия d_k < ε. При этом проектный параметр оптимизации составляет a_k < x < b_k. Можно в качестве оптимального значения принять x = a_k (или x = b_k, или x = (a_k + b_k)/2 и т.п.).

2.4 Метод Ньютона.

       Как было отмечено в п. 2.1, задача одномерной оптимизации дифференцируемой функции сводится к нахождению критических точек этой функции, определяемых уравнением:                          (2.7)

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

     Пусть - решение уравнения (2.7), а некоторое начальное приближение к . Применим для решения (2.7) метод Ньютона решения уравнения , которое эквивалентно уравнению (2.7) при . Для этого в формулу для -го приближения метода Ньютона подставим вместо производную и получим тем самым формулу для  -го приближения к решению уравнения (2.7):

             (2.8)

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

или близости значений целевой функции на этих приближениях

.

  Достаточное условие сходимости метода Ньютона (2.8) можно получить. А именно, справедлива следующая теорема.

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

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

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

(2.9)

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

 что совпадает с (2.8). Разложение (2.9) в окрестности точки , на котором график функции заменяется параболой графиком функции .

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

3. Многомерные задачи  оптимизации

3.1 Минимум функции  нескольких переменных.

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

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

             (3.1)

   Рассмотренный метод можно использовать лишь для дифференцируемой целевой функции. Но и в этом случае могут возникнуть серьезные трудности при решении систем нелинейных уравнений (3.1).

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

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

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

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

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

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

                             (3.2)

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

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

   На любом k-том шаге этот процесс можно прервать. И значение функции в точке k принимается в качестве наименьшего значения целевой функции в рассматриваемой области.

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

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

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

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

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