Green-sell.info

Новые технологии
0 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

Оптимизационный метод одномерной оптимизации нулевого порядка

3 Численные методы поиска безусловного экстремума. Методы нулевого порядка. Методы одномерной минимизации (Лекции по теории оптимизации и численным методам)

Описание файла

Файл «3 Численные методы поиска безусловного экстремума. Методы нулевого порядка. Методы одномерной минимизации» внутри архива находится в папке «Лекции по теории оптимизации и численным методам». PDF-файл из архива «Лекции по теории оптимизации и численным методам», который расположен в категории «лекции и семинары». Всё это находится в предмете «теория оптимизации и численные методы» из четвёртого семестра, которые можно найти в файловом архиве МАИ. Не смотря на прямую связь этого архива с МАИ, его также можно найти и в других разделах. Архив можно найти в разделе «лекции и семинары», в предмете «теория оптимизации и численные методы» в общих файлах.

Просмотр PDF-файла онлайн

Текст из PDF

Лекция 34. ЧИСЛЕННЫЕ МЕТОДЫ ПОИСКА БЕЗУСЛОВНОГО ЭКСТРЕМУМАПринципы построения численных методов. Применение необходимых и достаточных условий безусловного экстремума эффективно для решения ограниченного числапримеров, в которых вытекающие из условий соотношения имеют аналитическое решение.

Для решения большинства практических задач они не могут быть рекомендованы последующим причинам: целевая функция f ( x) может не иметь непрерывных производных до второго порядка включительно; использование необходимого условия первого порядка связано с решением системы n в общем случае нелинейных алгебраических уравнений, что представляет собой самостоятельную задачу, трудоемкость решения которой сравнима с трудоемкостью численного решения поставленной задачи поиска экстремума; возможны случаи, когда о целевой функции известно лишь то, что ее значениеможет быть вычислено с нужной точностью, а сама функция задана неявно.Подавляющее большинство численных методов оптимизации относится к классуитерационных, т.е.

порождающих последовательность точек в соответствии с предписанным набором правил, включающим критерий окончания. При заданной начальной точкеx 0 методы генерируют последовательность x 0 , x 1 , x 2 . Преобразование точки x k вx k 1 представляет собой итерацию.Для определенности рассмотрим задачу поиска безусловного локального минимума:f ( x  )  min f ( x) .xR nЧисленное решение задачи безусловной оптимизации, как правило, связано с построениемпоследовательностиxkточек,обладающихсвойством f ( x k 1 )  f ( x k ) , k  0,1, . Общее правило построения последовательности x k имеет видx k 1  x k  t k d k ,k  0,1,  ,где точка x 0 – начальная точка поиска; d k – приемлемое направление перехода из точки x k в точку x k 1 , обеспечивающее выполнение условия убывания функции и называемое направлением спуска; t k – величина шага.Начальная точка поиска x 0 задается, исходя из физического содержания решаемойзадачи и наличия априорной информации о положении точек экстремума.Классификация численных методов поиска безусловного экстремума.

В зависимости от наивысшего порядка частных производных функции f ( x) , используемых дляформирования d k и t k , численные методы решения задачи безусловной минимизациипринято делить на три группы:27 методы нулевого порядка, использующие только информацию о значениифункции f ( x) ; методы первого порядка, использующие информацию о первых производныхфункции f ( x) ; методы второго порядка, требующие для своей реализации знания вторых производных функции f ( x) .МЕТОДЫ НУЛЕВОГО ПОРЯДКАА.

МЕТОДЫ ОДНОМЕРНОЙ МИНИМИЗАЦИИПостановка задачи. Тpебуется найти безусловный минимум функции f ( x) однойпеpеменной, т.е. такую точку x   R , чтоf ( x*)  min f ( x) .xRПоставленная задача одномерной минимизации может быть решена с помощьюнеобходимых и достаточных условий безусловного экстремума. Однако проблема полуdf ( x ) 0 может оказаться весьма сложной. Более того, вчения решения уравненияdxпрактических задачах функция f (x ) может быть не задана в аналитическом виде иличасто неизвестно, является ли она дифференцируемой. Поэтому получение численногорешения поставленной задачи является важным для приложений.З а м е ч а н и я.1.

