Разделы презентаций


Линейный поиск презентация, доклад

Содержание

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

Слайды и текст этой презентации

Слайд 1ЧИСЛЕННЫЕ МЕТОДЫ ОПТИМИЗАЦИИ
Константин Ловецкий

Октябрь 2012
Кафедра систем телекоммуникаций

ЧИСЛЕННЫЕ МЕТОДЫ ОПТИМИЗАЦИИКонстантин ЛовецкийОктябрь 2012Кафедра систем телекоммуникаций

Слайд 2Линейный поиск
Методика линейного поиска
Рассмотрим итеративные методы, останавливающиеся при выполнении некоторого

критерия останова итеративного процесса. При этом предполагается, что условия, определяющие

направление спуска,



выполнены.

Практика показывает, что искать точное решение задачи о минимуме функции


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

при фиксированных и .

Линейный поискМетодика линейного поискаРассмотрим итеративные методы, останавливающиеся при выполнении некоторого критерия останова итеративного процесса. При этом предполагается,

Слайд 3Однако простейшая процедура, заключающаяся в выборе достаточно
большого начального значения

, которое затем уменьшается (делением
пополам)

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

(*)

при .

Линейный поиск

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

Слайд 4Это требование обеспечивает некую усредненную скорость спуска на очередной итерации

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


Чтобы шаг метода не был слишком маленьким, накладывается еще одно условие (но так, чтобы удовлетворялось и предыдущее):

(**)
при . На практике обычно выбирают
Иногда последнее неравенство заменяют более слабым:

(***)
(вспомним, что поскольку - направление спуска).

Линейный поиск

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

Слайд 5Свойство. Предположим, что

для всех

. Тогда существует интервал такой, что в методе спуска условия (*) и (**) или (*) и (***) удовлетворяются для любых при
и .
Выбор параметров можно обеспечить многими способами, наиболее современной стратегией является перебор с возвратом
(backtracking technique): при фиксированном значении
начиная со значения уменьшаем его умножением на
до тех пор, пока не выполнится условие (*).
Эта процедура приводится ниже. В качестве входных параметров используются текущее значение вектора , содержащее , имена подпрограмм, вычисляющих значение функции и ее якобиана ,
вектор , содержащий текущее направление поиска, а также значения
, обычно порядка 1.0e-4, и масштабного множителя .
На выходе подпрограмма возвращает , вычисленное при подходящем значении .

Линейный поиск

Свойство. Предположим, что           для всех

Слайд 6
Линейный поиск

Линейный поиск

Слайд 7http://www.hbmeyer.de/backtrack/backtren.htm

Поиск с возвратом (англ. Backtracking) — общий метод нахождения решений задачи, в

которой требуется полный перебор всех возможных вариантов в некотором множестве

М. Как правило позволяет решать задачи, в которых ставятся вопросы типа: «Перечислите все возможные варианты …», «Сколько существует способов …», «Есть ли способ …», «Существует ли объект…» и т. п.
Термин backtrack был введен в 1950 году американским математиком Дерриком Генри Лемером.
Незначительные модификации метода поиска с возвратом, связанные с представлением данных или особенностями реализации, имеют и иные названия: метод ветвей и границ, поиск в глубину, метод проб и ошибок и т. д. Поиск с возвратом практически одновременно и независимо был изобретен многими исследователями еще до его формального описания.

Линейный поиск с возвратом

http://www.hbmeyer.de/backtrack/backtren.htmПоиск с возвратом (англ. Backtracking) — общий метод нахождения решений задачи, в которой требуется полный перебор всех возможных вариантов

Слайд 8Методы оптимизации
Методы спуска минимизации квадратичных функций
Для методов спуска особый интерес

представляют такие функции, для
которых параметр шага

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

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

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



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

Слайд 9Методы спуска для квадратичных функций
В частности, при заданном направлении спуска

можно определить
оптимальную величину шага

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


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

Слайд 10Методы спуска для квадратичных функций
Отклонение от точного решения на

-м шаге процесса минимизации

можно вычислить по формуле:

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

Слайд 11Методы спуска для квадратичных функций
С другой стороны,


поэтому из предыдущей формулы

следует, что



