12250

Методы минимизации функции многих переменной

Лабораторная работа

Информатика, кибернетика и программирование

Лабораторная работа 3. Методы минимизации функции многих переменной. Постановка задачи: Требуется найти безусловный минимум функции от n переменных fx1 x2 xn т.е. такую точку что . Значение точки минимума вычислить приближенно с заданной точностью ε. Метод пр

Русский

2013-04-24

255.93 KB

57 чел.

Лабораторная работа 3.

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

Постановка задачи: Требуется найти безусловный минимум функции от n переменных f(x1, x2, …, xn), т.е. такую точку , что . Значение точки минимума вычислить приближенно с заданной точностью ε.

Метод правильного симплекса.

Стратегия поиска: Симплексом в Rn называется выпуклая оболочка (n+1) точек
x1, x2, …, xn+1, не принадлежащих ни к какому (n-1)-мерному подпространству Rn. Правильным симплексом называется множество из (n+1) равноудаленной точки. На плоскости (в двухмерном пространстве) правильный симплекс является правильным треугольником, в трехмерном пространстве правильный симплекс – правильный тетраэдр.

На первой итерации данного метода выбирается некоторый правильный симплекс в пространстве Rn . На каждой итерации сравниваются значения f(x) в вершинах симплекса. Затем преобразуется та вершина симплекса, в которой достигается максимальное значение. Преобразование происходит путем отражения  данной вершины симметрично относительно центра тяжести xC  остальных вершин. Если значение функции в полученной точке меньше, чем в исходной, то переходят к новому симплексу. Иначе пытаются осуществить процедуру отражения для остальных вершин исходного симплекса. Если все попытки неудачны, повторяют процедуру с уменьшенной длиной ребра до тех пор, пока данная длина не станет меньше заданной точности.

Алгоритм:

  1. Задать точность вычислений , выбрать начальное приближение , ребро a.
  2. Построить начальный правильный симплекс по заданному ребру a и точке .
  3. Вычислить значения f(x) в вершинах симплекса.
  4. Упорядочить вершины симплекса в порядке возрастания значений f(x).
  5. Найти и выполнить отражение вершины xn: . Если , то положить и перейти к шагу 3. Иначе перейти к шагу 6.
  6. По формулам, аналогичным формулам пункта 5, вычислить отражения вершин с номерами j = n-1, …, k. Где k выбирается из условия , либо
    k =1.
  7. Если k > 1, то положить и перейти к шагу 3. Иначе перейти к шагу 8.
  8. Выбрать новый размер ребра a = a / 2. Если a > перейти к пункту 2. Иначе остановка расчета и выбор в качестве точки минимума точки x0.

Метод деформируемого симплекса

(Метод Нелдера-Мида)

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

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

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

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

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

Стратегия поиска: Алгоритм на каждом шаге содержит две основные процедуры:

а) исследующий покоординатный поиск  в окрестности данной точки x, предназначенный для определения направления убывания функции f(x) – точка ;

б) перемещение в направлении убывания (-x).

Если после шага а) = x, то происходит уменьшение шага исследующего спуска.

Если шаг становится меньше заданной точности, то прекращение поиска.

Алгоритм исследующего покоординатного спуска:

  1. Положить j = 1.
  2. Сделать пробный шаг . - заданный шаг в направлении j. Если f(y) < f(x), перейти к шагу 6, иначе к шагу 3.
  3. Сделать пробный шаг . - заданный шаг в направлении j. Если f(y) < f(x), перейти к шагу 6, иначе к шагу 4.
  4. Если j < n, положить j = j +1 и перейти к шагу 2. Иначе перейти к шагу 5.
  5. Положить = x и завершить поиск.
  6. Положить = y и завершить поиск.

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

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

Метод градиентного спуска с постоянным шагом.

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

Рассмотрим итерационные процедуры минимизации вида

  (1)

где направление убывания pk определяется тем или иным способом с учетом информации о частных производных функции f(x), а величина шага > 0 такова, что

  (2)

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

Алгоритм:

  1. Задать точность вычислений , , выбрать начальное приближение .
  2. Выбрать начальное значение шага .
  3. Положить k = 0 (k – номер итерации).
  4. Вычислить значение .
  5. Вычислить точку .
  6. Проверить выполнение критерия окончания поиска:

, .

Если критерий выполнен переход к шагу 10, иначе к шагу 7.

  1. Положить k = k+1.
  2. Проверка условия (2). Если условие не выполнено, положить =/2.
  3. Переход к новой итерации (шаг 4).
  4. Выбираем приближенно , . Поиск завершен.

Вопросы и задания

  1. Написать в среде MATLAB функции, реализующие следующие три метода: метод правильного симплекса (либо метод Нелдера-Мида), метод покоординатного спуска Хука-Дживса, метод градиентного спуска с постоянным шагом.
  2. Протестировать работу реализованных методов на примере функции:

,

выбрав несколько значений a в диапазоне от 1  до 100 (3-5 значений), при одинаковом начальном приближении (10, 10). Сравнить скорость работы методов при различных значениях параметра a, заполнив таблицу следующего вида:

Таблица 1. Число итераций N для различных значений a.

Метод

a = 1

a = 10

a = 100

a=…

ε = 0.01

ε = 0.001