Для методов одномеpной минимизации типично задание апpиоpной инфоpмациио положении точки минимума с помощью начального интервала неопpеделенностиL0  a0 , b0  . Пpедполагается, что точка минимума x * пpинадлежит интеpвалу L0 , но ееточное значение неизвестно.2. Большинство известных методов одномеpной минимизации пpименяется длякласса унимодальных функций.Опpеделение. Функция f ( x) называется унимодальной на интеpвале L0  a0 , b0  ,если она достигает глобального минимума на a0 , b0  в единственной точке x  , пpичемслева от x  эта функция строго убывает, а справа от x  – стpого возpастает.3.

Методы одномеpной минимизации шиpоко пpименяются в методах пеpвого ивтоpого поpядков для нахождения оптимальной величины шага. Пpи этом левая гpаницаначального интеpвала неопpеделенности, как правило, совпадает с началом кооpдинат,т.е. a0  0 .Стpатегия поиска включает в себя тpи этапа:1. Выбоp начального интеpвала неопpеделенности.

Гpаницы a0 , b0 интеpваладолжны быть такими, чтобы функция f ( x) была унимодальной.2. Уменьшение интеpвала неопpеделенности.283. Пpовеpку условия окончания. Поиск заканчивается, когда длина текущегоинтеpвала неопpеделенности a k , bk  оказывается меньше установленной величины.Ответом является множество точек, пpинадлежащих последнему интеpвалунеопpеделенности, сpеди котоpых каким-либо обpазом выбиpается pешение задачи x  .В некотоpых методах заранее задается или находится количество N вычисленийфункции. В этом случае пpодолжительность поиска огpаничена.А1. Метод дихотомииСтратегия поискаЗадаются начальный интеpвал неопpеделенности и тpебуемая точность.

Алгоpитмопиpается на анализ значений функции в двух точках (см. pис. 1). Для их нахождения текущий интеpвал неопpеделенности делится пополам и в обе стоpоны от сеpедины откладывается по, где  – малое положительное число. Условия окончания пpоцесса поис2ка стандаpтные: поиск заканчивается, когда длина текущего интеpвала неопpеделенностиоказывается меньше установленной величины.АлгоpитмШаг 1. Задать начальный интеpвал неопpеделенности L0  a0 , b0  ,   0 – малоечисло, l  0 – точность.Шаг 2.

Положить k  0 .a  bk  a  bk  , f yk  , zk  k, f z k  .Шаг 3. Вычислить y k  k22Шаг 4. Сpавнить f  y k  с f z k  :а) если f  y k   f z k  , положить ak 1  ak , bk 1  z k (pис. 1, а) и пеpейти к шагу5;б) если f  y k   f z k  , положить ak 1  y k , bk 1  bk (pис. 1, б).Шаг 5. Вычислить L2k 1  bk 1  ak 1 и проверить условие окончания:а) если L2k 1  l , пpоцесс поиска завеpшить. Точка минимума принадлежит интервалу: x   L2 k 1  ak 1 , bk 1  . В качестве пpиближенного pешения можновзять сеpедину последнего интеpвала: x  ak 1  bk 1;2б) если L2k 1  l , положить k  k  1 и пеpейти к шагу 3.З а м е ч а н и е.

Текущие интеpвалы неопpеделенности L0 , L2 , L4 ,  имеют четные номеpа, указывающие на количество сделанных вычислений функции.29fff z k f y k 2f y k 2zkykakbkxykak2f z k 2zkxbkНовый интервалНовый интервалТекущий интервалТекущий интервалабРис. 1А2. Метод золотого сеченияВ методе золотого сечения в качестве точек вычисления функции выбираютсяточки золотого сечения.Определение.

Читать еще:  Оптимизация проектных решений

