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

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

 

Классические методы функции одной  переменной.

 

Дана функция y=f(x)-целевая функция. Функция одной переменной, имеющая в интервале исследования один горб(впадину) называется унимодальной.

Более строго:                                                                     

Определение: функция f(x), заданная на интервале a<=x<=b называется унимодальной на [a,b], если существует единственная точка x* минимума f(x), т.е. f(x*)=min F(x) {на a<=x<=b}                                                                   и если для любых двух точек x₁,x₂ принадлежащих [a,b] выполняется соотношение:

-из неравенств x₁<x₂<=x* следует f(x₁)>f(x₂);

-из неравенств x₂>x₁=>x* следует F(x₁)<F(x₂).

 

Необходимое условие  минимума(максимума) функции f(x) в точке x*.

Необходимые условия того, что x* является точкой локального минимума (максимума) дважды дифференцируемой функции f на открытом интервале (a,b) выражаются следующими соотношениями:

1)    df                        2)      d²f

                       =0                                     =>0(<=0)

       dx     x=x*                   dx²      x=x*

Определение:

Стационарной точкой называется точка x*, в которой

     df

                        =0

     dx     x=x*

 

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

 

Пример:

                                          f(x)=x³

 

 

                                                              x*                     x

 

 

                                                             Точка перегиба(седловая точка)

 

 

Достаточные условия экстремума.

 

Пусть в точке  x* первые (n-1) производные функции обращаются в нуль, а производная порядка n отлична от нуля.

(1)Если n-нечетное, то x*-точка перегиба.

(2)Если n-четное, то x*-точка локального оптимума.

Кроме того,

(а)если эта производная положительная,  то x*-точка локального минимума

(б)если эта производная отрицательная,  то x*-точка локального максимума

Пример:

Исследуем функцию f(x)=x³ на оптимум в точкеx=0.

Вычисляем

df                                      d²f                                   d³f

              =3x²          =0;                   =6x          =0;                =6.

dx    x=0           x=0         dx²    x=0          x=0        dx³  x=0

Так как порядок  первой отличной от нуля производной  равен 3 (нечетное число), точка x=0 является точкой перегиба.

Пример:

Дана функция

f(x)=5x⁶ - 36x⁵ + (162/2)x⁴ - 60x³ + 36,определенная на всей действительной оси. Определить точки локальных минимумов и максимумов.

Вычисляем:

df/dx=30x⁵ – 180x⁴ + 330x³ – 180x² = 30x²(x-1)(x-2)(x-3)

Первая производная обращается в нуль в точках x=0,1,2,3-это стационарные точки.

Вычисляем:

d²f/dx²=150x⁴ – 270x³ + 990x² – 360x

  d²f

                 =0       , пока ничего нельзя сказать об этой точке

  dx²   x=0

 

  d²f

                =60>0  ,  x=1 – точка локального минимума

  dx²  x=1

 

  d²f

               = -120<0, x=2 – точка локального максимума

  dx²  x=2

  d²f

               =540>0,    x=3 – точка локального минимума

  dx²  x=3

Чтобы идентифицировать точку x=0, вычислим третью производную

  d³f

                =(600x³-2160x²+1980x-360)           = -360

  dx³  x=0                                                  x=0

Т.к. эта производная  не равна нулю и имеет нечетный порядок, то точка x=0 является не точкой оптимума, а точкой перегиба.

 

Определение глобального максимума  или минимума функции одной переменной.

Пусть требуется  максимизировать f(x) при ограничениях a<=x<=b, где a и b – установленные границы измерений переменной x.

(Очевидно  в этом случае проверку наличия  локального оптимума необходимо  проводить не только в стационарных  точках, но и в граничных точках  интервала)

Алгоритм  следующий:

Шаг 1: приравнять df/dx=0 и найти все стационарные точки.

Шаг 2: выбрать все стационарные точки, которые расположены а интервале [a,b]. Обозначим эти точки через x₁,x_2,…,x_n. Проверку наличия локального оптимума следует проводить только на множестве указанных точек, дополненном точками a и b.

