Приближённые методы поиска экстремальных значений функций нескольких переменных

Тема 8.   Приближенные  методы  поиска  экстремальных  значений  функций  нескольких  переменных.

Ограничимся  рассмотрением  функций  двух  переменных  вида  z = f(x,y),  которую  будем  считать  имеющей  вторые  частные  производные  по  каждой  независимой  переменной.  Определение  глобальных  и  локальных  экстремумов  для  такой  функции  аналогично  приведенным  выше  определениям  для  функции  одной  переменной.  Отличием  является  то,  что  экстремум  ищется  не  на  отрезке  (как  в  случае  однгой  переменной),  а  в  области  G  изменения  двух  переменных  -  xÎ[a_x, b_x],  yÎ[a_y, b_y].

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

                               .                                                                                             (8.1)

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

                    .                                                         (8.2)

Из  условия    следует  утверждение,  что  знаки    совпадают.

Рекомендуемые материалы

При  этом,   

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

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

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

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

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

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

Метод  сетки   предназначен  для  поиска  глобального  экстремума  функции  в  заданной  области.  Суть  метода  состоит  в  том,  что  вся  область G   {xÎ[a_x, b_x],  yÎ[a_y, b_y]}  по  каждой  координате  покрывается  “сеткой”  -  множеством  точек,  удаленных  друг  от  друге  на  более  чем  на  величину  заданной  точности  e>0.  Таким  образом,  вся  прямоугольная  область  G  окажется  прокрытой  прямоугольной  сеткой  с  шириной  каждой  ее  ячейки  не  более  величины  e,   а  затем  в  каждом  узле  такой  сетки  вычисляются  значения  функции.  Далее  из  них  выбирается  минимальное  (или  максимальное),  которое  (вместе  с  соответствующими  ей  значениями  переменных  x  и  y)  и  будет  принято  в  качестве  искомого  значения  глобального  экстремума  заданной  функции  в  заданной  области.  Выбор  шага  разбивки  интервалов  изменения  каждой  независимой  переменной  производится  аналогично  ранее  описанному  случаю  одной  независой  переменной.

Метод  покоординатного  спуска предназначен  для  поиска  локального  экстремума  функции  z=f(x,y)  в  заданной  области.  Для  начала  поиска  необходимо  найти  начальное  приближение  искомой  точки  (x₀, y₀).   Затем  производится  фиксация  значения  переменной  y  на  значении y₀    и  поиск  экстремума  функции 

                                            z = f(x, y₀) = j(x)                                                                           (8.3)

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

                                           z = f(x₁, y) = y(y)                                                                            (8.4)

как  функции  одной  переменной  y.   Ее  экстремум  (в  заданной  области)  находят  в  точке  y₁.  Таким  образом,  от  исходной  точки  (x₀, y₀)  в  два  этапа  произведен  переход  к  точке  (x₁, y₁).  Значение  функции  в  ней  ближе  к  искомому  экстремальному  значению.  Повторяя  снова  те  же  действия,  можно  получить  новые  точки  (x_i, y_i)  (i=2, 3, …),  значения  функции  в  которых  постепенно  и  монотонно  будет  стремиться  к  экстремальному.  Процесс  завершается,  если

                                           max(|x_i+1- x_i|, |y_i+1 - y_i|)                                                                    (8.5)

 станет  меньше  заданной  точности.   