Точка пpоизводит золотое сечение отpезка, если отношение длинывсего отpезка к большей части pавно отношению большей части к меньшей.На отpезке a0 , b0  имеются две симметpичные относительно его концов точки y 0и z0 :b0  a0b0  y 0b0  y 0b  a0z  a0 1  5 0 0 1,618 .y 0  a0z 0  a0 b0  z 02При этом точка y 0 пpоизводит золотое сечение отpезка a0 , z 0  , а точка z 0 – отpезка y 0 , b0  (рис. 2).a0y0z0b0xРис. 2Стратегия поискаЗадаются начальный интеpвал неопpеделенности и тpебуемая точность. Алгоpитмуменьшения интеpвала опиpается на анализ значений функции в двух точках (см.

pис. 2).В качестве точек вычисления функции выбиpаются точки золотого сечения. Тогда с учетом свойств золотого сечения на каждой итеpации, кpоме пеpвой, тpебуется произвеститолько одно новое вычисление функции. Условия окончания пpоцесса поискастандаpтные: поиск заканчивается, когда длина текущего интеpвала неопpеделенностиоказывается меньше установленной величины.30АлгоpитмШаг 1.

Задать начальный интеpвал неопpеделенности L0  a0 , b0  , точностьl  0.Шаг 2. Положить k  0 .Шаг 3. Вычислитьy 0  a0 3 5b0  a0  ; z 0  a0  b0  y 0 ,23 5 0,38196 .2Шаг 4. Вычислить f  y k  , f z k  .Шаг 5. Сpавнить f  y k  и f z k  :а) если f  y k   f z k  , то положить ak 1  ak , bk 1  z kи y k 1  a k 1  bk 1  y k , z k 1  y k (рис. 3, а) и пеpейти к шагу 6;б) если f  y k   f z k  , то положить ak 1  y k , bk 1  bkи y k 1  z k , z k 1  ak 1  bk 1  z k (рис.

3, б).Шаг 6. Вычислить   ak 1  bk 1и проверить условие окончания:а) если   l , пpоцесс поиска завеpшить. Точка минимума принадлежит интервалу: x    a k 1, bk 1  . В качестве пpиближенного pешения можно взять сеpединуa bk 1;последнего интеpвала: x   k 12б) если   l , положить k  k  1 и пеpейти к шагу 4.fff y k f z k f y k f z k yakk 1y k  z k 1 z kz k 1xakbkНовый интервалykz k  y k 1Новый интервалТекущий интервалТекущий интервалабРис. 331bkxЗамечания.1. Текущие интеpвалы неопpеделенности имеют следующий вид: L0 , L2 , L3 , L4 , .Они отpажают тот факт, что на пеpвой итеpации пpоизводится два вычисления функции,а на последующих – по одному.2. Сокpащение длины интеpвала неопpеделенности постоянно:L0L2L2L3L3L41 5 1,618 .2А3.

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

Методы одномерной оптимизации

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

f(x) -> min , x принадлежит [a, b].

Самым слабым требованием на функцию f(x), позволяющим использовать эти методы, является ее унимодальность. Поэтому далее будем считать функцию f(x) унимодальной на отрезке [a, b]

т.е. на котором имеется один минимум.

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

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

Разобьем отрезок [a,b] на n равных частей точками деления:

Вычислив значения F(x) в точках xi, путем сравнения найдем точку xm, где m — это число от 0 до n, такую, что

F(xm) = min F(xi) для всех i от 0 до n.

Погрешность определения точки минимума xm функции F(x) методом перебора не превосходит величены Eps=(b-a)/n.

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

Рис. 3. Одномерная минимизация: а — дихотомическое деление; б — золотое сечение

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

Отношение большей части к меньшей в этой пропорции выражается квадратичной иррациональностью

и, наоборот, отношение меньшей части к большей

Геометрическое построение. Золотое сечение отрезка AB можно построить следующим образом: в точке B восстанавливают перпендикуляр к AB, откладывают на нём отрезок BC, равный половине AB, на отрезке AC откладывают отрезок AD, равный ACCB, и наконец, на отрезке AB откладывают отрезок AE, равный AD. Тогда

Рассмотрим для простоты отрезок [0,1] единичной длины.

Ясно, что на отрезке имеется две таких точки и , они симметричны относительно концов. Точка производит золотое сечение отрезка [A,C] , а точка производит золотое сечение отрезка [B,D]. Положим |AB|= x. Тогда |BD|=1-x. В соответствии с определением точки «золотого сечения» имеем: . Решив эту пропорцию, получим .

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