Шаг 3:найти наибольшее значение f(x) из множества f(a),f(b),f(x₁),…,f(x_n). Это значение соответствует глобальному максимуму.

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

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

Пример:

Максимизировать

f(x)= -x³ +3x² +9x +10=0 на интервале –2<=x<=4

Решение:

Имеем

df/dx= -3x² +6x +9=0

             3(x-3)(x+1)=0

Решая это уравнение, получаем две  стационарные точки:

x=3, x= -1

Они расположены внутри заданного  интервала.

Для того чтобы найти глобальный максимум, вычислим значения f(x) в точках           x=3, -1, -2 и 4.

f(3)=37; f(-1)=5;f(-2)=12;f(4)=30.

Ответ: точка x=3 соответствует максимальному значению f на интервале   [-2,4].

 

Выпуклые и вогнутые функции.

(Это важный класс унимодальных  функций)

Введем обозначение: x=(x₁,x₂,…,x_n)-n-мерный вектор.

Определение:

Функция n мерных f(x), определенная на выпуклом множестве D, называется выпуклой функцией тогда и только тогда, когда для любых двух точек x⁽¹⁾ и x⁽²⁾ принадлежащих D, и любого числа L (0<=L<=1) выполняется неравенство:

f(Lx⁽¹⁾ +(1-L)x⁽²⁾)<=Lf(x⁽¹⁾)+(1-L)f(x⁽²⁾).

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

 

 

        f(x)

 

                                               Lf(x₁)+(1-L)f(x₂                 f(x₂)

                                               

                      f(x₁)

 

                                                                                                   выпуклая

                                                                                                    функция

 

                               x₁                Lx₁+(1-L)x₂                 x₂         x

 

 

Свойства  выпуклых функций:

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

2.Выпуклая функция лежит над  своими касательными

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

4.Вторая производная f(x) всегда не отрицательна на рассматриваемом интервале.

5.Для выпуклой функции локальный  минимум всегда является глобальным  минимумом.

Градиент функции f(x₁,x₂,…,x_n) определяется как вектор

 

           f(x₁,…,x_n)=(df/dx₁,df/dx₂,…,df/dx_n)^T.

 

Матрица Гессе(гессиан) для функции f(x₁,…,x_n) есть симметрическая матрица порядка n*n:

H_f(x₁,…,x_n)=[d²f/dx_idx_j]=     ²f.

 

Проверка функции на выпуклость.

Функция f(x₁,…,x_n) выпуклая, если ее матрица Гессе положительно определена или положительно полуопределена для всех значений x₁,x₂,…,x_n .

Для функции  одной переменной: функция f(x) выпуклая, если ее вторая производная неотрицательна для всех значений x:

d²f/dx²=>0, для всех x.

Если матрица  Гессе H_f – положительно определенная матрица, то f называется строго выпуклой функцией и обладает единственной точкой минимума.

 

Проверка матриц на положительную  определенность.

1)Все диагональные  элементы должны быть положительными.

2)Все ведущие  главные определители должны  быть положительными.

Пример:

                    1 2 3

Матрица     4 5 6

                    7 8 9

Ведущие главные определители:

                       1 2 3

1,      1 2  ,      4 5 6

         4 5         7 8 9     .

Проверка матриц на положительную  полуопределенность:

1)Все диагональные элементы  неотрицательны.

2)Все главные определители неотрицательны.

Главные определители:

                                       1 2 3

1,5,9,   1 2 ,  1 3 ,  5 6 ,  4 5 6 

            4 5    7 9    8 9    7 8 9

Замечание:

Чтобы установить, что данная матрица  является отрицательно определенной (полуотрицательно определенной), следует умножить ее на  -1 и проверить полученную матрицу  на положительную определенность (полуположительную  определенность).

 

Вогнутая функция.

Функция f(x₁,…,x_n) является вогнутой функцией на множестве D тогда и только тогда, когда –f(x) есть выпуклая функция на D.

 