Процес  поиска  значения  экстремума  этим  методом  удобно  проводить  с  занесением  результатов   расчетов  в  таблицу  следующего  вида   (в  ней  введено  обозначение  D= Max(| x_i+1- x_i|, | y_i+1- y_i|)

При  использовании  для  расчетов  Excel  для  поиска  минимумов  функций  и  удобно  использовать  опцию  Поиск  решения  из  меню  Сервис.

Пример 2.  Вычислить  методом  покоординатного  спуска  минимум  функции  двух  переменных    z = f(x, y) = 2(x-0.2)² + (y-0.8)² + 3   в  области G   {xÎ[0, 4],  yÎ[0, 2]}  с  точностью  0.01.

Анализ заданной  функции  на  наличие  локального  минимума  в  заданной  области  мы  произвели  в  примере  1.  За  начальное  приближение  искомой  точки  минимума  примем  средину  заданной  области.  Таким  образом  имеем  (x₀, y₀)= (2, 1).

Результаты  расчетов  в  Excel  приведены  в  виде  таблицы

Решение  найдено  за  два  шага  -  минимум  функции      f_min = 3.000  и  достигается  он  в  точке   x_min = 0.2000  и  y_min =0.8000.

Пример 3.  Вычислить  методом  покоординатного  спуска  минимум  функции  двух  переменных   z = f(x, y) = 2(x+0.1y-0.1)² + Sin²(0.5x+y-0.5)   в  области  G   {xÎ[0, 1],  yÎ[0, 0.75]}  с  точностью  0.01.

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

                      f_x^’(x,y)=4(x+0.1y-0.1)+0.5Sin(x+2y-1)

                      f_y^’(x,y)=0.4(x+0.1y-0.1)+Sin(x+2y-1)

                      f_xx^’’(x,y)=4+0.5Cos(x+2y-1)

                      f_xy^’’(x,y)=0.4+Cos(x+2y-1)

                      f_yy^’’(x,y)=0.04+Cos(x+2y-1)

                     D= f_xx^’’ f_yy^’’-( f_yy^’’)²=3.22Cos(x+2y-1) – 0.5 Cos² (x+2y-1)>0

                      f_xx^’’>0.

Следовательно,  в  области  G   {xÎ[0, 1],  yÎ[0, 0.75]}  заданная  функция  имеет  локальный  минимум.  За  начальное  приближение  искомой  точки  минимума  примем  левый  нижний  угол  этой  области,  т.е.  (x₀, y₀)= (0, 0).

Результаты  расчетов  в  Excel  приведены  в  виде  таблицы

Решение  найдено  за  четыре  шага  -  минимум  функции  f_min = 0.000  и  достигается  он  в  точке   x_min = 0.0540  и  y_min = 0.4728.

Метод  найскорейшего  спуска  предназначен  для  поиска  локального  экстремума  функции  z = f(x,y)  в  заданной  области.  В  отличие  от  метода  покоординатного  спуска,  движение  к  точке  экстремума  ведется  не  по  координатным  линиям,  а  по  направлению  наиболешего  изменения  значения  функции.  Такое  направление  задается  вектором,  называемым  градиентом  функции.  Этот  вектор,  обозначаемый  ,  состоит  из  двух  компонент.  Они  равны  значениям  частных  производных  функции  f  по  каждой  из  двух  независимых  переменных,  т.е.

                                                      .                                                                  (8.6)

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

 Для  начала  поиска  необходимо  найти  начальное  приближение  искомой  точки,  которое  представим  в  виде  вектора   с  координатами  (x₀, y₀)^Т.  Затем  вычислим  в этой  точке  значения  координат   вектора    и   вектор  движения  вдоль  него  в  сторону  экстремума  с  точки   (x₀, y₀).  Это  направление  зададим  вектором    следующего  вида

                                             ,                                                                   (8.7)

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

                .        (8.8)

В  этой  формуле  знак   “±”   необходимо  заменить  на  “+”  при  поиске  максимума,   и  на  “-“  при  поиске  минимума.   Подставляя  полученные  таким  образом  выражения  для  координат  x  и  y  в  исходную  функцию,  получим

           .                                  (8.9)

Таким  образом,  мы  получили  функцию  от  одной  переменной  t.   Найдя  ее  экстремум  (минимум  или  максимум,   исходя  из  задания),  мы  найдем  точку  достижения  этого  экстремума  и  обозначим  ее  через  t₁.  Подставляя  затем  это  значение  t = t₁  в  формулу  (8.8),  получим  следующее  приближение   с  координатами  (x₁, y₁)^Т

                                      .                                          (8.10)

Таким  образом,  от  исходной  точки  (x₀, y₀)  произведен  переход  к  точке  (x₁, y₁).  Значение  функции  в  ней  ближе  к  искомому  экстремальному  значению.

Аналогично  вышеописаному,  в  точке     снова  найдем  значение  градиента  функции,  вычислим  координаты  вектора    и  координаты  вектора  движения  вдоль  него.   Затем  подставим  их  в  заданную  функцию  и  приведем  ее  к  функции  одной  независимой  переменной.  Найдем  ее  экстремум  в  точке  t₂   и  найдем  точку  (x₂, y₂).  Повторяя  снова  те  же  действия,  можно  получить  новые  точки  (x_i, y_i)  (i=3, 4, …),  значения  функции  в  которых  постепенно  и  монотонно  будет  стремиться  к  экстремальному.  Этот  процесс  завершается,  если  следующая  точка  будет  мало  отличаться  от  предыдущей.  Точнее  это  можно  выразить  так,  что  должно  быть  max(|x_i+1 - x_i|, |y_i+1 - y_i|)  меньше  заданной  точности.  Результаты  расчетов  удобно  представлять  в  виде,  приведенном  в  нижеследующем  примере.

Пример 4.  Вычислить  методом  найскорейшего  спуска  минимум  функции  двух  переменных   z = f(x, y) = x² + 5y²   в  области  G   {xÎ[-1, 1],  yÎ[-2, 3]}  с  точностью  0.01.

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

                      f_x^’(x,y)=2x;                  f_y^’(x,y)=10y;

                      f_xx^’’(x,y)=2;            f_xy^’’(x,y)=0;              f_yy^’’(x,y)=10.

                     D= f_xx^’’ f_yy^’’-( f_yy^’’)²=20>0;

                      f_xx^’’>0.

Следовательно,  в  области  G   {xÎ[-1, 1],  yÎ[-2, 3]}  заданная  функция  имеет  локальный  минимум.  За  начальное  приближение  искомой  точки  минимума  примем  правый  верхний  угол  области  -  (x₀, y₀)= (1, 3).

Результаты  расчетов  в  Excel  приведены  в  виде  таблицы

Решение  найдено  за  пять  шагов  -  минимум  функции   f_min = 0.000  и  достигается  он  в  точке   x_min = 0.0002  и  y_min = 0.0000.