Согласно методу чисел Фибоначчи, используют числа Фибоначчи , последовательность которых образуется по правилу при , т.е. ряд чисел Фибоначчи имеет вид 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, . Метод аналогичен методу золотого сечения с тем отличием, что коэффициент «а» равен отношению , начальное значение определяется из условия, что должно быть наименьшим числом Фибоначчи, превышающим величину , где — заданная допустимая погрешность определения экстремума. Так, если , то начальное значение , поскольку , и , на следующем шаге будет и т.д.

Читать еще:  Что такое оптимизация приложений

Метод полиномиальной аппроксимации: P = a+a1 x +a2 x 2

Выбирают промежуточную точку С на отрезке А,В и записывают значения целевой функции в каждой точке. Далее решают систему из трех АУ, полученных подстановкой P(x) и А, В, С вместо х – получают аi. Исходя из (dP(x)/dx =0) определяют точку экстремума.

Сравнение эффективности алгоритмов одномерной условной оптимизации.

Аналитическое решение возможнотолько при условии одномерной унимодальной функции Ф(х) на интервале . В качестве критерия используют максимальную длину текущего интервала неопределенности (ТИН) после N испытаний.

А) после одной итерации равномерного поиска ТИН уменьшается в N/2 раз

Б) при дихотомическом поиске после одной итерации ТИН уменьшается в 2 раза

B) алгоритм Фибоначчи: i-число Фибоначчи, N-шаг. W= (b-a)/i(N).

-при =14 алгоритм Фибоначчи почти в 3 раз эффективнее алгоритма деления пополам.

-при =14 алгоритм золотого сечения примерно на 40 процентов эффективнее алгоритма Фибоначчи.

МЕТОДЫ ОДНОМЕРНОЙ ОПТИМИЗАЦИИ

О.К. МУРГА

ЧИСЛЕННЫЕ МЕТОДЫ

ОПТИМИЗАЦИИ

Учебное пособие

Казань 2004

Мурга О.К. Численные методы оптимизации: Учебное пособие. Казань: Изд-во Казан. гос. техн. ун-та, 2004, 59 с.

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

Табл. 3 Ил. 4 Библиогр.: 4 назв.

Рецензенты: кафедра математического анализа ( Казанский государствен-

ный педагогический университет);