Проверка функции на вогнутость.

Функция f(x₁,…,x_n) вогнутая, если ее матрица Гессе отрицательно определена, или отрицательно полуопределена для всех значений x₁,…,x_n.

Пример:

Исследовать функцию на выпуклость.

f(x₁,x₂,x₃)=3x₁² +2x₂² +x₃² –2x₁x₂ –2x₁x₃ +2x₂x₃ –6x₁ –4x₂ –2x₃

                                    6x₁ –2x₂ –2x₃ –6

            f(x₁,x₂,x₃)=      4x₂ –2x₁ +2x₃ –4

                                    2x₃ –2x₁ =2x₂ –2

                            6  -2   -2

H_f (x₁,x2,x3)=   -2    4    2

                          -2    2    2

Исследуем H_f.

1. H_f –симметрическая матрица.
2. Все диагональные элементы H_f положительны.
3. Ведущие главные определители Н равны:

                                                    6   –2  –2 

        6 >0      6   –2   =20>0        –2   4    2     =16>0

                    –2   4                       –2   2    2 

                                                                     (см. кн.2,с.302)

Следовательно, H_f – положительно определенная матрица.

Отсюда следует, что f-выпуклая функция.

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

Пример:

                 1 2 3               5 6         2 3        2 3

        A=    4 5 6 ;  A =1  8 9   -4   8 9   +7 5 6

                 7 8 9

 A_nxn, то |A|= ⁿ     _i=1  a_i1(-1)ⁱ⁺¹|M_i1|

M_i1-подматрица матрицы A, полученная путем исключения строки i и столбца1.

Исследовать свойства функции:

f(x)=(2x+1)²(x-4)

Вычисляем:

f ^|=2(2x+1)2(x-4)+(2x+1)²=(2x+1)(6x-15)

f ^||=2(6x-15)+6(2x+1)=24(x-1)

При x<=1 имеем f ^||<=0, следовательно, функция является вогнутой в заданной области.

Если x=>1, то f ^|| =>0, т.е. функция является выпуклой в этой области.

Найдем  стационарные точки из уравнения

f^|(x)=(2x+1)(6x-15)=0

x=-1/2 и x=5/2 – стационарные точки.

 

Вычислим

f^||(-1/2)=24(-1/2-1)<0,  следовательно функция обладает локальным максимумом при x=-1/2.

Вычислим

f^||(5/2)=24(5/2-1)>0, следовательно функция достигает в точке x=5/2 локального минимума.

Если  ограничить допустимую область неравенством x<=1, то f(x) имеет глобальный максимум при x=-1/2, т.к. f(x)-вогнутая функция(в данной области) и x=-1/2 – точка локального максимума.

Аналогично, если ограничить допустимую область  неравенством x=>1, то f(x) достигает глобального минимума при x=5/2.

Однако, если переменная x изменяется на всей действительной оси от –00 до +00, то функция f(x) не имеет конечного глобального максимума или минимума.

Примерный вид функции:

 

                                   max

                             -1   -1/2   0            1        2    5/2    3                              x

 

 

 

 

 

 

                                                                             min

Пример. (Задача управления запасами).

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

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

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

Для решения  этой задачи часто используется так  называемая модель определения наиболее экономичного размера заказа. (Заказ на товары для создания запаса).

В рамках этой модели спрос предполагается постоянный и равный l единиц товара в год.

Частное пополнение запасов (выполнение заказов) нецелесообразно, т.к. стоимость выполнения одного заказа составляет К рублей независимо от его размера.

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

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

Проиллюстрируем изменение объема запасов с течением времени на рисунке.

Циклы управления запасами.

 

                            q(t)=Q-Qt/T

                B

Q    объем

    запасов

 

                  A         C                                                     время,t

                        T

 

В точке  А объем запасов равен Q; затем объем запасов начинает уменьшаться со скоростью l единиц товара в единицу времени и достигает нулевого значения в точке С.

