Алгоритм наискорейшего спуска

@q74 · Регистрация: 14.11.2016

Студворк — интернет-сервис помощи студентам

Мне нужно найти локальные минимумы в массиве в пределах окрестности.
Прочитала про метод наискорейшего спуска, но везде в алгоритмах используется значение функции и вычисленная ее производная. Я не совсем понимаю, если у меня массив состоит из чисел:
x y f(x), где f(x) - значение функции, то о какой производной идет речь?

Можете дать какие-то наводки по решению данной задачи?

@cybeuser · 21.11.2016, 10:15

Сообщение от q74

x y f(x), где f(x)

Может f(x,y) ?

Добавлено через 10 минут
А вообще локальный минимум в массиве - это элемент, который меньше своих соседей

@q74 · 22.11.2016, 20:56 **[ТС]**

Да, опечатка, f(x, y). Метод общего перебора мне известен. Просто хотелось разузнать именно про метод наискорейшего спуска.

@cybeuser · 22.11.2016, 22:17

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

@q74 · 24.11.2016, 21:52 **[ТС]**

Спасибо за совет. Подумав, у меня возник вопрос: у меня массив состоит из более 100000 точек, допустим я запрограммирую написание интерполяционного многочлена Лагранжа, ну а как тогда от него программно находить производную?

@q74 · 25.11.2016, 08:12 **[ТС]**

Думаю, мне нужно более подробно обозначить проблему. Я построила в матлабе график по входному массиву, который представлен тремя переменными:
var[0] = x
var[1] = y
var[2] = z (само значение функции)

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

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

@q74 · 25.11.2016, 08:17 **[ТС]**

P. S. И Еще: в интернете я нашла только как строить многочлен Лагранжа для функции заданной в виде xi и yi, а у меня случай zi = f(xi, yi)...

@cybeuser · 25.11.2016, 08:48

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

@q74 · 25.11.2016, 08:56 **[ТС]**

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

@cybeuser · 25.11.2016, 09:00

q74, посмотрите на функцию, на какую она похожа?

Добавлено через 2 минуты
в общем, пробуйте всё, будет очень полезно

@q74 · 25.11.2016, 09:01 **[ТС]**

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

Добавлено через 19 секунд
Хорошо, попробую, спасибо

@cybeuser · 25.11.2016, 09:37

q74, и не забудьте что исследование функции вне заданных значений нужно избежать, поэтому используйте условную оптимизацию

@q74 · 25.11.2016, 09:53 **[ТС]**

Спасибо! Я еще узнала, что имеется оператор Собеля: из википедии: Оператор вычисляет градиент яркости изображения в каждой точке. Так находится направление наибольшего увеличения яркости и величина её изменения в этом направлении. Как думаете, может с него начать? А то не очень то меня вдохновляет это многомерная аппроксимация

@cybeuser · 25.11.2016, 10:05

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

Добавлено через 3 минуты
обратитесь в этот раздел возможно вам там дадут более дельные советы
https://www.cyberforum.ru/optimization-methods/

@q74 · 25.11.2016, 10:07 **[ТС]**

Благодарю за помощь!

@Mr.X · 25.11.2016, 18:17

Сообщение от q74

у меня случай zi = f(xi, yi)

А функция формулой задана или как?

@q74 · 25.11.2016, 19:21 **[ТС]**

Функция задана таблично

IGPIGP · 25.11.2016, 20:11

Сообщение от q74

Функция задана таблично

Размер таблицы? В пост поместится?

@q74 · 26.11.2016, 09:21 **[ТС]**

Не поместится) файл большой, могу скинуть фрагмент:

1 1 192
2 1 192
3 1 191
4 1 191
5 1 190
6 1 189
7 1 188
8 1 188
9 1 187
10 1 186
11 1 185
12 1 184
13 1 183
14 1 182
15 1 181
16 1 181
17 1 180
18 1 180
19 1 179
20 1 179
21 1 179
22 1 179
23 1 180
24 1 180
25 1 181
26 1 181
27 1 182
28 1 183
29 1 184
30 1 184
31 1 185
32 1 185
33 1 185
34 1 185
35 1 185
36 1 184
37 1 183
38 1 182
39 1 181
40 1 180
41 1 179
42 1 178
43 1 177
44 1 176
45 1 175
46 1 173
47 1 172
48 1 171
49 1 170
50 1 169
51 1 168
52 1 167
53 1 167
54 1 167
55 1 167
56 1 167
57 1 167
58 1 168
59 1 168
60 1 168
61 1 168
62 1 169
63 1 169
64 1 169
65 1 170
66 1 170
67 1 170
68 1 171
69 1 171
70 1 172
71 1 172
72 1 173
73 1 173
74 1 173
75 1 174
76 1 174
77 1 174
78 1 174
79 1 174
80 1 174
81 1 174
82 1 175
83 1 175
84 1 175
85 1 175
86 1 175
87 1 176
88 1 176
89 1 176
90 1 176
91 1 176
92 1 176
93 1 175
94 1 175
95 1 175
96 1 175
97 1 174
98 1 174
99 1 174
100 1 173
101 1 173
102 1 173
103 1 172
104 1 172
105 1 171
106 1 171
107 1 170
108 1 170
109 1 170
110 1 170
111 1 170
112 1 170
113 1 170
114 1 170
115 1 170
116 1 170

