Методы оптимизации в машинном обучении (курс лекций)/2012/Задание 1
Материал из MachineLearning.
м |
|||
(13 промежуточных версий не показаны.) | |||
Строка 1: | Строка 1: | ||
__NOTOC__ | __NOTOC__ | ||
- | |||
- | |||
{{Main|Методы оптимизации в машинном обучении (курс лекций)}} | {{Main|Методы оптимизации в машинном обучении (курс лекций)}} | ||
Строка 7: | Строка 5: | ||
[[Image:MOMO12_Task1_intro.jpg|300px]] | [[Image:MOMO12_Task1_intro.jpg|300px]] | ||
- | '''Начало выполнения задания''': | + | '''Начало выполнения задания''': 28 сентября 2012 |
- | '''Срок сдачи''': {{ins| | + | '''Срок сдачи''': {{ins|11 октября 2012 (четверг), 23:59}} |
- | Среда реализации задания – MATLAB | + | Среда реализации задания – MATLAB. |
=== Формулировка задания === | === Формулировка задания === | ||
Для выполнения задания необходимо: | Для выполнения задания необходимо: | ||
* Реализовать алгоритмы одномерной минимизации функции без производной: метод золотого сечения, метод парабол и комбинированный метод Брента; | * Реализовать алгоритмы одномерной минимизации функции без производной: метод золотого сечения, метод парабол и комбинированный метод Брента; | ||
- | * Протестировать реализованные алгоритмы на наборе задач оптимизации; | + | * Протестировать реализованные алгоритмы на следующем наборе задач оптимизации: |
- | * Написать отчет в формате PDF с описанием всех проведенных исследований. | + | ** <tex>f(x) = -5x^5+4x^4-12x^3+11x^2-2x+1</tex> на интервале [-0.5, 0.5]; |
+ | ** <tex>f(x) = \ln^2(x-2) + \ln^2(10-x) - x^{0.2}</tex> на интервале [6, 9.9]; | ||
+ | ** <tex>f(x) = -3x\sin 0.75x + \exp(-2x)</tex> на интервале <tex>[0, 2\pi]</tex>; | ||
+ | ** <tex>f(x) = \exp(3x) + 5\exp(-2x)</tex> на интервале [0, 1]; | ||
+ | ** <tex>f(x) = 0.2x\ln x + (x-2.3)^2</tex> на интервале [0.5, 2.5]; | ||
+ | * Протестировать реализованные алгоритмы для задач минимизации многомодальных функций, например, на различных полиномах; | ||
+ | * Реализовать метод кубических аппроксимаций (по значениям функции и производной в двух точках) и комбинированный метод Брента c производной, сравнить их работу с методами оптимизации без производной; | ||
+ | * Реализовать метод Флетчера для неточной одномерной оптимизации, протестировать метод для минимизации двухмерной функции <tex>f(x) = 0.7x_1^4-8x_1^2+6x_2^2+\cos(x_1x_2)-8x_1</tex> из точки <tex>x_0 = [-\pi, \pi]^T</tex> вдоль направлений <tex>d = [1, -1.3]^T</tex> и <tex>d = [1, -1.1]^T</tex>, сравнить работу метода Флетчера с точными методами одномерной минимизации; | ||
+ | * Написать отчет в формате PDF с описанием всех проведенных исследований. Данный отчет должен содержать, в частности, количество обращений к оракулу при всех запусках итерационных процессов оптимизации. | ||
=== Спецификация реализуемых функций === | === Спецификация реализуемых функций === | ||
Строка 34: | Строка 40: | ||
|interval — границы интервала оптимизации, вектор типа double длины 2; | |interval — границы интервала оптимизации, вектор типа double длины 2; | ||
|- | |- | ||
- | |(param_name, param_value) — необязательные | + | |(param_name, param_value) — необязательные параметры, следующие названия и значения возможны: |
|- | |- | ||
- | | | + | | |
+ | {|border="0" | ||
+ | |'eps' — точность оптимизации по аргументу, число, по умолчанию = 1e-5; | ||
+ | |- | ||
+ | |'max_iter' — максимальное число итераций, число, по умолчанию = 500; | ||
+ | |- | ||
+ | |'display' — режим отображения, true или false, если true, то отображаются номер итерации, текущее значение функции, аргумента, текущая точность и др. показатели, по умолчанию = false; | ||
+ | |- | ||
+ | |} | ||
|- | |- | ||
- | |||
- | |||
- | |||
- | |||
- | |||
|} | |} | ||
|- | |- | ||
Строка 49: | Строка 58: | ||
| | | | ||
{| | {| | ||
- | | | + | |x_min — найденное значение минимума, число; |
|- | |- | ||
- | | | + | |f_min — значение функции в точке минимума, число; |
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
|- | |- | ||
- | | | + | |status — результаты оптимизации, структура со следующими полями: |
|- | |- | ||
- | | | + | | |
+ | {|border="0" | ||
+ | |'flag' — общий результат, число, равно 1, если достигнут оптимум с точностью eps, равно -1, если произошел выход по максимальному числу итераций; | ||
+ | |- | ||
+ | |'num_oracle' — количество обращений к оракулу; | ||
+ | |- | ||
+ | |} | ||
|- | |- | ||
- | + | |} | |
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | |} | + | |
|} | |} | ||
- | + | Прототипы функций min_parabolic для метода парабол, min_qubic для кубических аппроксимаций и min_brent для метода Брента выглядят аналогично. В методе Брента добавляется параметр 'use_gradient' с возможными значениями true и false для учета случая оптимизации с производной и без. При отображении в методе Брента необходимо указывать способ выбора очередной точки на каждой итерации (golden/parabolic или bisection/parabolic). | |
{|class="standard" | {|class="standard" | ||
- | !'' | + | !''Метод Флетчера'' |
|- | |- | ||
- | |[ | + | |[alpha_min, f_min, status] = min_fletcher(func, x, d, param_name1, param_value1, ...) |
|- | |- | ||
|ВХОД | |ВХОД | ||
|- | |- | ||
| | | | ||
- | {| | + | {|border="0" |
- | | | + | |func — указатель на оптимизируемую функцию; |
|- | |- | ||
- | | | + | |x — текущая точка, вектор типа double; |
|- | |- | ||
- | | | + | |d — направление минимизации, вектор типа double; |
|- | |- | ||
- | | | + | |(param_name, param_value) — необязательные параметры, следующие названия и значения возможны: |
|- | |- | ||
- | | | + | | |
- | + | {|border="0" | |
- | + | |'params' — параметры метода [rho sigma tau xi], по умолчанию = [0.1 0.7 0.1 9]; | |
- | + | |- | |
- | + | |'max_iter' — максимальное число итераций, число, по умолчанию = 100; | |
+ | |- | ||
+ | |'display' — режим отображения, true или false, по умолчанию = false; | ||
+ | |- | ||
+ | |} | ||
|- | |- | ||
|} | |} | ||
Строка 124: | Строка 110: | ||
| | | | ||
{| | {| | ||
+ | |alpha_min — найденное значение минимума для alpha, число; | ||
|- | |- | ||
- | | | + | |f_min — значение функции в точке минимума, число; |
|- | |- | ||
- | | | + | |status — результаты оптимизации, структура со следующими полями: |
|- | |- | ||
- | | | + | | |
+ | {|border="0" | ||
+ | |'flag' — общий результат, число, равно 1, если достигнут неточный оптимум, равно -1, если произошел выход по максимальному числу итераций; | ||
+ | |- | ||
+ | |'num_oracle' — количество обращений к оракулу; | ||
+ | |- | ||
+ | |} | ||
|- | |- | ||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
|} | |} | ||
|} | |} | ||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
=== Оформление задания === | === Оформление задания === | ||
Строка 220: | Строка 132: | ||
Письмо должно содержать: | Письмо должно содержать: | ||
- | *PDF-файл с описанием проведенных исследований | + | *PDF-файл с описанием проведенных исследований; |
- | *Набор вспомогательных файлов при необходимости | + | *Файлы min_golden.m, min_quadratic.m, min_cubic.m, min_brent.m, min_fletcher.m; |
+ | *Набор вспомогательных файлов при необходимости. | ||
[[Категория:Учебные курсы]] | [[Категория:Учебные курсы]] |
Текущая версия
Начало выполнения задания: 28 сентября 2012
Срок сдачи: 11 октября 2012 (четверг), 23:59
Среда реализации задания – MATLAB.
Формулировка задания
Для выполнения задания необходимо:
- Реализовать алгоритмы одномерной минимизации функции без производной: метод золотого сечения, метод парабол и комбинированный метод Брента;
- Протестировать реализованные алгоритмы на следующем наборе задач оптимизации:
- на интервале [-0.5, 0.5];
- на интервале [6, 9.9];
- на интервале ;
- на интервале [0, 1];
- на интервале [0.5, 2.5];
- Протестировать реализованные алгоритмы для задач минимизации многомодальных функций, например, на различных полиномах;
- Реализовать метод кубических аппроксимаций (по значениям функции и производной в двух точках) и комбинированный метод Брента c производной, сравнить их работу с методами оптимизации без производной;
- Реализовать метод Флетчера для неточной одномерной оптимизации, протестировать метод для минимизации двухмерной функции из точки вдоль направлений и , сравнить работу метода Флетчера с точными методами одномерной минимизации;
- Написать отчет в формате PDF с описанием всех проведенных исследований. Данный отчет должен содержать, в частности, количество обращений к оракулу при всех запусках итерационных процессов оптимизации.
Спецификация реализуемых функций
Метод золотого сечения | |||||||
---|---|---|---|---|---|---|---|
[x_min, f_min, status] = min_golden(func, interval, param_name1, param_value1, ...) | |||||||
ВХОД | |||||||
| |||||||
ВЫХОД | |||||||
|
Прототипы функций min_parabolic для метода парабол, min_qubic для кубических аппроксимаций и min_brent для метода Брента выглядят аналогично. В методе Брента добавляется параметр 'use_gradient' с возможными значениями true и false для учета случая оптимизации с производной и без. При отображении в методе Брента необходимо указывать способ выбора очередной точки на каждой итерации (golden/parabolic или bisection/parabolic).
Метод Флетчера | ||||||||
---|---|---|---|---|---|---|---|---|
[alpha_min, f_min, status] = min_fletcher(func, x, d, param_name1, param_value1, ...) | ||||||||
ВХОД | ||||||||
| ||||||||
ВЫХОД | ||||||||
|
Оформление задания
Выполненный вариант задания необходимо прислать письмом по адресу bayesml@gmail.com с темой «[МОМО12] Задание 1. ФИО». Убедительная просьба присылать выполненное задание только один раз с окончательным вариантом. Новые версии будут рассматриваться только в самом крайнем случае. Также убедительная просьба строго придерживаться заданной выше спецификации реализуемых функций. Очень трудно проверять большое количество заданий, если у каждого будет свой формат реализации.
Письмо должно содержать:
- PDF-файл с описанием проведенных исследований;
- Файлы min_golden.m, min_quadratic.m, min_cubic.m, min_brent.m, min_fletcher.m;
- Набор вспомогательных файлов при необходимости.