Наискорейший градиентный спуск с вычислением величины шага методом Дихотомии

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

При решении примера в учебнике не используется какой-либо численный метод.
Помогите пожалуйста!
Книга Пантелеев 2005г. "Методы оптимизации в примерах". На 187 странице начинается пример.

0

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

Вот и ищете. Сначала крупными шажками, потом шажки уменьшаете. В чём вопрос-то?

1

Сообщение от AdmiralHood найти экстремум функции вдоль прямой в направлении градиента

Предположим что я немного чайник. Если Вас не затруднит, поделитесь ссылкой где это разжевано...
Или может быть покажите на примере... Спасибо!

Окей. Какой мать её функции????

Сообщение от AdmiralHood экстремум функции

Вот этой??

Мне брать х1 и х2? Так получается что я работаю и с x1 и с x2... Я тупо запнулся об этот камень, и не могу обойти его. -_-

0

Сообщение от _include Вот этой??

6 пункт в книге смотрите.Только в отличии от книги,у себя вы будете искать минимум \varphi({t}_{k} ) численно.Т.е. ваша исходная функция будет вычисляться с известными зависящими от неизвестной .
В своей программе зададите диапазон поиска оптимального шага в котором ищете минимум своей функции методом дихотомии.

1

Сообщение от S_el Т.е. ваша исходная функция будет вычисляться с известными зависящими от неизвестной .

Перечитываю этот пункт 10й раз. Не совсем понимаю откуда я буду знать x1,x2..

Если я правильно понял, формула по которой я буду считать находится на 188 странице, где х1 и х2 предыдущая и последующая точка?

0

Находите производные dy/dx1 и dy/dx2 в этой точке.
dy/dx1=4x1+x2
dy/dx2=x1+4x2
Берёте какую-нибудь начальную точку, например, x1=1, x2=2. Т.е. А0=(1,2).
Значение функции в этой точке 12, градиент в этой точке (6,9).
Делаете шажок из начальной точки в направлении градиента: A1= (1,2)+k*(6,9).
Берём, например, для начала k=-0.1.
A1= (1,2)-0.1*(6,9)=(0.4;1.1). Вычисляете функцию в новой точке, смотрите, уменьшилась она или увеличилась...

1

Сообщение от AdmiralHood Делаете шажок из начальной точки в направлении градиента: A1= (1,2)+k*(6,9). Берём, например, для начала k=-0.1. A1= (1,2)-0.1*(6,9)=(0.4;1.1). Вычисляете функцию в новой точке, смотрите, уменьшилась она или увеличилась...

Спасибо!) Собственно, до этого момента мне все понятно.
А вот что делать после этого...

0

Сообщение от _include А вот что делать после этого...

После этого делаете следующую итерацию и так до тех пор,пока выбранный метод не найдет оптимальный шаг t

1

S_el, AdmiralHood, Меня посетило сомнение - я реализовал метод дихотомии для простого уравнения типа x^3-6x^2+9x = 0.
Из написанного выше, я понял что такое х1 и х2. Как мне выбрать интервал [a;b]? В него должна входить точка x1 и точка х2? Или я отдельно считаю минимум для x1 и отдельно для х2? И мне все равно не понятно какую функцию использовать для счета =_=

0

Сообщение от _include Как мне выбрать интервал [a;b]?

Например методом Свенна или оценить по графику(если он есть)

1

Сообщение от S_el методом Свенна

Ну, будем знакомиться
Какую функцию я использую в нем?
Эту ? -

0

Сообщение от _include Какую функцию я использую в нем?

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

1

Что-то я совсем запутался. Спрашивал у преподавателя - говорит не знает как сделать с дихотомией, мол у него нет времени даже на консультациях... - Думай сам.

0

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

Мдаа.Значит не заморачивайтесь с диапазоном подбора шага,а возьмите какой нравится.Я пока не смог найти советов по его подбору.

1

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

Вот эта аллегория — один к одному то, что вам нужно сделать. Потому что функция двух переменных - это некий трёхмерный рельеф, топографическая карта. X1 и X2 - это широта и долгота, а значение функции — высота над уровнем моря.

И вот ваш робот стоит в некой точке (X1;X2) и вычисляет градиент. Не важно, каким образом, важно, что градиент — это направление, вдоль которого функция возрстает быстрее всего. То есть можно надеяться, что это ближайший путь к вершине.

Проблема в том, что градиент всегда указывает точно на вершину только для осесимметричных рельефов. На реальной горке вы по градиенту пройдёте мимо вершины. Градиент - штука локальная. В других точках на склоне его направление может быть другим.

Беллетристику на эту тему можно почитать здесь: http://vladfotki.narod.ru/__hb... irabok.djv. Начиная со стр. 17. В принципе можно просто прочитать подписи под картинками и всё будет ясно.

Так вот, вы задаёте роботу направление и он идёт по нему, через каждые 100 метров измеряя высоту рельефа: 140, 160, 175, 180, 174... Очевидно, что между двумя последними замерами вы проскочили точку максимума. Конечно, это не глобальный максимум, это всего лишь максимум вдоль выбранного направления, но вам нужно его найти, чтобы сделать его отправной точкой для дальнейшего поиска.

Поэтому вы уменьшаете шаг двое (лично я бы уменьшил в 4 раза, но раз такое задание, пусть будет в 2 раза), до 50 метров, и возвращаетесь на 50 метров назад. В этой точке высота 182.

Тут возникает некий дуализм (именно поэтому я не рекомендую уменьшать шаг вдвое). Непонятно, где теперь находится максимум — между точками 180 и 182 или между 182 и 174. В наихудшем случае придётся проверить обе. Уменшаем шаг до 25 метров и идём в точку посередине между 182 и 174. Там высота 186. Угадали. Снова оказываемся в ситуации дуализма. Уменьшаем шаг до 12,5 м и делаем то же самое, что на предыдущем шаге.

В конце концов находим максимум вдоль выбранного направления. Эту точку берём в качестве новой отправной точки и далее см. самое начало текста.

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

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

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

Тут возникает вторая проблема — как долго идти? Скажем, максимум находится на расстоянии 1000 км (априориы это неизвестно, конечно), а вы идёте к нему 10-метровыми шажками. До-олго будете идти.

Тут поможет только адаптивный шаг. Если за некоторое количество шагов (скажем, за 4 шага) признаков экстемума не обнаружено, увеличиваете шаг вдвое и снова делаете определённое количество шагов. Если же область экстремума нашлась, начинаете уменьшать шаг, локализуете экстремум.

1

AdmiralHood, S_el, я понял!!! Спасибо огромное!!! Благодарю вас за помощь, господа!

0

Сообщение от AdmiralHood Находите производные dy/dx1 и dy/dx2 в этой точке. dy/dx1=4x1+x2 dy/dx2=x1+4x2 Берёте какую-нибудь начальную точку, например, x1=1, x2=2. Т.е. А0=(1,2). Значение функции в этой точке 12, градиент в этой точке (6,9). Делаете шажок из начальной точки в направлении градиента: A1= (1,2)+k*(6,9). Берём, например, для начала k=-0.1. A1= (1,2)-0.1*(6,9)=(0.4;1.1). Вычисляете функцию в новой точке, смотрите, уменьшилась она или увеличилась...

Добавлено через 1 минуту
Извиняюсь (всем привет), может кто-нибудь объяснить, у меня просто такое же задание - реально я что-то не понимаю,
градиент же по-другому находится grad = частная производная(x1)^2 + частная производная (x2)^2 и всё это под корнем ?

0