Нахождение экстремумов функций двух переменных приближёнными методами

ВСР №4. Тема: «Нахождение экстремумов функций двух переменных приближёнными методами».

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

Содержание  учебного материала:

1. Функции нескольких переменных.
2. Частные производные и полный дифференциал 1-го порядка.
3. Градиент функции. Производная по направлению.
4. Экстремум функции двух переменных.
5. Приближённые методы решения задач.
1. Метод Хука – Дживса.
2. Метод Нелдера – Мида.

3. Метод полного  перебора (метод сеток).

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

6. Примеры решения задач в MathCAD.
7. Вопросы и задания.
8. Список рекомендуемых источников.

Функции нескольких переменных

Определение. Переменная z называется функцией переменных х и у, если каждой паре значений х и у в некоторой области их изменения поставлено в соответствие  одно значение z. Функциональную зависимость z от х и у записывают в виде: z=f(x,у). Это уравнение определяет некоторую поверхность в пространстве R³. 
     Геометрическим образом функции z=x²+y² является параболоид. Пусть z=a, тогда x²+y²=a, т.е. линия пересечения плоскости z= a с поверхностью z=x²+y² есть окружность x ²+ y ²= a радиуса . Пусть у=0, тогда z=x² и, следовательно, при пересечении плоскости Oхz с поверхностью получается парабола. Метод сечений дает возможность лучше представить себе геометрический образ данной функции.

 
 
       
     Определение. Число А называется пределом функции z=f(x,у) в точке М₀(х₀, у₀), если для каждого числа ε>0 найдется такое число β>0, что для всех точек М(х,у), для которых выполняется неравенство |ММ₀|<β, будет выполняться неравенство | f(x,у)– A|< ε 
    

Обозначим

  . 
     Определение. Функция z=f(x,у) называется непрерывной в точке М₀(х₀,у₀), если имеет место равенство

  .

 

Частные производные и  полный дифференциал 1-го порядка

Определение. Производная от функции z=f(x,у) по х, найденная в предложении, что у остается постоянным, называется частной производной от z по х и обозначается  или f'_x (x,у). Аналогично определяется и обозначается частная производная z по у. 
     Если функция z=f(x,у) имеет в точке (х,у) непрерывные частные производные, то ее полное приращение может быть представлено в виде:  
     ,                                             (1) 
     где  при . 
     Определение.  Выражение  является главной частью полного приращения Δz и называется полным дифференциалом функции z=f(x,у) и обозначается dz: 
     .                                                          (2) 
     Полагая в формуле (2) z равным х, найдем , а при z=y . Поэтому  
     .                                                           (3) 
     Из (1) следует, что . 
     Функция f(x,y) называется дифференцируемой в точке (х,у), если она имеет в этой точке полный дифференциал. 
     Пример. Найти полный дифференциал функции . 
     Решение. Сначала найдем частные производные 
      
      
     Производная  найдена в предположении, что у постоянна, а  найдена в предположении, что х постоянна. По формуле (3): 
     . 
     Ответ. dz=(10 x–6xy³) dx+(9 x² y²+6) dy.

Градиент  функции. Производная  по направлению

Определение. z=f(x,у) дифференцируемая функция двух переменных. Тогда вектор  называется градиентом функции z=f(x,у). 
     Он обладает следующими свойствами: 
      
      
      
     Пусть  – направляющие косинусы некоторого вектора , т.е. . Тогда  – производная функции z=f(x,у) в данном направлении .

Экстремум функции двух переменных

Определение. Функция z=f(x,у) имеет в точке М₀(х₀,у₀) максимум, если в окрестности этой точки выполняется равенство f(x,у)<f(x₀,у₀). 
      Аналогично определяется минимум функции z=f(x,у) в точке М₀(х₀, у₀). 
Необходимый признак экстремума 
     Если М (х₀,у₀) – точка экстремума дифференцируемой функции z=f(x,у)), то  
      то есть

Достаточный признак экстремума 
     Пусть z=f(x,у) – функция, для которой существуют производные первого и второго порядка в точке М(х₀,у₀):     . Составим выражение Δ=АС–В². 
     Если Δ>0, то М(х₀, у₀) – точка экстремума, а именно: точка максимума при A<0 (если C<0), точка минимума при A>0 (или С>0). Если Δ<0, то в точке М нет экстремума.

Приближённые  методы решения задач

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

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

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

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

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

     Описание  этой процедуры представлено ниже:

     А. Выбрать начальную базисную точку b₁ и шаг длиной h_j для каждой переменной x_j, j = 1, 2, ..., n. В приведенной ниже программе для каждой переменной используется шаг h, однако указанная выше модификация тоже может оказаться полезной.

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

     1. Вычисляется значение функции f(b₁) в базисной точке b₁.

     2. Каждая переменная по очереди  изменяется прибавлением длины  шага.

     Таким образом, мы вычисляем значение функции f(b₁ + h₁e₁), где e₁ - единичный вектор в направлении оси х₁. Если это приводит к уменьшению значения функции, то b₁ заменяется на b₁ + h₁e₁. В противном случае вычисляется значение функции f(b₁ – h₁e₁), и если ее значение уменьшилось, то b₁ заменяем на b₁-h₁e₁. Если ни один из проделанных шагов не приводит к уменьшению значения функции, то точка b₁ остается неизменной и рассматриваются изменения в направлении оси х₂, т.е. находится значение функции f(b₁ + h₂e₂) и т.д. Когда будут рассмотрены все n переменные, мы будем иметь новую базисную точку b₂.

     3. Если b₂ = b₁, т.е. уменьшение функции не было достигнуто, то исследование повторяется вокруг той же базисной точки b₁, но с уменьшенной длиной шага. На практике удовлетворительным является уменьшение шага (шагов) в десять раз от начальной длины.

     4. Если  , то производится поиск по образцу.

     В. При поиске по образцу используется информация, полученная в процессе исследования, и минимизация функции завершается поиском в направлении, заданном образцом. Эта процедура производится следующим образом:

     1. Разумно двигаться из базисной  точки b₂ в направлении b₂ - b₁, поскольку поиск в этом направлении уже привел к уменьшению значения функции. Поэтому вычислим функцию в точке образца

     В общем случае

     2. Затем исследование следует продолжать  вокруг точки P₁ (P_j).

     3. Если наименьшее значение на  шаге В,2 меньше значения в базисной точке b₂ (в общем случае b_j+1), то получают новую базисную точку b₃ (b_j+2), после чего следует повторить шаг В,1. В противном случае не производить поиск по образцу из точки b₂ (b_j+1) а продолжить исследования в точке b₂ (b_j+1).

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

     Ниже  приведена блок-схема данного  метода.

 
Рис. 2. 

 
Рис. 3. 

Метод Нелдера – Мида

     Метод Нелдера — Мида (называется также поиском по деформируемому многограннику) является развитием симплексного метода Спендли, Хекста и Химсворта. Множество (n + 1)-й равноудаленной точки в n-мерном пространстве называется регулярным симплексом. Эта конфигурация рассматривается в методе Спендли, Хекста и Химсворта. Следовательно, в двумерном пространстве симплексом является равносторонний треугольник, а в трехмерном пространстве — правильный тетраэдр. Идея метода состоит в сравнении значений функции в (n + 1) вершинах симплекса и перемещении симплекса в направлении оптимальной точки с помощью итерационной процедуры. В симплексном методе, предложенном первоначально, регулярный симплекс использовался на каждом этапе. Нелдер и Мид предложили несколько модификаций этого метода, допускающих, чтобы симплексы были неправильными. В результате получился очень надежный метод прямого поиска, являющийся одним из самых эффективных, если .