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

Сентябрь 3, 2022

Главная
Алгебра
Методы оптимизации

Содержание

2. Методы оптимизации Говоря о задачах минимизации выделяют несколько общих моментов: Определяют некоторую «скалярную» меру качества –
3. Методы спуска Продолжим рассмотрение итерационных методов, являющиеся более изощренными по сравнению с методами нулевого порядка. Формулируются
4. Методы спуска Методами спуска называются методы рассмотренного выше типа, в которых векторы являются векторами спуска. Поскольку
5. Методы спуска Различные способы выбора направлений спуска приводят к разным методам минимизации: Метод Ньютона, в котором
6. Методы спуска Градиентный метод или метод скорейшего спуска, соответствующий выбору направления спуска по формуле . Таким
7. Выбор направления недостаточен для полного задания метода спуска. Ведь остается еще проблема определения так, чтобы шаг
8. К сожалению, за исключением редких случаев, точное решение задачи одномерной минимизации невозможно, поскольку задача нелинейна. Одна
9. Линейный поиск Методика линейного поиска Рассмотрим итеративные методы, останавливающиеся при выполнении некоторого критерия останова итеративного процесса.
10. Однако простейшая процедура, заключающаяся в выборе достаточно большого начального значения , которое затем уменьшается (делением пополам)
11. Это требование обеспечивает некую усредненную скорость спуска на очередной итерации не меньше определенной доли от величины,
12. Свойство. Предположим, что для всех . Тогда существует интервал такой, что в методе спуска условия (*)
13. Линейный поиск
14. http://www.hbmeyer.de/backtrack/backtren.htm Поиск с возвратом (англ. Backtracking) — общий метод нахождения решений задачи, в которой требуется полный
15. Функция Розенброка
17. Скачать презентацию

Слайд 2

Методы оптимизации
Говоря о задачах минимизации выделяют несколько общих моментов:
Определяют некоторую «скалярную»

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

Слайд 3

Методы спуска
Продолжим рассмотрение итерационных методов, являющиеся более
изощренными по сравнению с

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

Слайд 4

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

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

Слайд 5

Методы спуска
Различные способы выбора направлений спуска приводят к разным методам минимизации:
Метод

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

Слайд 6

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

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

Слайд 7

Выбор направления недостаточен для полного задания метода спуска. Ведь остается еще

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

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

Слайд 8

К сожалению, за исключением редких случаев, точное решение задачи
одномерной минимизации невозможно,

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

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

Слайд 9

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

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

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

Слайд 10

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

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

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

Слайд 11

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

меньше определенной доли от величины, достигнутой на предыдущей итерации.
Чтобы шаг метода не был слишком маленьким, накладывается еще одно условие (но так, чтобы удовлетворялось и предыдущее):
(**)
при . На практике обычно выбирают
Иногда последнее неравенство заменяют более слабым:
(***)
(вспомним, что поскольку - направление спуска).

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

Слайд 12

Свойство. Предположим, что для всех . Тогда существует интервал такой, что

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

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

Слайд 13

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

Слайд 14

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

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

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

Слайд 15

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

Содержание

Методы оптимизацииГоворя о задачах минимизации выделяют несколько общих моментов:Определяют некоторую «скалярную»

Методы спускаПродолжим рассмотрение итерационных методов, являющиеся более изощренными по сравнению с

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

Методы спускаРазличные способы выбора направлений спуска приводят к разным методам минимизации:Метод

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

Выбор направления недостаточен для полного задания метода спуска. Ведь остается еще

К сожалению, за исключением редких случаев, точное решение задачиодномерной минимизации невозможно,

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

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

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

Свойство. Предположим, что для всех . Тогда существует интервал такой, что

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

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

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

Похожие презентации

Методы оптимизации
Говоря о задачах минимизации выделяют несколько общих моментов:
Определяют некоторую «скалярную»

Методы спуска
Продолжим рассмотрение итерационных методов, являющиеся более
изощренными по сравнению с

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

Методы спуска
Различные способы выбора направлений спуска приводят к разным методам минимизации:
Метод

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

К сожалению, за исключением редких случаев, точное решение задачи
одномерной минимизации невозможно,

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

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

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