Обозначим

, где



Методы спуска для квадратичных функцийС другой стороны,поэтому из предыдущей формулы следует, чтоОбозначим

Слайд 12Метод наискорейшего спуска
Поскольку матрица A симметрична и положительно определена, то
всегда

положительна. Более того, можно проверить непосредственно, что

; и лишь когда вектор ортогонален , тогда .
Выбор направления спуска в виде приводит к методу
наискорейшего спуска. В этом случае справедливо неравенство


Отсюда следует
Неравенство Канторовича


Метод наискорейшего спускаПоскольку матрица A симметрична и положительно определена, товсегда положительна. Более того, можно проверить непосредственно, что

Слайд 13Лемма. (Неравенство Канторовича) Пусть

- симметричная положительно определенная матрица с

наибольшим и наименьшим по модулю значениями соответственно. Тогда для любого ненулевого вектора :

Методы спуска

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

Лемма. (Неравенство Канторовича) Пусть           - симметричная положительно

Слайд 14Соответствующие методы обладают следующим хорошим свойством:
Свойство. Метод вычисления точки минимума

квадратичной функции,
основанный на вычислении A-сопряженных направлений спуска, достигает
результата

после самое большое n итераций, если параметр
вычисляется по формуле


Более того, для любого k, x (k+1) является точкой минимума на
подпространстве, натянутом на векторы и

Метод сопряженных направлений

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

Слайд 15Метод сопряженных направлений
A-сопряженные направления можно вычислять в соответствии со следующей

процедурой. Для начального приближения

положим и формулы метода сопряженных градиентов записываются в виде:

Зная число обусловленности матрицы можно оценить скорость сходимости метода:

Метод сопряженных направленийA-сопряженные направления можно вычислять в соответствии со следующей процедурой. Для начального приближения

Слайд 16Скорость сходимости метода может быть повышена лишь за счет проведения


предобуславливания матрицы с целью уменьшения числа обусловленности.
Замечание. Случай не

квадратичных функций. Метод сопряженных
направлений может быть распространен и на случай не квадратичных
функций. Однако в этом случае оптимальное значение параметра
не может быть определено аналитически и для его отыскания придется
решать одномерную оптимизационную задачу. Мало того, параметры
могут определяться не единственным образом. Наиболее надежны два
варианта выбора :
Флетчера-Ривса (Fletcher-Reeves):

Полака-Рибиера (Polak-Ribiere):

Метод сопряженных направлений

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

Слайд 17Метод сопряженных направлений
Иллюстрация последовательных приближений метода наискорейшего спуска (зелёная ломаная)

и метода сопряжённых градиентов (красная ломаная) к точке экстремума.

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

Слайд 18Метод сопряженных градиентов
The algorithm is detailed for solving Ax =

b where A is a real, symmetric, positive-definite matrix. The

input vector x0 can be an approximate initial solution or 0.

Example code in GNU Octave

function [x] = conjgrad(A,b,x)
r=b-A*x;
p=r;
rsold=r'*r;
for i=1:size(A)(1)
Ap=A*p;
alpha=rsold/(p'*Ap);
x=x+alpha*p;
r=r-alpha*Ap;
rsnew=r'*r;
if sqrt(rsnew)<1e-10 break;
end
p=r+rsnew/rsold*p;
rsold=rsnew;
end
end

Метод сопряженных градиентовThe algorithm is detailed for solving Ax = b where A is a real, symmetric,

Слайд 19The gradient method

The gradient method

Слайд 20The gradient method

The gradient method

Слайд 21The gradient method
Alfio Quarteroni, Riccardo Sacco, Fausto Saleri
Numerical Mathematics

The gradient methodAlfio Quarteroni, Riccardo Sacco, Fausto SaleriNumerical Mathematics

Слайд 22Функция Розенброка

Функция Розенброка

Слайд 23Функция Химмельблау

Функция Химмельблау

Обратная связь

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

Email: Нажмите что бы посмотреть 

Что такое TheSlide.ru?

Это сайт презентации, докладов, проектов в PowerPoint. Здесь удобно  хранить и делиться своими презентациями с другими пользователями.


Для правообладателей

Яндекс.Метрика