ε = 0.01

ε = 0.001

ε = 0.01

ε = 0.001

Правильного симплекса

Хука-Дживса

Градиентного спуска

Для точности также выбирается 3-5 значений, соответствующих степеням десяти.

  1. Изучить зависимость работы методов от начального приближения при фиксированном значении a для функции задания 2. Результаты представить в виде таблицы, аналогичной заданию 1. Например, сравнить выбор начального приближения на осях (точки (0, 10) и (10, 0)) и на прямой x=y (точка (10, 10)). 
  2. На примере функции Химмельблау

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

  1. Сравнить поведение предложенных методов на примере функции Розенброка («овражной» функции):

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


 

А также другие работы, которые могут Вас заинтересовать

26268. Контроль сорной растительности в агроценозах 233.5 KB
  Рассматриваются наиболее типичные условия засоренности агроценозов экономические пороги вредоностности сорняков предупредительные и истребительные методы контроля сорняков в том числе агротехнические биологические и химические. Контроль сорной растительности в агроценозах Среди всех агрономических проблем одна из самых сложных контроль сорняков причем при снижении интенсивности обработки почвы она обостряется. Методы контроля сорняков подразделяются на предупредительные и истребительные. Предупредительные методы контроля сорняков Они...
26269. Регулирование минерального питания растений в процессе вегетации 109 KB
  Цель тканевой диагностики выявление необходимости ранней азотной подкормки. Азотные подкормки проводят при показаниях прибора ОАП1 от 1 до 4 баллов или при бледнорозовой окраске индикаторной бумаги. При 41 55 балла применение поздней азотной некорневой подкормки улучшает качество зерна. Необходимость подкормки для улучшения качества зерна определяют по количеству общего азота в листьях пшеницы в фазы колошения цветения.
26270. Особенности почвенно-ландшафтного картографирования и формирования агроГИС для проектирования агротехнологий 72.5 KB
  Сформировать представление о почвенноландшафтном картографировании земель и умение пользоваться агроГИС для проектирования агротехнологий. Ключевые слова: агропроизводственные группировки почв; почвенноландшафтные карты АгроГИС электронные картслои лцифровка GPS Геоморфологическая карта карта СПП карта видов земель базы данных. Разработать карту агроэкологических видов земель в агроГИС на основе материалов почвенноландшафтного картографирования и набора тиматических электронных карт земельного массива фонды кафедры почвоведения...
26271. Абиотические и биотические факторы стресса, влияющие на продуктивность растений 602 KB
  Лекция: Абиотические и биотические факторы стресса влияющие на продуктивность растений Цели и задачи. Технологические повреждения растений. Под стрессом понимают нагрузку на организм которая вызывает сначала дестабилизацию потом нормализацию и повышение устойчивости а при превышении приспособляемости адаптируемости и способности соответствующих механизмов к компенсации отрицательного влияния отмирание целых растений или их частей. С одной стороны стресс мешает максимальной реализации генетического потенциала культурных растений но с...
26272. Применение сенсорной техники при дифференцированном внесении гербицидов (сенсоры сорняков) 120 KB
  Если имеется гетерогенное распределение сорняков при периодической борьбе с сорняками дифференциация расхода гербицида приносит экономические преимущества экономия производственных средств. Внесение гербицидов по потребности требует при дозировке ориентироваться на наличие сорняков. Это предполагает мелкоплощадное установление наличия сорняков.
26273. Точное земледелие 418 KB
  GPSприёмник и бортовой компьютер с программным обеспечением. Например с помощью мобильного радиоуправляемого самолета смонтированных на нем GPSприемника и видеокамеры можно получить информацию о распределении сорняков в пределах заданного поля. Наличие же GPSприемников совершенно необходимо для рассмотренного выше режима offline . Этапы 12 выполняются по стандартным методикам с использованием мобильного GPSнавигатора.
26274. Урожайность яровой пшеницы (т/га) на выщелоченных черноземах в производственных опытах СибНИИЗХим, Новосибирская область 263.5 KB
  Порядок формирования технологий возделывания сельскохозяйственных культур, их региональные и федеральные регистры. Наборы технологий разрабатывают применительно к различным агроэкологическим группам земель, для разных уровней интенсификации производства и категорий товаропроизводителей на основе нормативов.
26275. Архивное законодательство в 2000-е гг 56 KB
  Последнему непосредственно подчинены 15 федеральных государственных архивов Архивы в системе архивной службы РФ Федеральному архивному агентству непосредственно подчиняются 15 федеральных государственных архивов Всероссийский научноисследовательский институт документоведения и архивного дела ВНИИДАД и 1 обслуживающая организация.2004 Положение о ФАА положение регламентирует отношения сроки сферу использования сеть архивов обязанности сторон отраслевые фонды имеющие право постоянного хранения документов. принимает решение о выдаче...
26276. Организация комплектования Архивного Фонда Российской Федерации и других архивных документов 21.85 KB
  Целью комплектования является наиболее полная концентрация в архиве профильных ему документов. Мероприятия входящие в понятие комплектования: Определение состава источников; ЭЦД и НТО; Прием документов в государственные муниципальные архивы. Понятие источник комплектования появилось в 1940ые годы это учреждения или лица непосредственно передающие документы в государственные или ведомственные архивы.