канд. техн. наук А.Н. Козин (Академия управления

Рекомендовано к изданию Учебно-методическим центром

КГТУ им.А.Н. Туполева

ISBN С Изд-во Казан. гос.техн. ун-та, 2004.

С Мурга О.К., 2004.

ОГЛАВЛЕНИЕ

1. МЕТОДЫ ОДНОМЕРНОЙ ОПТИМИЗАЦИИ.. 6

1.1. МЕТОДЫ ПЕРЕБОРА.. 7

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

1.1.2. Метод поразрядного поиска. 7

1.2. МЕТОДЫ ИСКЛЮЧЕНИЯ ОТРЕЗКОВ.. 8

1.2.1. Метод дихотомии. 8

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

1.3. СРАВНИТЕЛЬНЫЙ АНАЛИЗ МЕТОДОВ ОДНОМЕРНОГО ПОИСКА.. 11

1.4. ПОРЯДОК ВЫПОЛНЕНИЯ ЛАБОРАТОРНОЙ РАБОТЫ. 11

1.5. ЗАДАНИЯ ДЛЯ ЛАБОРАТОРНОЙ РАБОТЫ. 12

2. МЕТОДЫ БЕЗУСЛОВНОЙ ОПТИМИЗАЦИИ.. 13

2.1. ПРЯМЫЕ МЕТОДЫ БЕЗУСЛОВНОЙ ОПТИМИЗАЦИИ.. 13

2.1.1. Поиск по правильному симплексу. 14

2.1.2. Поиск по деформируемому многограннику. 15

2.1.3. Типовой пример. 19

2.1.4. Порядок выполнения лабораторной работы.. 20

2.1.5. Задания для лабораторной работы.. 21

2.2 МЕТОДЫ ПОКООРДИНАТНОГО СПУСКА.. 21

2.2.1 Метод циклического покоординатного спуска. 21

2.2.2. Метод Зейделя. 23

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

2.2.4. Метод Пауэлла. 25

2.2.5. Типовые примеры.. 25

2.2.6. Порядок выполнения лабораторной работы.. 28

2.2.7. Задания для лабораторной работы.. 29

2.3. ГРАДИЕНТНЫЕ МЕТОДЫ. 29

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

2.3.2. Метод наискорейшего спуска. 31

2.3.4. Порядок выполнения лабораторной работы.. 33

2.3.5. Задания для лабораторной работы.. 34

3. МЕТОДЫ ОПТИМИЗАЦИИ ПРИ НАЛИЧИИ ОГРАНИЧЕНИЙ.. 35

3.1. МЕТОДЫ ПОСЛЕДОВАТЕЛЬНОЙ БЕЗУСЛОВНОЙ ОПТИМИЗАЦИИ.. 36

3.1.1. Метод штрафных функций. 36

3.1.2. Метод барьерных функций. 37

3.1.3. Комбинированный метод штрафных функций. 38

3.1.4. Типовой пример. 38

3.1.5. Задание для лабораторной работы.. 39

3.2. МЕТОД ВОЗМОЖНЫХ НАПРАВЛЕНИЙ.. 40

3.2.1. Постановка задачи выпуклого программирования. 40

3.2.2. Описание метода возможных направлений. 40

3.2.3. Построение начального приближения. 41

3.2.4. Выбор наилучшего подходящего направления. 43

3.2.5. Определение длины шага. 46

3.2.6. Типовой пример. 46

3.2.7. Задания для лабораторной работы.. 48

3.3. МЕТОД СЛУЧАЙНОГО ПОИСКА.. 48

3.3.1. Поиск с возвратом при неудачном шаге. 49

3.3.2. Алгоритм наилучшей пробы.. 50

3.3.3. Алгоритм статистичекого градиента. 50

3.3.4. Порядок выполнения работы.. 51

3.3.5. Задания для лабораторной работы.. 51

4. ПРИБЛИЖЁННОЕ РЕШЕНИЕ ЗАДАЧИ ОПТИМАЛЬНОГО УПРАВЛЕНИЯ.. 53

4.1. ПОСТАНОВКА ЗАДАЧИ ОПТИМАЛЬНОГО УПРАВЛЕНИЯ.. 53

4.2. ГРАДИЕНТНЫЙ МЕТОД РЕШЕНИЯ ЗАДАЧИ ОПТИМАЛЬНОГО УПРАВЛЕНИЯ.. 53

4.2.1. Описание градиентного метода в функциональном пространстве. 53

4.2.2. Алгоритм метода. 55

4.2.3. Порядок выполнения лабораторной работы. 57

4.2.4. Задания для лабораторной работы. 58

СПИСОК ЛИТЕРАТУРЫ. 59

ВВЕДЕНИЕ

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

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

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

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

МЕТОДЫ ОДНОМЕРНОЙ ОПТИМИЗАЦИИ

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

Решить задачу одномерной оптимизации

т.е. найти число x*[a ;b], такое что f(x*)  f(x), x[a;b].

Здесь a, b – заданные числа, причем a  b; функция одной переменной f(x) унимодальна на отрезке [a;b].

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

(x) = 0, (1.2)

находятся все стационарные точки на интервале (a;b). В найденных стационарных точках проверяется достаточное условие и выделяются из них точки локального минимума, в которых выполнилось условие

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

Однако, даже если функция f(x) задана аналитически и производная (x) найдена, то решение уравнения (1.2) зачастую вызывает затруднения. Кроме того, вычисление производных может быть весьма трудоемко или же функция f(x) может быть задана не аналитически. Поэтому классический метод имеет ограниченное применение и для решения задачи (1.1) на практике, как правило, применяют приближенные методы.

Читать еще:  Для оптимизации работы

Начнём изучение с простейших приближённых методов, позволяющих найти решение задачи (1.1) с необходимой точностью в результате определения конечного числа значений функции f(х) в некоторых точках отрезка [a ;b]. Такие методы называют прямыми методами одномерного поиска.

МЕТОДЫ ПЕРЕБОРА

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

Метод равномерного поиска является простейшим из прямых методов одномерной оптимизации и состоит в следующем.

Отрезок [a ;b] разбивается на n равных частей точками деления

Сравнением значений функции f(x) во всех точках xi, , находится точка хk: 0  k  n, для которой

Полагая х * xk , ff(xk), получается решение задачи (1.1) с погрешностью, не превосходящей величины

en= . (1.6)

Для того, чтобы обеспечить требуемую точность  определения точки x*, число n отрезков разбиения необходимо выбирать из условия n  , т.е. назначить

n ³ . (1.7)

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

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

Очевидно, если окажется, что f(xi+1)  f(xi), то отпадает необходимость вычислять f(x) в точках xi+2, xi+3,…, xn, т.к. в силу унимодальности функции f(x) x*xi+1. Кроме того, целесообразно сначала грубо определить отрезок, содержащий x * , т.е. найти точку x * с небольшой точностью, а затем искать её на этом отрезке с меньшим шагом, повышая точность. Реализация этих возможностей улучшения метода перебора и приводит к методу поразрядного поиска.

В методе поразрядного поиска перебор точек отрезка предлагается выполнять сначала с достаточно большим шагом h=xi+1 — xi ( например, h=(b — a)/4 ) до тех пор, пока не выполнится условие f(xi+1)  f(xi) или пока очередная точка не совпадет с концом отрезка. После этого шаг уменьшается и перебор точек с новым шагом производится в противоположном направлении до тех пор, пока значения функции снова не перестанут уменьшаться или пока очередная точка не совпадет с другим концом отрезка. Описанный процесс завершается, когда перебор в данном направлении закончен, а использованный при этом шаг h не превосходит .

Таким образом получается следующий алгоритм метода поразрядного поиска.

Шаг 0. Задать параметр точности   0, выбрать начальный шаг h=(b — a)/4, положить x=a, вычислить f(x).

Шаг 1. Найти очередную точку x1= x+h, вычислить f(x1).

Шаг 2. Сравнить значения функции f(x) и f(x1). Если f(x)f(x1), то перейти к шагу 3, иначе – к шагу 4.

a * »x , f * »f(x), иначе–перейти к шагу 5.

Шаг 5. Изменить направление и шаг поиска, положив h=-h /4, x=x1, f(x)=f(x1). Перейти к шагу 1.

Сравнение методов одномерной оптимизации

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

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

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

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

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

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

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

Классификация методов многомерной оптимизации

• МЕТОДЫ НУЛЕВОГО ПОРЯДКА — при выборе направления спуска требуют вычисления только значений функции (методы: Гаусса-Зейделя, Пауэлла, ДСК, Розенброка, Хука-Дживса, Нелдера-Мида).

• МЕТОДЫ ПЕРВОГО ПОРЯДКА — требуют вычисления (точного или приближенного) градиента функции (методы: градиентный, сопряженных градиентов, Давидона-Флетчера-Пауэлла (ДФП), Флетчера-Ривса идр.).

• МЕТОДЫ ВТОРОГО ПОРЯДКА — требуют вычисления как градиента, так и матрицы вторых производных (методы: Ньютона, Ньютона-Рафсона).

• МЕТОДЫ С ПЕРЕМЕННОЙ МЕТРИКОЙ – занимают промежуточное место между методами 1-го и 2-го порядка.

Метод последовательного перебора

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

Алгоритм последнего варианта приведен ниже.

Задаются x0, некоторый шаг h и погрешность ε .

1. Из точки x0 делается шаг x1=x0+h и вычисляются y1 = f (x1) .

2. x0=x1, y0=y1 — запоминается удачная точка.

3. x1=x0+h, y1=f(x1) — делаем следующий шаг в удачном направлении.

4. Если функция убывает, y1 ε / 4 , тогда повторить с п.2, иначе перейти к п.7.

Скорость сходимости данного метода существенно зависит от удачного выбора начального приближения x0 и шага h. Шаг h следует выбирать как половину оценки расстояния от x0 до предполагаемого минимума xm.

МЕТОД МОНТЕ-КАРЛО

Метод Монте-Карло является одним из методов случайного поиска.

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

где i=1,2. n (n – число параметров)

j=1,2. m (m – число испытаний)

ksi – случайное число в диапазоне [0,1].

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

2. Выбрать вариант с минимальным значением функции.

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

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

Ссылка на основную публикацию
Adblock
detector