@Mr.X · 26.11.2016, 10:27

Ну, если значений всего 100000, то перебрать их все и не мучиться.

Новые блоги и статьи Все статьи Все блоги /
Изучаю kubernetes lagorue 13.01.2026 А пригодятся-ли мне знания kubernetes в России?	Сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/	WordPad для Windows 11 Jel 10.01.2026 WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .	Classic Notepad for Windows 11 Jel 10.01.2026 Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .
Почему дизайн решает? Neotwalker 09.01.2026 В современном мире, где конкуренция за внимание потребителя достигла пика, дизайн становится мощным инструментом для успеха бренда. Это не просто красивый внешний вид продукта или сайта — это. . .	Модель микоризы: классовый агентный подход 3 anaschu 06.01.2026 aa0a7f55b50dd51c5ec569d2d10c54f6/ O1rJuneU_ls https:/ / vkvideo. ru/ video-115721503_456239114	Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ФедосеевПавел 06.01.2026 Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ВВЕДЕНИЕ Введу сокращения: аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .	Модель микоризы: классовый агентный подход 2 anaschu 06.01.2026 репозиторий https:/ / github. com/ shumilovas/ fungi ветка по-частям. коммит Create переделка под биомассу. txt вход sc, но sm считается внутри мицелия. кстати, обьем тоже должен там считаться. . . .

@q74 0 / 0 / 0 Регистрация: 14.11.2016 Сообщений: 35

	Алгоритм наискорейшего спуска 21.11.2016, 09:56. Показов 5016. Ответов 24 Метки нет (Все метки) Мне нужно найти локальные минимумы в массиве в пределах окрестности. Прочитала про метод наискорейшего спуска, но везде в алгоритмах используется значение функции и вычисленная ее производная. Я не совсем понимаю, если у меня массив состоит из чисел: x y f(x), где f(x) - значение функции, то о какой производной идет речь? Можете дать какие-то наводки по решению данной задачи? 0

@q74 0 / 0 / 0 Регистрация: 14.11.2016 Сообщений: 35
	22.11.2016, 20:56 [ТС]
	Да, опечатка, f(x, y). Метод общего перебора мне известен. Просто хотелось разузнать именно про метод наискорейшего спуска. 0

@cybeuser 109 / 108 / 74 Регистрация: 18.11.2013 Сообщений: 304
	22.11.2016, 22:17
	q74, если функция задана дискретно, то для нахождения производной, которая требуется в градиентном методе, придется интерполировать точки (интерполяционный многочлен Лагранжа, к примеру) 0

@q74 0 / 0 / 0 Регистрация: 14.11.2016 Сообщений: 35
	24.11.2016, 21:52 [ТС]
	Спасибо за совет. Подумав, у меня возник вопрос: у меня массив состоит из более 100000 точек, допустим я запрограммирую написание интерполяционного многочлена Лагранжа, ну а как тогда от него программно находить производную? 0

@q74 0 / 0 / 0 Регистрация: 14.11.2016 Сообщений: 35
	25.11.2016, 08:12 [ТС]
	Думаю, мне нужно более подробно обозначить проблему. Я построила в матлабе график по входному массиву, который представлен тремя переменными: var[0] = x var[1] = y var[2] = z (само значение функции) Нахождение глобального минимума очевидно: это ноль. А вот что касается локальных: на графике они видны, но программно их вычислить у меня не получается. Попробовала начать с простого способа: если значение пикселя меньше значений всех его восьми соседей, то выдать, что это минимум. Увы, на выходе определяется только один минимум - это глобальный. Приблизив и посмотрев график в матлабе, я пришла к выводу, что не все точки на графике, которые предположительно (визуально) являются минимумами, удовлетворяют этому условию. По поводу интерполяционного многочлена Лагранжа: то есть, если использовать численные методы поиска минимума, то явное задание функции необходимо (то есть через f(x))? Изучила информацию про метод покоординатного спуска, который включает в себя подметод золотого сечения. Может лучше вместо градиентного метода спуска использовать тот, где не нужно находить производную? Миниатюры 0

@q74 0 / 0 / 0 Регистрация: 14.11.2016 Сообщений: 35
	25.11.2016, 08:17 [ТС]
	P. S. И Еще: в интернете я нашла только как строить многочлен Лагранжа для функции заданной в виде xi и yi, а у меня случай zi = f(xi, yi)... 0

@cybeuser 109 / 108 / 74 Регистрация: 18.11.2013 Сообщений: 304
	25.11.2016, 08:48
	q74, для нахождения множества локальных минимумов используйте мультистарт, то есть несколько начальных приближений, можете расположить их равномерно, но это всё равно не гарантирует нахождение всех минимумов. Для использования методов оптимизации вам все равно придется найти хоть какую-то функцию, которая способна отражать значения во всех точках её определения. Почитайте про аппроксимацию многомерных функций. 0