В это  время поступает новая партия товара (выполняется заказ), и объем  запасов восстанавливается.

Треугольник ABC представляет один цикл управления запасами, который повторяется во времени.

Задача  заключается в том, чтобы определить оптимальный размер заказа (объем  запасов) Q и продолжительность интервала времени между заказами T, T=C-A.

T-это величина промежутка времени, в течении которого при скорости расходования l истощается запас Q, поэтому:

T=Q/l.

Таким образом, задача сводится к нахождению оптимального значения Q.

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

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

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

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

Полные  затраты/год=(затраты/цикл)*(кол-во циклов/год)

Кол-во циклов (заказов)/год=1/T=l/Q.

Затраты/цикл=затраты на выполнение заказа + затраты на хранение запасов.

Затраты на выполнение заказов = К.

Определим затраты на хранение запасов в  течении цикла (т.е. в течении времени  Т).

q(t)=Q-Qt/T-функция изменение запасов за цикл.

Затраты на хранение запасов в течении  промежутка времени [t,t+dt] равны hq(t)dt,     h-стоимость хранение единицы товара в единицу времени. Тогда затраты на хранение запасов/цикл равны:

_{Т                        T                                          T                       T                                                      T}

òhq(t)dt = hò(Q-Qt/T)dt = hQòdt - hQ/Tòtdt = hQT-(hQ/T)t²/2 =hQT-(hQ/T)T²/2=

^{0                        0                                           0                       0                                                       0}

= hQT/2 = hQ²/(2l), т.к. T=Q/l.

Итак,

Затраты/цикл = K+hQ²/(2l)

Полные затраты/год = (K+hQ²(2l))l/Q=lK/Q+hQ/2.

Таким образом, функция полных затрат (целевая функция):

f(Q) = lK/Q + hQ/2        min

Вычислим:

f^|(Q) = -lK/Q² +h/2

Вычислим:

f^||(Q) = 2lK/Q³ > 0, при всех Q>0.

Отсюда  следует, что f(Q) – выпуклая функция,и если существует положительное значение Q*, такое, что f^|(Q*) =0, то Q* минимизирует f(Q).

Решим уравнение:

f^|(Q) = 0

-lK/Q² + h/2 = 0

lK/Q² = h/2

Q² = 2lK/h

Q* = Ö2lK/h > 0 –оптимальный размер заказа.

При этом:

T* = Q*/l=Ö2K/(hl) – интервал времени между заказами.

Величина  Q* известна в теории управления как наиболее экономичный размер запаса.

 

Методы исключения интервалов.

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

Среди этих методов можно выделить методы исключения интервалов.

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

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

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

Правило исключения интервалов.

Пусть функция  f унимодальна на интервале a£x£b, а ее минимум достигается в точке x*.

Рассмотрим  точки x₁ и x₂, расположенные в интервале таким образом, что a<x₁<x₂<b.

Сравнивая значения функции в точках x₁ и x₂, можно сделать следующие выводы:

1. Если f(x₁)>f(x₂), то точка минимума f(x) не лежит в интервале (a,x₁), т.е. x*Î(x₁,b)

        f(x)

       f(x₁)

       f(x₂)

 

 

                       a  x₁   x*            x₂         b       x

 

2.Если f(x₁)<f(x₂), то точка минимума не лежит в интервале (x₂,b), т.е. x*Î(a,x₂)

 

 

 

 

     f(x)

        f(x₁)

        f(x₂)

 

 

                              a               x₁        x*          x₂  b      x

3.Если f(x₁)=f(x₂), то можно исключить оба крайних интервала (a,x₁) и (x₂,b), при этом x*Î(x₁,x₂).

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

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

Достоинства этих методов:

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

(при этом не требуется,  чтобы исследуемые функции были  дифференцируемы).

В процессе применения рассматриваемых методов  поиска можно выделить два этапа:

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

 

Этап установления границ интервала.

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

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

Рассмотрим  один из эвристических методов такого поиска, предложенный Свенном.