@q74 0 / 0 / 0 Регистрация: 14.11.2016 Сообщений: 35
	25.11.2016, 08:56 [ТС]
	Прочитала немного про аппроксимацию многомерных функций... как я поняла, в моем случае подбирать функцию придется в ручную? То есть попробовать сначала линейную модель, если не подойдет, то квадратичную, потом кубическую, если нужно добавить экспоненты... 0

@cybeuser 109 / 108 / 74 Регистрация: 18.11.2013 Сообщений: 304
	25.11.2016, 09:00
	q74, посмотрите на функцию, на какую она похожа? Добавлено через 2 минуты в общем, пробуйте всё, будет очень полезно 0

@q74 0 / 0 / 0 Регистрация: 14.11.2016 Сообщений: 35
	25.11.2016, 09:01 [ТС]
	Там где глобальный минимум и в ближайшей окрестности - это параболоид, а за пределами: то возвышенность, то углубление - не понятно Добавлено через 19 секунд Хорошо, попробую, спасибо 0

@cybeuser 109 / 108 / 74 Регистрация: 18.11.2013 Сообщений: 304
	25.11.2016, 09:37
	q74, и не забудьте что исследование функции вне заданных значений нужно избежать, поэтому используйте условную оптимизацию 0

@q74 0 / 0 / 0 Регистрация: 14.11.2016 Сообщений: 35
	25.11.2016, 09:53 [ТС]
	Спасибо! Я еще узнала, что имеется оператор Собеля: из википедии: Оператор вычисляет градиент яркости изображения в каждой точке. Так находится направление наибольшего увеличения яркости и величина её изменения в этом направлении. Как думаете, может с него начать? А то не очень то меня вдохновляет это многомерная аппроксимация 0

@cybeuser 109 / 108 / 74 Регистрация: 18.11.2013 Сообщений: 304
	25.11.2016, 10:05
	q74, про данный оператор я ничего не знаю, скажу так, что я в своё время решал задачу аппроксимации при помощи нейронных сетей, простор открыт, пробуйте всё. А вообще градиент - это "вектор, своим направлением указывающий направление наибольшего возрастания некоторой величины" . Добавлено через 3 минуты обратитесь в этот раздел возможно вам там дадут более дельные советы https://www.cyberforum.ru/optimization-methods/ 0

@q74 0 / 0 / 0 Регистрация: 14.11.2016 Сообщений: 35
	25.11.2016, 10:07 [ТС]
	Благодарю за помощь! 0

@q74 0 / 0 / 0 Регистрация: 14.11.2016 Сообщений: 35
	25.11.2016, 19:21 [ТС]
	Функция задана таблично 0

@q74 0 / 0 / 0 Регистрация: 14.11.2016 Сообщений: 35
	26.11.2016, 09:21 [ТС]
	Не поместится) файл большой, могу скинуть фрагмент: 1 1 192 2 1 192 3 1 191 4 1 191 5 1 190 6 1 189 7 1 188 8 1 188 9 1 187 10 1 186 11 1 185 12 1 184 13 1 183 14 1 182 15 1 181 16 1 181 17 1 180 18 1 180 19 1 179 20 1 179 21 1 179 22 1 179 23 1 180 24 1 180 25 1 181 26 1 181 27 1 182 28 1 183 29 1 184 30 1 184 31 1 185 32 1 185 33 1 185 34 1 185 35 1 185 36 1 184 37 1 183 38 1 182 39 1 181 40 1 180 41 1 179 42 1 178 43 1 177 44 1 176 45 1 175 46 1 173 47 1 172 48 1 171 49 1 170 50 1 169 51 1 168 52 1 167 53 1 167 54 1 167 55 1 167 56 1 167 57 1 167 58 1 168 59 1 168 60 1 168 61 1 168 62 1 169 63 1 169 64 1 169 65 1 170 66 1 170 67 1 170 68 1 171 69 1 171 70 1 172 71 1 172 72 1 173 73 1 173 74 1 173 75 1 174 76 1 174 77 1 174 78 1 174 79 1 174 80 1 174 81 1 174 82 1 175 83 1 175 84 1 175 85 1 175 86 1 175 87 1 176 88 1 176 89 1 176 90 1 176 91 1 176 92 1 176 93 1 175 94 1 175 95 1 175 96 1 175 97 1 174 98 1 174 99 1 174 100 1 173 101 1 173 102 1 173 103 1 172 104 1 172 105 1 171 106 1 171 107 1 170 108 1 170 109 1 170 110 1 170 111 1 170 112 1 170 113 1 170 114 1 170 115 1 170 116 1 170 0

@Mr.X 3225 / 1752 / 436 Регистрация: 03.05.2010 Сообщений: 3,867
	26.11.2016, 10:27
	Ну, если значений всего 100000, то перебрать их все и не мучиться. 1